1 · The essentials
The manuscript describes a way to build networks in which every point has exactly the same chosen number of neighbors. That number can be any fixed whole number of at least three. The construction is claimed to work for every sufficiently large even number of points, not merely for a selected sequence of sizes. No point is linked to itself, and no pair of points has more than one link. The network cannot be divided into two groups with all links running between the groups. Its connection pattern also satisfies strict mathematical bounds that make it a Ramanujan graph. The algorithm makes no random choices and outputs the complete list of neighbors in polynomial time for each fixed degree. This result is claimed in the manuscript; it is not formalized in Lean and has not been formally verified.
A picture to help (an imperfect image, not to be taken literally)
As an imperfect image, imagine arranging direct contacts among people so that everyone has exactly the same number of contacts. The manuscript claims a fixed procedure for making such an arrangement for every sufficiently large even group size, with additional mathematical restrictions on the overall pattern. The image illustrates equal numbers of neighbors, but not the spectral bounds at the heart of the result.
Why it matters
The claim combines control over the degree, the size, and the spectrum with a deterministic construction. It also specifies that the algorithm outputs the full adjacency list, rather than merely asserting that a suitable graph exists. The running-time guarantee is for each fixed degree, with an exponent that may depend on that degree.
2 · Going further
The precise claim is that, for every fixed integer , a deterministic algorithm constructs a simple, nonbipartite, -regular Ramanujan graph on every sufficiently large even number of vertices. Here, -regular means that each vertex has exactly neighbors, and simple means that there are no loops or multiple edges. Nonbipartite means that the vertices cannot be split into two classes with every edge crossing between them.
The spectral requirement is strict: every nonconstant adjacency eigenvalue satisfies . These eigenvalues describe the action of the adjacency matrix on nonconstant patterns of values assigned to vertices. The claimed construction therefore avoids both boundary values, rather than merely allowing equality at the Ramanujan bounds.
The algorithm outputs the full adjacency list using polynomially many bit operations, with a polynomial exponent that may depend on . The supplied abstract states this guarantee but does not describe the construction or the main idea of its argument. Only the main manuscript is supplied, so no relationship to companion manuscripts can be described from this source.
Useful notions
- Vertices, edges, and neighbors
- Regular and bipartite graphs
- Adjacency matrices and eigenvalues
- Deterministic algorithms
- Polynomial bit complexity
What was known before / what is new
Before
The supplied text does not describe earlier constructions or establish what was previously known. It gives no historical comparison or named open problem, so it does not support a more specific account of the prior state of the subject.
New
The manuscript presents a deterministic construction for every fixed degree and every sufficiently large even number of vertices. Its stated guarantees combine simplicity, nonbipartiteness, strict Ramanujan spectral bounds, and full adjacency-list output in polynomial bit time. The abstract does not provide enough context to assess priority beyond this stated contribution.
Limits and assumptions
The degree must be a fixed integer at least three, and the size guarantee covers only sufficiently large even numbers of vertices. The supplied text gives no explicit size threshold and makes no guarantee for odd sizes or smaller even sizes. The polynomial running-time exponent may depend on the degree; no degree-independent exponent is stated. The abstract does not supply argument details or identify remaining open problems. The main result is not formalized in Lean and has not been formally verified.
Mini glossary
- Simple graph —
- A graph with no edge from a vertex to itself and no multiple edges between a pair of vertices.
- Degree —
- In a simple graph, the degree of a vertex is its number of neighbors.
- Nonbipartite graph —
- A graph whose vertices cannot be divided into two classes so that every edge joins different classes.
- Adjacency eigenvalue —
- A number by which the adjacency matrix scales a corresponding nonzero pattern of values on the vertices.
- Adjacency list —
- A representation of a graph that lists the neighbors of each vertex.
- Polynomial bit time —
- A running-time bound counting bit operations that grows at most polynomially with the size parameter, here for each fixed .
Keywords : Ramanujan graphs · Deterministic construction · Spectral bounds
AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.
3 · Technical details and sources
Claim made in the manuscript (source text)
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 and . A deterministic algorithm outputs the full adjacency list in polynomial bit time, with exponent depending on d.
To be verified: the proof is written in the manuscript, but no software has checked it and no validation by independent mathematicians is established. It may contain errors.
Manuscripts in this family
Deterministic nonbipartite Ramanujan graphs in every fixed degree
23/09/2026For 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 and .