In September 2026, OpenAI released a preprint (OpenAI 2026) announcing a deterministic polynomial-time algorithm for constructing Ramanujan graphs of every fixed degree. The result addresses a fundamental problem concerning expander graphs, which are simultaneously sparse and highly connected.
We have discussed expander graphs in this blog several times, including an earlier post about Avi Wigderson’s talk on expanders and a post on the eigenvalues of random regular graphs.
Let us recall the basic definitions.
A graph is called -regular if every vertex has exactly neighbours. An expander graph is, informally, a graph in which every sufficiently small set of vertices has many edges connecting it to the rest of the graph.
What makes expanders remarkable is that they can have very few edges relative to the number of vertices, yet remain highly connected. This combination makes them useful in theoretical computer science, particularly in the construction of error-correcting codes, pseudorandom generators, and efficient algorithms.
An important way to measure the expansion properties of a graph is through its eigenvalues.
Let be a graph with vertices . Its adjacency matrix is the matrix , where The matrix is symmetric and therefore has real eigenvalues, which we denote by
Recall that a number is an eigenvalue of a matrix if there exists a nonzero vector such that .
If is -regular, then , because every row of its adjacency matrix contains exactly ones. The corresponding eigenvector is the vector whose coordinates are all equal to .
The remaining eigenvalues contain important information about the graph’s expansion properties. In particular, the smaller is relative to , the better the graph’s edge expansion.
However, there is a fundamental limitation on how small these eigenvalues can be. The Alon–Boppana bound states that, for every fixed , any sequence of -regular graphs with an increasing number of vertices satisfies where denotes a quantity tending to zero as the number of vertices tends to infinity.
This makes a natural threshold.
A connected, non-bipartite -regular graph is called Ramanujan if all its eigenvalues other than satisfy Thus, Ramanujan graphs have essentially the best possible spectral expansion properties for their degree.
Constructing such graphs is a difficult problem.
The first explicit infinite families of Ramanujan graphs were constructed in the 1980s by Lubotzky, Phillips, and Sarnak (Lubotzky et al. 1988), and independently by Margulis. However, their constructions worked only for certain degrees.
In 2015, Marcus, Spielman, and Srivastava (Marcus et al. 2015) proved that infinite families of bipartite Ramanujan graphs exist for every degree . Their proof introduced the powerful method of interlacing polynomials, which has since found numerous applications.
A graph is called bipartite if its vertices can be divided into two groups so that every edge joins vertices from different groups. Every bipartite -regular graph has the eigenvalue , in addition to . Consequently, the definition of a bipartite Ramanujan graph excludes both these trivial eigenvalues from the spectral bound.
For non-bipartite graphs, the existence problem remained open for many years.
In 2024, Huang, McKenzie, and Yau (Huang et al. 2024) established a remarkable result concerning random regular graphs. They proved that, for every fixed , approximately of all sufficiently large -regular graphs are Ramanujan.
Thus, Ramanujan graphs are surprisingly common! However, knowing that a randomly selected graph is likely to have the desired property does not automatically give us a deterministic way to construct one efficiently.
An important earlier result of Alon (Alon 2021) gave deterministic constructions for every fixed degree and sufficiently large admissible order with the slightly weaker spectral bound where is any prescribed constant.
The remaining challenge was to remove the extra and obtain the exact Ramanujan threshold, deterministically and in polynomial time.
The new OpenAI preprint (OpenAI 2026) claims to accomplish this.
Here simple means that the graph has no loops or multiple edges.
For example, taking , the theorem guarantees that for every sufficiently large even , we can construct a simple -regular graph on exactly vertices whose nontrivial eigenvalues all lie strictly between
Notice that the theorem guarantees more than the usual Ramanujan property: the inequalities are strict.
They also imply that the resulting graph is connected and non-bipartite. Indeed, a disconnected -regular graph would have as an eigenvalue more than once, while a bipartite -regular graph would have the eigenvalue . Both possibilities are excluded because
Let us briefly discuss the proof.
The authors begin by constructing a nearly Ramanujan graph, whose eigenvalues are allowed to exceed the desired bounds by a very small amount. They do this by gradually pairing the ends of edges, choosing each new connection deterministically while maintaining a collection of spectral estimates.
The method is related to the classical method of conditional expectations, which converts suitable probabilistic existence arguments into deterministic algorithms.
The most difficult step is then to remove the remaining spectral error. The authors achieve this through carefully chosen edge switches. Such a switch removes two edges joining four distinct vertices and replaces them with two different edges, without changing the degree of any vertex.
By analyzing how these modifications affect the eigenvalues near both ends of the spectrum, the authors show that a suitable collection of switches moves all the remaining eigenvalues strictly inside the required interval.
The construction is algorithmic throughout. In particular, the final spectral condition can be checked using exact matrix computations, without relying on numerical approximations to eigenvalues.
There is an important qualification: although the running time is polynomial in for every fixed degree , the theorem does not claim a running time polynomial jointly in and . The constants involved may also be extremely large, so this is primarily a theoretical breakthrough rather than an immediately practical algorithm.
The result is currently available as a preprint, and independent verification of its proof remains important.
If confirmed, it will complete a remarkable sequence of developments: from the first explicit Ramanujan graphs in special degrees, to the existence of bipartite Ramanujan graphs in every degree, to the discovery that most random regular graphs are Ramanujan, and finally to their deterministic construction at essentially every sufficiently large prescribed size.
The conclusion is particularly striking: graphs with almost optimal spectral expansion are not merely abundant—they can be constructed efficiently, without using any randomness at all.