Deterministic nonbipartite Ramanujan graphs in every fixed degree
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}\).
Cite
@misc{OAI:Deterministic-nonbipartite-Ramanujan-graphs-in-every-fixed-degree-September-23-2026,
author = {{OpenAI}},
title = {{Deterministic nonbipartite Ramanujan graphs in every fixed degree}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/Deterministic-nonbipartite-Ramanujan-graphs-in-every-fixed-degree-September-23-2026/paper.pdf}{OAI:Deterministic-nonbipartite-Ramanujan-graphs-in-every-fixed-degree-September-23-2026}},
year = {2026}
}