Family 178CombinatoricsNo LeanNot yet digested

Deterministic nonbipartite Ramanujan graphs in every fixed degree

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.

Manuscripts in this family · 1

Deterministic nonbipartite Ramanujan graphs in every fixed degree

Sep 23, 2026·paper.pdf

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}

Full abstract

PDF on GitHub LaTeX source