Deterministic nonbipartite Ramanujan graphs in every fixed degree

What OpenAI claims

For every fixed d ≥ 3, constructs a simple d-regular nonbipartite Ramanujan graph on every sufficiently large even number n of vertices, with every nonconstant adjacency eigenvalue strictly between -2√(d-1) and 2√(d-1). A deterministic algorithm outputs the full adjacency list in polynomial bit time, with exponent depending on d.

Paper

1. Deterministic nonbipartite Ramanujan graphs in every fixed degree

   23 September 2026 · Preprint, not peer reviewed · PDF

   OpenAI's abstract For every fixed integer d ≥ 3, we give a deterministic algorithm that constructs a simple nonbipartite d-regular Ramanujan graph on every sufficiently large even number n of vertices. It outputs the full adjacency list in polynomially many bit operations, with an exponent that may depend on d. Every nonconstant adjacency eigenvalue lies strictly between -2√(d-1) and 2√(d-1).

Status

Preprint. The paper has not been independently reviewed. Treat the result as OpenAI's claim until other mathematicians have checked it. If a video exists, it illustrates the statement; it is not the proof.