Browse › Combinatorics › 178 Deterministic nonbipartite Ramanujan graphs in every fixed degree
Deterministic nonbipartite Ramanujan graphs in every fixed degree
Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion
Edit NOTES.md · Existing issues · Source on GitHub
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}$.
If the PDF does not display here, open it directly: Open PDF.
Notes
No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.
Automatically collected notes (unreviewed)
work in progress
Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.
Follow-up works
- Lermont, Benchmark spectral topology selection for P2P broadcast and audit family 178 feasibility (GitHub pull request to Lermont/math, merged 2026-10-11). A simulation experiment motivated by family 178 that compares random regular graphs, a selection heuristic and an LPS Ramanujan graph for peer-to-peer flooding; the PR says "the full deterministic construction from family 178 is not implemented or benchmarked."
Comments and discussion
- Malt7635 (GitHub handle), Flaw report: Deterministic nonbipartite Ramanujan graphs in every fixed degree (GitHub Gist, 2026-10-10). This public report alleges that the asserted scale of $J_T$ in Step 2 of Theorem 8.3 conflicts with its local spectral-mass hypothesis, affecting the probability law used for exact spectral repair.
Related prior literature mentioned by others
- Gil Kalai, New Ramanujan Graphs! (blog post, Combinatorics and more, 2013-05-01). Kalai's October 2026 post links this earlier account of the Marcus–Spielman–Srivastava bipartite Ramanujan graphs of all degrees, interlacing polynomials and the Bilu–Linial lifting conjecture as background to this paper's nonbipartite construction.
Possibly relevant literature (found by the agent, not checked)
- Jiaoyang Huang, Theo McKenzie, Horng-Tzer Yau, Optimal Eigenvalue Rigidity of Random Regular Graphs (arXiv:2405.12161, May 2024). Shows that the extreme eigenvalues of random d-regular graphs (fixed d ≥ 3) fluctuate on the scale N^{-2/3+o(1)}, the same scale as the paper's repair window e = n^{-2/3+a}; the paper cites the companion works arXiv:2412.20263 and Huang–Yau, but not this one.
- Chi-Fang Chen, Jorge Garza-Vargas, Joel A. Tropp, Ramon van Handel, A new approach to strong convergence (arXiv:2405.16026; Annals of Mathematics 203(2), 2026). Gives another short proof of Friedman's near-optimal spectral gap for random regular graphs, which the paper's introduction discusses through Friedman (2008) and Bordenave (2020).
Digests and expositions
- AI Proved What?, Ramanujan graphs, made to order? (Episode 178, October 2026). This illustrated exposition summarizes the prescribed-order claim, the pairing and switching stages, the exact positivity certificate, and distinctions from earlier existence and near-Ramanujan results. [AI-generated per source]
Elsewhere
- VibeMathed: Problem record
- Emergent Mind: family 178
Independent sites; their content is not reviewed here.
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}
}Family 178: 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.
This is the only paper in this family.