Constructing exact nonbipartite Ramanujan graphs at prescribed sizes

← All digests

Family 178 · Combinatorics
Importance 4/5 · Provisional editorial rating
Sources consulted 2026-10-11

1. The question

A sparse network can still spread information remarkably well if its edges are distributed evenly. Ramanujan graphs reach the sharp asymptotic spectral target for this kind of expansion. But existence, efficient construction, exact spectral bounds and freedom to prescribe the number of vertices are different achievements.

The manuscript claims a deterministic construction combining all four in the nonbipartite setting. For every fixed degree at least three, it produces a simple regular graph on every sufficiently large even number of vertices, with all nonconstant adjacency eigenvalues strictly inside the Ramanujan interval.

The construction first gets extremely close to the desired spectral interval and then repairs the remaining excess using carefully selected edge switches. The repair must improve both ends of the spectrum while preserving every vertex degree and the exact number of vertices.

2. Background and essential definitions

A graph is $d$-regular when every vertex has exactly $d$ neighbors. Its adjacency matrix $A$ has entry one at adjacent vertex pairs and zero elsewhere. For an undirected graph this matrix is symmetric, so all its eigenvalues are real.

The constant vector $\mathbf1$ is an eigenvector with eigenvalue $d$. The remaining eigenvectors can be taken perpendicular to it: their coordinates sum to zero. Write $\mathbf1^\perp$ for that subspace. The spectrum there measures deviations from uniform behavior.

For example, applying $A/d$ to a vector averages its values over neighboring vertices. On a nonconstant eigenvector, one averaging step multiplies its amplitude by $\lambda/d$. Small absolute eigenvalues therefore mean rapid decay of nonuniform modes.

The Ramanujan bound is

$$|\lambda|\leq2\sqrt{d-1}.$$

The number on the right is the spectral radius of the infinite $d$-regular tree. The Alon–Boppana phenomenon makes it the optimal asymptotic target for large fixed-degree graphs.

Bipartite graphs have a special complication: assigning opposite signs to the two vertex classes gives an eigenvalue $-d$. The usual bipartite Ramanujan convention excludes both $d$ and $-d$ from the bound. This manuscript instead bounds the entire restriction to $\mathbf1^\perp$, so $-d$ is not exempt. Its output must consequently be nonbipartite.

“Simple” means no loops or parallel edges. “Deterministic polynomial time” here means producing the whole adjacency list using polynomially many bit operations when $d$ is fixed. It does not mean answering each adjacency query in time logarithmic in the graph’s order.

3. Development history and previous partial results

Lubotzky, Phillips and Sarnak, and independently Margulis, constructed Ramanujan graphs using arithmetic methods. Morgenstern extended the available degrees to $q+1$ for every prime power $q$. These gave exact infinite families, but with restrictions on degrees and graph orders.

Bilu and Linial developed constructions through two-lifts: replace each vertex by two copies and choose one of two possible matchings above each edge. The new eigenvalues are those of a signed adjacency matrix. Marcus, Spielman and Srivastava used interlacing polynomials to obtain bipartite Ramanujan families in every degree. Spectral symmetry in bipartite graphs turns one-sided control into control of both nontrivial spectral edges.

Further work produced bipartite Ramanujan multigraphs at all even orders, and Cohen made that construction deterministic in polynomial time. These are substantial exact results, but bipartiteness and permitted parallel edges distinguish them from the present output model.

For simple nonbipartite graphs, deterministic constructions approached the threshold with an additive error. Mohanty, O’Donnell and Paredes obtained bounds $2\sqrt{d-1}+\varepsilon$ for every fixed positive $\varepsilon$. Alon achieved such bounds at every sufficiently large admissible order.

Random graphs supplied stronger existence information. Friedman’s theorem says a uniformly random simple regular graph is near-Ramanujan with probability tending to one. Huang, McKenzie and Yau obtained spectral-edge universality in every fixed degree, implying exact Ramanujan existence at every sufficiently large admissible size. The manuscript cites an asymptotic probability of about $0.69$ for the exact two-sided event.

The gap addressed here is therefore deterministic polynomial-time construction at the exact threshold and a prescribed even order. It is not the first existence theorem for exact nonbipartite examples of arbitrary fixed degree.

4. What the new manuscripts claim

For every fixed integer $d\geq3$, the manuscript states that there are constants $n_0(d)$ and $k_d$, and a deterministic algorithm that, for every even integer $n\geq n_0(d)$, outputs a simple $d$-regular graph on exactly $n$ vertices in

$$O_d(n^{k_d})$$

bit operations. Every eigenvalue of its adjacency matrix on $\mathbf1^\perp$ satisfies the strict inequalities

$$-2\sqrt{d-1}<\lambda<2\sqrt{d-1}.$$

The subscript on $O_d$ allows the hidden constant to depend on $d$. The exponent and minimum permitted size may also depend on $d$.

The output is connected. If it had more than one connected component, a nonconstant vector constant on each component would supply another eigenvalue $d$, outside the permitted interval. It is also nonbipartite because a bipartition would supply $-d$.

A convenient size corollary follows: for every sufficiently large requested integer $N$, the algorithm produces such a graph with

