Deterministic nonbipartite Ramanujan graphs in every fixed degree
OpenAI research collection · 1 manuscript · Source checked 2026-10-19
OpenAI's result summary
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.
Read the manuscripts
Short excerpts below come from OpenAI's abstracts. The full abstract and original PDF preserve the paper's precise scope.
MANUSCRIPT 01
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…
Full source 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\sqrt{d-1} and 2\sqrt{d-1}.
This exact PDF is not listed in the imported formalization catalogue. Family scope notes may contain further information.
New mathematical reasoning could help AI tackle harder scientific and computational problems. How reliably these skills transfer beyond mathematics will determine how much they contribute to general intelligence.