Deterministic Ramanujan graphs in every degree
From OpenAI Aftermath
A Ramanujan graph is a d-regular graph whose adjacency eigenvalues other than d all lie in [−2√(d−1), 2√(d−1)], the best possible spectral window for large graphs by the Alon–Boppana bound. Arithmetic constructions give such graphs only in special degrees, and the interlacing method of Marcus, Spielman and Srivastava gives bipartite ones in every degree; random regular graphs are Ramanujan with positive probability, but that gives no explicit construction. A manuscript in OpenAI's public mathematics collection (github.com/openai/math), dated 23 September 2026, claims a deterministic polynomial-time construction of nonbipartite Ramanujan graphs for every fixed degree d ≥ 3 and every sufficiently large even number of vertices. The family has no Lean formalization in the repository's catalogue. This page summarizes the published claim and lists publicly available follow-up work, including a public flaw report. Statements are the respective authors' claims; the publication of a paper is not presented here as independent verification.
Background
- As recounted in the introduction of the manuscript:
- Lubotzky, Phillips and Sarnak and Margulis constructed Ramanujan graphs arithmetically in restricted degrees and on arithmetic sequences of orders; Morgenstern extended the degrees to q + 1 for every prime power q, including nonbipartite families.
- Bilu and Linial introduced graph two-lifts and signings. Marcus, Spielman and Srivastava used interlacing polynomials to obtain bipartite Ramanujan graphs in every degree, where bipartite symmetry controls the negative edge of the spectrum; Hall, Puder and Sawin extended the covering theorem, and Cohen made the matching construction of Marcus, Spielman and Srivastava, which gives bipartite multigraphs, deterministic in polynomial time.
- Mohanty, O'Donnell and Paredes, and Alon, gave deterministic constructions within any fixed margin 2√(d−1) + ε of the bound; the manuscript notes that these leave a positive spectral error.
- Friedman proved that random regular graphs are near-Ramanujan, and Huang, McKenzie and Yau showed that the probability that a random regular graph is exactly Ramanujan tends to about 0.69, so that such graphs exist at every large size with dn even. The manuscript attributes existence to this work and presents its contribution as a deterministic construction.
The original result
- Claim. Theorem 1.1 of Deterministic nonbipartite Ramanujan graphs in every fixed degree states that for every integer d ≥ 3 there are constants n0(d) and kd and a deterministic algorithm that, on input an even integer n ≥ n0(d), outputs the adjacency list of a simple d-regular graph on n vertices in Od(nkd) bit operations, with every eigenvalue on the vectors orthogonal to the constant vector strictly between −2√(d−1) and 2√(d−1). The graph is therefore connected and nonbipartite.
- The manuscript states that the exponent and the size threshold may depend on d, and that it does not assert a running time polynomial jointly in n and d or a local adjacency-query algorithm. It also states that the construction does not resolve the Bilu–Linial conjecture on two-lifts.
- Method, as described: half-edges are paired one at a time by a derandomized procedure that tracks the spectral distance to both edges of the window through a family of error statistics. After cleanup and completion, the intermediate graph has its spectrum within a margin e/20 of the window, where e = n−2/3+a and a = 10−4, together with local bounds on the spectral mass near either edge. A final stage, Theorem 8.3, repairs the remaining error exactly by ⌈n1/3+10a⌉ simultaneous vertex-disjoint edge switches drawn from a tilted law that biases the modes closest to either edge, and the strict bound is certified in exact rational arithmetic.
- Source (openai/math repository, commit
7ef5c0c): Deterministic nonbipartite Ramanujan graphs in every fixed degree, dated 23 September 2026. The repository history at this commit shows no change to the manuscript after its initial commit of 6 October 2026.
Public follow-up work
| Date | Work | Relation | Public claim | Public status (checked 30 October 2026) |
|---|---|---|---|---|
| 2026-10-07 | Deterministic graphs at the exact Ramanujan threshold, an article of the Latent Seminar blog at lowrank.github.io | Reading (exposition) | Explains the exact spectral threshold, its consequences for expansion, the pairing of half-edges with spectral information, the repair of both spectral edges and exact certification, with proof outlines on eliminating only the bulk, why uniform switches cannot repair a negative slack, how local spectral mass pays for errors and valid switches, and the polynomial search space from pairwise independence. | Blog article; it states that its review covers statements, introductions and selected proof mechanisms and is not an independent verification of the complete proofs. |
| 2026-10-10 | Malt7635 (GitHub user), Flaw report: openai/math family 178, a public GitHub Gist | Critique | States that Step 2 of Theorem 8.3 asserts that the number JT of near-edge modes is of order n3a/2+a/10, while the theorem's own local spectral-mass hypothesis, summed over all vertices, bounds it by a constant times n3a/2. It argues that the positivity of the tilted law and the bias estimate both need the larger order, so that the exact repair stage fails and only the near-Ramanujan spectrum of the earlier stages is established, and that the gap is not fixable by tuning constants. It reports numerical checks of the surrounding algebra on small random regular graphs and mentions a possible repair direction without verifying it. | Unreviewed report by a GitHub user; the manuscript has not been revised in the repository as of the date above. Collected in the community revision's agent notes for this paper. |
| 2026-10-11 | Lermont, Benchmark spectral topology selection for P2P broadcast and audit family 178 feasibility, a merged pull request in the public fork Lermont/math | Experiment (application study) | A simulation study of peer-to-peer flooding that compares random regular graphs, a spectral selection heuristic and an LPS Ramanujan graph. Its stated main conclusion is that global connectivity helps and that additional gains from spectral selection are not established; it states that the deterministic construction of the manuscript is not implemented or benchmarked. | Repository experiment; the pull request states that no independent peer review is documented. |
| 2026-10-16 | J. Jardine, Lattice24, referee review rank_091 in JJardine919/openai-math-audit (archived at Zenodo 10.5281/zenodo.23422995) | Review (AI-assisted audit) | Reports no gap. Its one minor note says that the typical-edge argument relies on a bounded count of nonbacktracking paths supplied by the structural accounts, whose maintenance through the cleanup stage it only skimmed, and calls this the least directly verified link. The review lists the exact-repair theorem among the parts it read in full and the positivity of the tilted density among the steps it checked by hand; it does not mention the flaw report. | Part of an audit that its README describes as complete for the collection's manuscripts without a Lean formalization. The review is published under CC BY 4.0. |
| 2026-10-16 | AI Proved What?, episode 178 Ramanujan graphs, made to order?, remade versions of 22 and 24 October 2026 | Reading (exposition) | Video explainer of the claim and its history. The episode states that existence is not new and is credited to Huang, McKenzie and Yau, that no threshold n0(d) or exponent is computed, that only even sizes are covered, that the Bilu–Linial conjecture is not settled and that there is no implementation, and computes that one margin in the manuscript's table grows only like n7.4a, about 1.02 even at n = 1012. | Web page and video; the site states that its scripts and animations are produced with AI assistance and that the narration is an AI-generated voice. Status record last checked 27 October 2026: posted as a preprint: OpenAI, 85 pages, dated September 23, 2026; under expert review: not yet; peer reviewed: not yet; checked in Lean: not formalized. The page states that it has seen no expert review; it does not mention the flaw report. |
Notes
- The background summarizes the manuscript's own account of earlier work.
- The flaw report is listed as a public critique; this page does not assess it.
- The list covers follow-ups found in public sources up to the date above; it is not a priority or completeness claim.