$$N\leq|V(G)|\leq N+1,$$

by choosing the least even integer at least $N$. The main theorem does not cover every admissible odd order when $d$ is even.

The strict interior conclusion does not contradict the asymptotic optimality of the tree threshold. The distance from the spectral edge can shrink as the graph grows; no fixed positive improvement below $2\sqrt{d-1}$ is asserted for the entire family.

5. Why the advance matters

Importance: 4/5. The claim brings exact spectral quality, deterministic construction, simplicity and fine size control together for every fixed degree. Each feature was available in substantial earlier settings, but their simultaneous combination is a major constructive advance.

The difference between an arbitrarily small fixed error and zero error is especially important mathematically. A near-Ramanujan construction may place an eigenvalue just outside the sharp interval. Merely choosing a smaller fixed error does not provide a polynomial-time exact construction with the same guarantees.

The manuscript’s repair method also separates global spectral control from local eigenvector information. A small number of edge changes can have unpredictable effects if an eigenvector concentrates at their endpoints. Coordinating those local effects at both spectral edges is the central additional work. The rating reflects that construction problem, while crediting the earlier random existence and bipartite exact results.

6. The main idea

Build a nearly correct regular graph

Give each vertex $d$ distinguishable half-edges, often called stubs. Pairing two stubs creates an edge. A complete pairing makes every degree exactly $d$, although careless pairings could create loops or repeated edges.

The algorithm chooses pairs while tracking several matrix statistics. These include global spectral estimates and local comparisons with the infinite regular tree. It selects each next pair through a deterministic averaging principle: if the average future cost is controlled, at least one available choice preserves the combined bound.

The tracked quantities include sums over nonbacktracking paths, which never immediately reverse their last edge. Such paths are well suited to comparisons with a tree and to spectral analysis of regular graphs.

Separate and complete the unresolved boundary

After most stubs are paired, the construction removes troublesome nearby interactions among those left unresolved. The remaining stubs lie at distinct, well-separated vertices, with no short relevant return paths.

This separation makes the final pairing easier to control. Matrix inverse-update identities track how each completion changes the spectral reference. The first three stages produce a simple regular graph whose nonconstant eigenvalues lie within a very small error of the desired interval, while preserving additional local information for the repair stage.

The error scale used in the paper is close to $n^{-2/3}$. At that scale, only a small spectral subspace lies near either troublesome edge. More importantly, the construction bounds how much of that subspace can concentrate at any individual vertex.

Repair both ends using switches

An edge switch removes $\{u,v\}$ and $\{x,y\}$, then inserts $\{u,y\}$ and $\{x,v\}$. When endpoints and existing edges satisfy the appropriate conditions, this preserves simplicity, all degrees and the vertex set.

The manuscript chooses many compatible switches with a slight bias designed to improve eigenvalues near both $2\sqrt{d-1}$ and $-2\sqrt{d-1}$. Local eigenvector-mass bounds control fluctuations, while comparisons on typical edge endpoints control interactions with spectral modes farther from the edge.

The proof uses a Schur complement, a standard block-matrix operation that eliminates one group of variables, to isolate the remaining near-edge problem. It then establishes a positive shift large enough to move those modes strictly inside the interval.

The final algorithm checks an exact rational matrix inequality. If the columns of $B$ form a rational basis of $\mathbf1^\perp$, strict positivity of

$$B^T\bigl(4(d-1)I-A^2\bigr)B$$

certifies the desired strict bound. This is part of the manuscript’s stated construction, allowing exact spectral certification without relying on rounded numerical eigenvalues.

7. Scope, limitations, and open questions

The degree is fixed. The theorem does not claim running time polynomial jointly in $n$ and $d$, nor an optimized exponent for practical implementation. The threshold $n_0(d)$ may be large.

The construction outputs the complete graph description. Stronger notions of explicitness, such as fast local adjacency queries from a short vertex label, are not asserted. It also provides no promise of a large fixed spectral margin below the Ramanujan boundary.

The even-order restriction remains part of the theorem. For odd degree, parity already forces even order because the total degree must be twice the number of edges. For even degree, odd orders are possible in principle but are not covered here.

Finally, the argument does not resolve the Bilu–Linial conjecture that every regular graph has a two-lift with all new eigenvalues within the Ramanujan interval. It constructs graphs using partial pairings and switches, rather than proving the required signing for every prescribed base graph.

8. Sources and further reading

The manuscript’s introduction separates exact existence, near-Ramanujan construction, bipartite conventions and prescribed-size output. Its four-stage roadmap explains the local information retained for spectral repair.

Primary milestones include Lubotzky–Phillips–Sarnak, Marcus–Spielman–Srivastava’s bipartite construction, Alon’s every-size near-Ramanujan graphs, and Huang–McKenzie–Yau’s exact random existence result. The source bibliography also identifies the earlier deterministic multigraph algorithm and the local spectral methods adapted in this construction.

Source manuscripts

• M1. OpenAI, Deterministic nonbipartite Ramanujan graphs in every fixed degree (September 23, 2026).

Sources consulted on 11 October 2026 at repository revision fd4aeeb. Download the manuscript citations.