Ramanujan graphs, made to order?
A preprint claims a deterministic polynomial-time construction of nonbipartite Ramanujan graphs in every fixed degree, at every large even size, tight at both ends of the spectrum
Covers result 178 in OpenAI’s catalog: its one paper. See its connections to other results and the work it cites.
7:06. English captions available. The video loads from YouTube when you press play.
Chapters
The claim, in plain words
In a d-regular graph every vertex has d neighbours. Its adjacency matrix always has the eigenvalue d, from the constant vector; the other eigenvalues measure how well the graph mixes, and the smaller they are in size, the more closely the edges between any two large sets of vertices match an even spread. They cannot all be small: on large graphs some come close to 2√(d−1), the spectral radius of the infinite d-regular tree (the Alon–Boppana bound). A Ramanujan graph meets this exactly: every eigenvalue other than the trivial one lies in [−2√(d−1), 2√(d−1)]. The Petersen graph (d = 3) has eigenvalues 3, 1 and −2, well inside the window of about ±2.83. In this paper’s convention both ends count, so a bipartite graph, which always has the eigenvalue −d, fails; by our computation, a cubic prism on 34 vertices fails at both ends.
As the paper recounts, Lubotzky, Phillips and Sarnak, and Margulis, built Ramanujan graphs from arithmetic in restricted degrees and on special sizes, and Morgenstern extended the degrees to q + 1 for every prime power q, including nonbipartite families. Marcus, Spielman and Srivastava used interlacing polynomials to get bipartite Ramanujan graphs of every degree, where symmetry controls the bottom end, and Cohen made their matching construction, which gives bipartite multigraphs, deterministic in polynomial time. Mohanty, O’Donnell and Paredes, and Alon, gave deterministic constructions within any fixed margin of the bound, Alon’s at every sufficiently large size with dn even; “These constructions leave a positive spectral error.” Friedman proved that random regular graphs are nearly Ramanujan, and by Huang, McKenzie and Yau the chance of being exactly Ramanujan tends to about 0.69, so such graphs exist at every large size with dn even. In our simulation of uniformly random cubic graphs, the share is about 0.87 at 100 vertices and 0.79 at 500, and the bottom end fails more often than the top. What the paper supplies, in its words, is “a deterministic polynomial-time construction at the exact threshold and prescribed even order.”
Result 178 is one OpenAI preprint, Deterministic nonbipartite Ramanujan graphs in every fixed degree (85 pages, dated September 23, 2026). Its Theorem 1.1: for every d ≥ 3 there are constants n0(d) and kd and a deterministic algorithm that, on input an even n ≥ n0(d), outputs the adjacency list of a simple d-regular graph G on n vertices in Od(nkd) bit operations, with −2√(d−1) < λ < 2√(d−1) for every eigenvalue λ of AG on the vectors orthogonal to the constant vector. In particular G is connected and nonbipartite. The algorithm certifies the strict bound in exact rational arithmetic.
What it doesn’t claim
That existence is new: the paper credits it to Huang, McKenzie and Yau. No threshold n0(d) or exponent kd is computed, and “it does not assert a running-time bound polynomial jointly in n and d, or a local adjacency-query algorithm.” Only even sizes are covered, even for even degrees, where odd sizes are possible. It does not settle the Bilu–Linial conjecture about two-lifts, and there is no implementation. The paper never says how large n must be; one of the margins in its table grows only like n7.4a with a = 10−4 (up to constant factors), which by our arithmetic is about 1.02 even at n = 1012.
Where it stands
- Posted as a preprint
- OpenAI, 85 pages, dated September 23, 2026
- Peer reviewed
- Not yet
- Checked in Lean
- Not formalized
Last checked October 19, 2026. The preprint has not been revised since it was added to the repository in its initial commit on October 6, 2026. It is not formalized in Lean: the catalogue has no Lean link for this result, and we found no related files in the library. It reports no implementation. Its 85 pages rest on a long chain of estimates with constants chosen in order to be large or small enough. The paper is not among those OSVerify reviewed, and we have seen no expert review.
How the proof goes
- Two signed forms. With s = 2√(d−1), the other eigenvalues lie strictly inside the window exactly when sI − A and sI + A are both positive definite on the vectors orthogonal to the constant vector; the first controls the top of the spectrum and the second the bottom, and the paper tracks both throughout.
- Pairing half-edges without coins. Each vertex gets d half-edges, paired one at a time. A partial pairing still gets a matrix, averaging over the unpaired half-edges, whose inverse counts nonbacktracking walks. At each step it computes exactly how a random pair would change, on average, a polynomial collection of error statistics, then picks the pair with the least weighted total, each statistic discounted by its own growth rate; the best choice is never worse than the average.
- Three stages. It pairs most half-edges, cleans up the few bad ones so that the last ones lie far apart, and completes the graph. The result overshoots the window by less than n−2/3+0.0001/20.
- Repair by switches. A switch replaces edges uv and xy by uy and xv, keeping every degree. About n1/3 disjoint switches are made at once. On average, uniform switching only scales each eigenvalue’s distance from the edge by a factor just below one, so it cannot turn a violation into a pass; the paper tilts the choice of edge pairs using the eigenvectors nearest either edge; “the same law improves both signed forms.” Near-edge eigenvectors spread thinly over the vertices, and around a typical edge the graph’s spectral data match the infinite tree’s.
- No randomness at the end. The draws need only be pairwise independent, which a polynomial family of seeds provides. The algorithm tries every seed (almost all of them work) and tests each graph exactly: BT(4(d−1)I − A2)B ≻ 0, with B a basis of the vectors orthogonal to the constant vector.
The numbers in the video
- Our spectra of small cubic graphs, with the paper’s exact test: the Petersen graph (3, 1, −2) and the dodecahedron pass; the Heawood graph (bipartite, −3) and a prism on 34 vertices (second eigenvalue 2.8649, smallest −2.9659) fail.
- Our simulation of uniformly random cubic graphs (2,000, 8,000 and 1,500 samples at 20, 100 and 500 vertices): both ends inside the window in 0.92, 0.87 and 0.79 of them.
- The paper’s scales with a = 10−4, evaluated by us: at n = 106 the overshoot bound is 5.0 × 10−6 and the number of switches 102; n7.4a is 1.0103 at n = 106 and 1.0207 at n = 1012.
Read the source
- Deterministic nonbipartite Ramanujan graphs in every fixed degree (PDF), 85 pages.
- The collection’s catalog, where this is result 178.
The paper
OpenAI groups related papers into one result; this one has a single paper.
Transcript
Read the full script
0:00The question
In a d-regular graph, every vertex has exactly d neighbours. Its adjacency matrix always has the eigenvalue d, from the constant vector. The other eigenvalues measure how well the graph mixes: the smaller they are in size, the more closely the edges between any two large sets of vertices match an even spread. They cannot all be small. On large graphs, some must come close to two times the square root of d minus one, the spectral radius of the infinite tree in which every vertex has d neighbours. That is the Alon–Boppana bound. A Ramanujan graph meets it exactly: every eigenvalue other than the trivial one lies between minus and plus two root d minus one. The Petersen graph, with three neighbours per vertex, has eigenvalues one and minus two besides three, well inside the window of about ±2.83. A bipartite graph, whose vertices split into two sides with every edge crossing, always has minus d as an eigenvalue, so under this paper’s convention it fails: both ends of the spectrum count. In our computation, a cubic prism on 34 vertices fails at both ends. How do you find such graphs? Lubotzky, Phillips and Sarnak, and Margulis, built them from arithmetic, but only in some degrees and at special sizes; Morgenstern extended the degrees to one more than any prime power. Marcus, Spielman and Srivastava used interlacing polynomials to get bipartite Ramanujan graphs of every degree, where symmetry takes care of the bottom end, and Cohen made their matching construction, which gives bipartite multigraphs, deterministic in polynomial time. Mohanty, O’Donnell and Paredes, and Alon, gave deterministic constructions within any fixed margin of the bound, Alon’s at every large size, leaving a small error. Random regular graphs are nearly Ramanujan, by Friedman’s theorem, and Huang, McKenzie and Yau showed that the chance of being exactly Ramanujan tends to about 69%, so they exist at every large size where dn is even. In our simulation of random cubic graphs, the share is about 87% at 100 vertices and 79% at 500, and the bottom end fails more often than the top. What this paper supplies, in its words, is a deterministic polynomial-time construction at the exact threshold and prescribed even order.
2:31The claim
Result 178 is a single OpenAI preprint, 85 pages long, dated September 23, 2026. Its theorem: for every degree d of at least 3, there is a deterministic algorithm which, given any even number n beyond a threshold that depends on d, outputs the full list of edges of a simple d-regular graph on n vertices, using a number of bit operations polynomial in n, such that every nonconstant eigenvalue lies strictly between minus and plus two root d minus one. In particular the graph is connected and not bipartite. The algorithm checks the strict inequality in exact rational arithmetic, not in floating point. Not claimed: that existence is new; the paper credits it to Huang, McKenzie and Yau. No threshold and no exponent are computed, and the running time is not claimed to be polynomial in the degree. The algorithm outputs the whole graph; it gives no quick way to list one vertex’s neighbours. Only even sizes are covered, even for even degrees, where odd sizes are possible. It does not settle the Bilu–Linial conjecture about two-lifts, and there is no implementation. And the paper never says how large n must be. One of its margins grows only like a tiny power of n, so even at a trillion vertices it is about 1.02.
3:57How the proof goes
The proof starts from a reformulation. Write s for two root d minus one. The other eigenvalues lie strictly inside the window exactly when s minus the adjacency matrix, and s plus it, are both positive definite on vectors orthogonal to the constant vector. One handles the top of the spectrum, the other the bottom, and the paper tracks both throughout. It builds the graph the way a random graph is built: give each vertex d half-edges, and pair them one at a time. For a partial pairing the paper still defines a matrix, averaging over the unpaired half-edges, whose inverse counts nonbacktracking walks, walks that never immediately turn back. No coins are flipped. At each step it computes exactly how a random pair would change, on average, a polynomial collection of error statistics, then picks the pair that minimizes a weighted total, each statistic discounted by its own growth rate. The best choice is never worse than the average. In three stages, it pairs most half-edges, cleans up the few bad ones so that the last ones lie far apart, and completes the graph. The result overshoots the window by at most a sliver: roughly n^(−2/3), divided by twenty. The last stage removes the sliver. A switch replaces two edges, u v and x y, by u y and x v, and every degree stays the same. The algorithm makes about the cube root of n disjoint switches at once. On average, uniform switching only scales each eigenvalue’s distance from the edge by a factor just below one, so it cannot turn a violation into a pass. Instead, the paper tilts the choice of edge pairs, using the few eigenvectors closest to either edge, so that, in its words, the same law improves both signed forms. Two local facts make this work: eigenvectors near the edges spread thinly over the vertices, and around a typical edge, the graph’s spectral data match the infinite tree’s. Finally, randomness is removed again. The draws only need to be pairwise independent, which a family of polynomially many seeds provides. The algorithm tries every seed and tests each resulting graph exactly, checking that four times d minus one, minus the square of the adjacency matrix, is positive definite on vectors orthogonal to the constant vector. In fact almost every seed passes.
6:25Where it stands
The preprint is not peer reviewed and has not been revised. It has no Lean formalization, it reports no implementation, and it is not among the papers OSVerify reviewed; we have seen no expert review. Its 85 pages rest on a long chain of estimates, with constants chosen in order to be large or small enough, and no part of it has been checked by a machine. If it holds, then for every degree, a fixed procedure turns any large even number into a graph of that size whose spectrum meets the Ramanujan bound at both ends, with no randomness and no error term.
Spot a mistake?
This episode simplifies on purpose, but it shouldn’t be wrong. If something is, open an issue on GitHub or leave a comment on YouTube. Corrections are noted here with a date.