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\sqrt{d-1} and 2\sqrt{d-1}. A deterministic algorithm outputs the full adjacency list in polynomial bit time, with exponent depending on d.
Manuscript
Deterministic nonbipartite Ramanujan graphs in every fixed degree
September 23, 2026 · source · cite as \cite{OAI:Deterministic-nonbipartite-Ramanujan-graphs-in-every-fixed-degree-September-23-2026}
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\sqrt{d-1} and 2\sqrt{d-1}.
Result 178 · Combinatorics. Imported from openai/math, a collection of manuscripts produced by an OpenAI model; results are at different stages of verification. Discussion below is by Lemma members.
Source: https://github.com/openai/math/blob/main/CONTENTS.md