Deterministic nonbipartite Ramanujan graphs in every fixed degree

The explanation

Take the Petersen graph: ten points, each joined to exactly three others, fifteen links in all. Write its links as a 10-by-10 table of 0s and 1s. That table has ten special numbers called eigenvalues. Roughly, they describe how a signal spreads through the network. The largest is always 3, the number of links at each point. For Petersen the other nine are 1, five times, and −2, four times.

Those other nine numbers measure mixing. When all of them are small, links spread out evenly, with no hidden bottleneck or clumpSource 1. How small can they be? For networks with d links at each point, the best possible cutoff for large networks is 2√(d − 1)Source 2. For d = 3 that is about 2.83. Networks whose other eigenvalues all stay inside −2.83 to 2.83 are called Ramanujan graphs. Petersen qualifies, since 1 and −2 both fit.

The negative side matters too. A cube's corners and edges form another network with three links per point. Its eigenvalues are 3, then 1 and −1 three times each, then −3. The −3 shows that the cube is bipartite: its points split into two teams, and every link joins the two teams. Bipartite networks always break the negative side. A network that meets both sides of the cutoff is connected and not bipartiteSource 3.

Building large Ramanujan graphs on purpose has been hard. In the 1980s, Lubotzky, Phillips and Sarnak, and separately Margulis, used number theory to build themSource 4. Those methods work only for special degrees. Morgenstern extended them to every degree one more than a prime power, including non-bipartite onesSource 5. But they never covered every degree and every large size at onceSource 6. In 2015, Marcus, Spielman and Srivastava built bipartite Ramanujan graphs in every degreeSource 7. Bipartite graphs get the negative side for free by symmetry. Other fast constructions in every degree allowed a small extra error above the cutoffSource 8.

Random networks almost work. A random network with d links per point nearly meets the cutoff, with probability tending to oneSource 9. It meets the exact cutoff about 69 percent of the time in the limitSource 10. So such graphs exist. But a random draw needs a check, and the method gives no fixed recipe.

This paper claims a fixed recipeSource 11. For every degree d of at least 3, an algorithm takes any large enough even number n. It outputs a network with n points and d links per point. Every eigenvalue other than d lies strictly inside the cutoff on both sides. The running time grows like a power of n, but that power may depend on d. The result covers only large even sizes, and it does not claim a speed that is also polynomial in dSource 12.

The single difficulty is precision. Getting within a small error of the cutoff was already possible. Removing that error means controlling eigenvalues on a far finer scale, near both ends of the range at onceSource 13. The main tool is an edge switchSource 14. It deletes two links and adds two new ones on the same four points, so every point keeps its d links. But knowing only the overall size of the eigenvalues does not tell how one switch moves themSource 15. So the construction tracks extra local information at each point, and makes only switches whose effect it can predict.

The paper also says what it does not do. A related question, the Bilu–Linial conjecture, asks about doubling any network with a sign on each link. This construction does not settle itSource 16.

How sure is this? The paper has no Lean formalization listed. The theorem is a claim in a long preprint, and no specialist review of it has been published.

What it doesn't show. This does not give a running time that stays polynomial as the degree grows.