VibeMathedMath problems solved with AI
Sign in

Explicit nonbipartite Ramanujan graphs of every degree

A dd-regular graph is Ramanujan if every nonconstant adjacency eigenvalue λ\lambda satisfies ∣λ∣≤2d−1|\lambda|\le2\sqrt{d-1}, the Alon-Boppana optimum. Lubotzky, Phillips and Sarnak and Margulis built explicit Ramanujan families only for d=p+1d=p+1, Morgenstern extended this to d=q+1d=q+1 for prime powers qq, and Marcus, Spielman and Srivastava proved existence of bipartite Ramanujan graphs of every degree. Existence of nonbipartite ones in every degree now follows from random-graph universality (Huang, McKenzie, Yau), but non-constructively. For every fixed d≥3d\ge3, can nonbipartite dd-regular Ramanujan graphs be constructed deterministically, in polynomial time, at every large size?

Result
Proved(see note)
Status
Candidate (review pending)
AI contribution
AI-discovered
Method
Construction
Field
Spectral graph theory; expanders
Posed by
Alexander Lubotzky, Ralph Phillips and Peter Sarnak
Year posed
1988
Years open
38y
Solved
2026-09-23
Model
Unreleased internal OpenAI model
Vendor
OpenAI
Collaborators
—
Verification
Unreviewed
Publication
Announced
Collection
OpenAI math release (October 2026), version adc7f12
Significance
36 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

Theorem 1.1: for every d≥3d\ge3 there are n0(d)n_0(d), kdk_d and a deterministic algorithm that, on every even n≥n0(d)n\ge n_0(d), outputs the adjacency list of a simple connected nonbipartite dd-regular graph on nn vertices whose nonconstant eigenvalues lie strictly between ±2d−1\pm2\sqrt{d-1}, in Od(nkd)O_d(n^{k_d}) bit operations. The construction uses partial pairings, deterministic resolvent estimates, cleanup and an exact spectral repair step. It is not strongly explicit (no local adjacency queries), and the exponent may grow with dd.

What the AI did

The release README says every result in it was produced by an unreleased internal OpenAI model following a fixed procedure, on average about three hours of ChatGPT Pro thinking compute per result, and that some outputs build on earlier model results. This result is not among the README's exceptions (the Hodge conjecture for CM abelian varieties and the Re(s) > 11/12 zero-free region). The manuscript is authored 'OpenAI' and names no human author. Single-manuscript family dated September 23, 2026.

Verification

No independent mathematician has checked this yet. Checked here: Theorem 1.1 and Section 1.1 were read against the posed problem. The theorem gives, for each fixed d≥3d\ge3, a deterministic algorithm that on even n≥n0(d)n\ge n_0(d) outputs a simple dd-regular graph on nn vertices in Od(nkd)O_d(n^{k_d}) bit operations with every nonconstant eigenvalue strictly inside (−2d−1,2d−1)(-2\sqrt{d-1},2\sqrt{d-1}). Scope limits stated by the paper: the exponent and threshold depend on dd, running time is not polynomial jointly in nn and dd, there is no local neighbour-query algorithm, and the Bilu-Linial signing conjecture is not resolved. Existence alone was already known from Huang-McKenzie-Yau. No Lean formalization exists for this family. The proof was not refereed.

Source

Changelog1 change

Discussion