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}$.
Comments and reviews
No comments yet.
Discussed elsewhere
API
curl /api/v1/records/openai-math/Deterministic-nonbipartite-Ramanujan-graphs-in-every-fixed-degree
curl -X POST /api/v1/records/openai-math/Deterministic-nonbipartite-Ramanujan-graphs-in-every-fixed-degree/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/openai-math/Deterministic-nonbipartite-Ramanujan-graphs-in-every-fixed-degree/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'
Updates: Sharing AI progress on mathematics (amazing!); and my lecture plansCombinatorics and moreOct 7, 2026
a deterministic polynomial-time construction of nonbipartite Ramanujan graphs, for every fixed degree at least three and every sufficiently large even number of vertices. In higher dimensions, the release announces bounded-vertex-degree coboundary expanders over in every dimension at least three,…