Deterministic graphs at the exact Ramanujan threshold

Source and verification

This article explains family 178 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ The exact spectral threshold

For a simple $d$-regular graph $G$, the adjacency matrix $A$ has eigenvalue $d$ on the constant vector. The remaining spectrum is the restriction to $1^{\perp }$, the vectors whose coordinates sum to zero. A two-sided Ramanujan bound requires

$$\Vert A{|}_{1^{\perp }}\Vert \le 2\sqrt{d-1}.$$

The right side is the spectral radius of the infinite $d$-regular tree and is asymptotically optimal for large graphs of fixed degree. Both spectral ends matter. A bipartite regular graph has eigenvalue $-d$, which lies in $1^{\perp }$ and violates this convention for $d\ge 3$.

Manuscript claim

For every fixed integer $d\ge 3$, a deterministic algorithm produces, at every sufficiently large even order $n$, a simple $d$-regular graph whose nonconstant eigenvalues satisfy

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

It outputs the full adjacency list in $O_d(n^{k_d})$ bit operations. The size threshold and exponent may depend on $d$. (OpenAI, 2026)

This is not a complexity bound polynomial jointly in $n$ and $d$, nor a local adjacency-query algorithm. It asserts even orders; rounding an arbitrary sufficiently large target size upward gives a graph with either $N$ or $N+1$ vertices.

🏷️ Expansion and elementary spectral consequences

The strict bound forces connectedness. If there were two components, a nonconstant vector constant on each component could be chosen orthogonal to $1$, giving another eigenvalue $d$. It also excludes bipartiteness by the eigenvalue $-d$ observation.

For vertex subsets $S,T$, write $E(S,T)=1_S^{\mathsf{T}}A{1}_T$ and decompose their indicator vectors into constant and mean-zero parts. The spectral bound gives

$$\begin{array}{c}\left|E(S,T)-\frac{d|S||T|}{n}\right|\\ \le 2\sqrt{d-1}\sqrt{|S||T|}.\end{array}$$

Thus edge counts are close to the uniform-density prediction. The left side counts directed incidences when $S,T$ overlap, so the formula should not be interpreted as an unordered internal-edge count without the appropriate factor two.

Near-Ramanujan constructions allow a fixed positive error beyond the tree threshold. The manuscript must remove that error while preserving simplicity, regularity, and the exact number of vertices.

🏷️ Pairing half-edges with spectral information

Give every vertex $d$ labeled stubs; pairing stubs creates edges. The algorithm chooses successive pairings using nonnegative statistics and the method of conditional expectations. Each statistic is discounted by its own controlled growth factor, so one choice can preserve several estimates simultaneously.

Besides spectral confinement, the proof retains entrywise information about inverse matrices and weighted nonbacktracking paths, which never immediately reverse an edge. A cleanup stage pairs nearby unresolved stubs until the remaining boundary vertices are well separated from one another and from short returns.

Low-rank inverse update formulas then control completion of the pairing. The order of estimates matters: squared row energies are reduced before they are used to improve individual entry bounds. The result is a simple regular graph with spectrum inside a narrow neighborhood of the target interval and with the local data needed for repair.

🏷️ Repairing both spectral edges

Set $s=2\sqrt{d-1}$ and $e=n^{-2/3+a}$, with the fixed $a=10^{-4}$. The intermediate graph has spectral excess only of order $e$. For an orthonormal nonconstant eigenbasis $v_i$, define signed gaps $x_i^{\sigma }=s-\sigma {\lambda }_i$ for $\sigma \in \{+1,-1\}$.

The source controls local mass near either edge:

$$\sum _{i:x_i^{\sigma }\le w}|v_i(p){|}^2\le C{w}^{3/2}.$$

Summing over vertices shows that only $O(n{e}^{3/2})=O(n^{3a/2})$ modes lie within distance $O(e)$ of an edge. Thus only a comparatively small subspace needs a positive correction.

A valid edge switch replaces $uv,xy$ by $uy,xv$, with four distinct endpoints and absent new edges. Vertex-disjoint valid switches preserve the required graph constraints. Their spectral effect depends on local eigenvector mass, so a global norm estimate alone cannot choose useful switches.

The proof also controls two-by-two endpoint blocks of a truncated inverse on the bulk modes. It does not assume that the full inverse at the tree edge exists. Eliminating the bulk by a Schur complement leaves a quadratic-form problem on near-edge modes. A small bias in the switch distribution gives positive mean correction to the closest modes at both signs, and local mass bounds control fluctuations. The remaining modes retain enough positive slack.

🏷️ Exact certification and computational scope

The existence of successful switches is followed by a finite deterministic search. If the columns of a rational matrix $B$ form a basis of $1^{\perp }$, the final certificate is positive definiteness of the rational matrix

$$B^{\mathsf{T}}(4(d-1)I-A^2)B.$$

This exactly expresses strict containment of every nonconstant eigenvalue between the two tree edges. Numerical eigenvalues rounded near the threshold would not be an equivalent certificate.

The manuscript proves that its polynomial search contains a passing candidate and analyzes bit precision throughout. These notes do not implement that construction or certify a generated graph. The statement also does not resolve the separate conjecture that every regular graph has a two-lift with the corresponding two-sided bound on new eigenvalues.

🏷️ Key steps and proof outlines

Eliminate only the bulk, where inversion is legitimate

