Deterministic nonbipartite Ramanujan graphs in every fixed degree

OpenAI groups related papers into a “family”. OpenAI’s catalogue describes this one:

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.

The release has no Lean statement for this family, so there is no formal statement to compare with the result described above.

What the papers state

Theorem 1.1

In Deterministic nonbipartite Ramanujan graphs in every fixed degree, 23 September 2026

Possible match to OpenAI’s description, selected from shared wording. No review confirming the selection is recorded.

For every integer d\ge3 there are constants n_0(d) and k_d and a deterministic algorithm with the following property. On input an even integer n\ge n_0(d), the algorithm outputs the adjacency list of a simple d-regular graph G on n vertices in O_d(n^{k_d}) bit operations, and

-2\sqrt{d-1}<\lambda<2\sqrt{d-1} \quad\text{for every eigenvalue $\lambda$ of }A_G|_{\mathbf1^\perp}.

In particular, G is connected and nonbipartite.

Corollary 1.2

In Deterministic nonbipartite Ramanujan graphs in every fixed degree, 23 September 2026

Possible match to OpenAI’s description, selected from shared wording. No review confirming the selection is recorded.

For every fixed d\ge3, a deterministic polynomial-time algorithm, on every sufficiently large integer input N, produces a simple connected nonbipartite d-regular Ramanujan graph G with N\le |V(G)|\le N+1\le2N.

The release does not say which paper theorem its catalogue describes. The statements above share the most wording with the description; the atlas has not reviewed that choice. Identifying it is listed under Questions awaiting review.

Reported proof verification: The release has no Lean statement for this family. The papers are available to read and assess.
Papers and explanations: One current paper, readable here as a page beside its PDF.

Papers

Each paper opens as a reading page in the browser, with the PDF beside it. The statements each paper opens with are on its reading page.

Deterministic nonbipartite Ramanujan graphs in every fixed degree

23 September 2026, current edition.

Read it here 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}$.

Lean statements

The release has no Lean statement for this family. Its papers remain available to read, and contributors can propose a formal statement of a result. Suggest a change

Independent comparisons and proof-verification reports

Does the Lean express the advertised result?

The release contains no Lean statement for this family, so there is no formal statement to compare with OpenAI’s description.

What these papers cite in the release, and what cites them

These links come from the papers’ bibliographies. A citation records that one paper cites another; how each cited result is used has not been examined here.

Papers elsewhere in the release that this family’s papers cite

This family’s papers cite no paper elsewhere in the release.

Papers elsewhere in the release that cite this family’s papers

No paper elsewhere in the release cites this family’s papers.

References outside the release

Each paper’s outside references are listed with it on its reading page, where each citation is placed. Every outside work cited in the release: References outside the release

29 references in Deterministic nonbipartite Ramanujan graphs in every fixed degree

Explain a result, compare statements or propose a correction

Atlas has no contributed explanation for this family yet. You can offer one with a GitHub account. You receive named credit and disclose any AI assistance.

Each button opens a GitHub form with this page and its source version filled in. Opening the form does not reserve the work.

Offer to write an explanation Suggest a source attribution Suggest a change

What people have said

Commentary on this family by others, dated and credited. It is commentary, not a finding.

An unsigned public tier list, the OpenAI Math Tier List, classes it as a construction and rates its significance, if it holds up, as “Career-defining publication”. The page says that nothing on it is verified.
Author not stated. Source

Laura Monk, Comment on the deterministic Ramanujan graphs manuscript, 7 October 2026. Source
A specialist reports that the paper gives a low-complexity deterministic algorithm rather than the construction its title suggests, notes that a trivial deterministic search already works at poor complexity, and observes that it has 85 pages and no Lean.

Lean community, OpenAI releases solutions to hundreds of problems (117 messages, 6-10 Oct 2026), 6 October 2026. Source
Laura Monk: the Ramanujan graphs manuscript is 85 pages, has no Lean, and is a big oversell relative to its title.

Questions awaiting review

Each item identifies a statement, definition or report that needs further review. Its link opens a GitHub form with the source version already recorded.

Identify the theorem the catalogue describes

Family 178 No single paper statement clearly matches OpenAI’s description by wording, and no review identifying the intended theorem is recorded. Open the form

State the result in Lean

Family 178 The release has no Lean statement for this family. Open the form