{"id":"openai-math/Deterministic-nonbipartite-Ramanujan-graphs-in-every-fixed-degree","pdf":"https://github.com/openai/math/blob/main/preprints/Deterministic-nonbipartite-Ramanujan-graphs-in-every-fixed-degree-September-23-2026/paper.pdf","url":"https://github.com/openai/math/tree/main/preprints/Deterministic-nonbipartite-Ramanujan-graphs-in-every-fixed-degree-September-23-2026","tags":["spectral-graph-theory","expanders","graph-theory"],"score":0,"title":"Deterministic nonbipartite Ramanujan graphs in every fixed degree","domain":"Combinatorics","family":"178","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"math.CO","summary":"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}`$.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":1,"published":"2026-09-23","reactions":{},"discussion":[{"url":"https://gilkalai.wordpress.com/2026/10/07/updates-sharing-ai-progress-on-mathematics-amazing-and-my-lecture-plans/#:~:text=a%20deterministic%20polynomial-time%20construction%20of%20nonbipartite%20Ramanujan%20graphs","date":"2026-10-07","kind":"web","site":"Combinatorics and more","text":"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,…","added":"2026-10-24","title":"Updates: Sharing AI progress on mathematics (amazing!); and my lecture plans"}],"formalized":false,"family_title":"Deterministic nonbipartite Ramanujan graphs in every fixed degree"}