The repair theorem starts with the three quantitative outputs of the pairing construction: spectral confinement within $e/20$ of both tree edges, local spectral mass bounded by $C{w}^{3/2}$, and typical two-endpoint bulk inverse blocks. Set $s=2\sqrt{d-1}$, $e=n^{-2/3+a}$, $a=10^{-4}$, and use $M=\lceil n^{1/3+10a}\rceil$ switches. (OpenAI, 2026)

For a switch replacing $uv,xy$ by $uy,xv$, write $U=[e_u-e_x,e_v-e_y]$ and $F=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$. For sign $\sigma \in \{+1,-1\}$, the precision matrix changes by $U(\sigma F)U^{\mathsf{T}}$. Concatenate these columns and blocks for all switches.

Split nonconstant eigenmodes into a near space and a bulk with signed slack $x_i^{\sigma }=s-\sigma {\lambda }_i$ at least a cutoff $w_B^{\sigma }\asymp n^{-2/3+100a}$. The old bulk precision $D_B$ is positive definite. With $R_B^{\sigma }$ its inverse extended by zero on the near space, define

$$S_B=C_{\sigma }^{-1}+U^{\mathsf{T}}{R}_B^{\sigma }U.$$

The ideal two-by-two block of $S_B$ is

$$\frac{1}{d-2}\left(\begin{array}{cc}s& \sigma d\\ \sigma d& s\end{array}\right),$$

with determinant $-1$ and one eigenvalue of each sign. Closeness to these blocks preserves inertia. Comparing the two Schur complements of the corresponding block matrix proves that the updated bulk is positive definite. Its elimination leaves the exact near matrix

$$\mathrm{diag}(x_i^{\sigma })+U_E{S}_B^{-1}{U}_E^{\mathsf{T}}.$$

This remains valid when some old near slacks are negative. Inverting the full old precision at the tree edge would not be justified.

Uniform switches cannot repair a negative slack

Let $K_{\sigma }$ be the inverse ideal block, and for an oriented edge $g=(u,v)$ put $z_i(g)=(v_i(u),v_i(v){)}^{\mathsf{T}}$. Regularity and eigenvector orthogonality imply

$$\mathbb{E}{z}_i(g)=0,\mathbb{E}[z_i(g)z_k(g{)}^{\mathsf{T}}]=\frac{{\delta }_{ik}}{n}\left(\begin{array}{cc}1& {\lambda }_i/d\\ {\lambda }_i/d& 1\end{array}\right).$$

For two independent uniform oriented edges, the mean ideal near correction has diagonal entry $-4x_i^{\sigma }/((d-2)n)$. Summing switches merely multiplies the old slack by $1-4M/((d-2)n)$, which preserves its sign. A bias is genuinely necessary.

The source tilts the pair law using cross-edge correlations of the modes with slack below a cutoff in $[2e,3e]$. Local spectral mass makes this density a positive $1+o(1)$ perturbation. Its conditional mean is one when either edge is fixed, so both edge marginals remain uniform. The new mean correction on each targeted mode includes a positive multiple of

$$\mathrm{tr}(K_{\sigma }{M}_i{K}_{\sigma }{M}_i)=\Vert M_i^{1/2}{K}_{\sigma }{M}_i^{1/2}{\Vert }_{\mathrm{F}}^2,$$

where $M_i$ is the positive matrix above. Its size after $M$ draws is comparable with $M/(J_{T}n)\asymp n^{-2/3+8.4a}\gg e$. It dominates the possible negative slack. Untargeted near modes already have slack at least $2e$ and keep a positive margin. The same tilt includes both signs.

Local mass pays for errors and valid switches

Condition on typical original edges for the fixed bulk cutoffs. This loses probability $O(n^{-0.1})$. The local projector estimate bounds one near correction by $O(W_b^{3/2})$, so the total conditioning error is $O(M{n}^{-0.1}{W}_b^{3/2})=o(e)$. Second moments similarly control the centered near sum and bulk inverse error. After sandwiching by $U_E$, the latter also contributes $o(e)$ to the near matrix.

Endpoint collisions or already-present proposed edges have total probability $O_d(M^2/n)=o(1)$. Hence a successful collection is vertex-disjoint and preserves simplicity, degrees, and vertex count. The mean positive margin survives every error, proving strict positivity of both signed precisions.

Pairwise independence gives a polynomial search space

Only pairwise independence between switch draws is needed for these second-moment and collision estimates. Approximate the finite pair law by assigning outcomes to residues modulo a polynomial-size prime $P>M$. Enumerate the $P^2$ seeds $(\gamma ,\beta )$ and use residues $\gamma r+\beta$ for draw $r$. For distinct $r,t$, the map to their two residues is invertible, giving exactly uniform independent pairs.

The proof guarantees a passing seed. Each candidate is tested by exact rational positivity of $B^{\mathsf{T}}(4(d-1)I-A^2)B$ for a contrast basis $B$ of $1^{\perp }$. Thus approximate projectors choose a finite search law, while exact arithmetic certifies the final strict threshold. The preceding pairing and local inverse estimates remain essential inputs to this repair argument.

See Also

• Coboundary expanders generalizes expansion to faces of higher-dimensional complexes.
• Thin-tree construction also separates an existence argument from the additional obligations of finite-bit computation.

🏷️ Manuscripts and verification scope

• Deterministic nonbipartite Ramanujan graphs in every fixed degree — pinned manuscript and companion source.

No family scope page was present at lean/docs/178.md in the pinned snapshot. This does not establish that all related formalization code is absent. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026. Deterministic nonbipartite Ramanujan graphs in every fixed degree.