Ramanujan graph

• The complete graph ${\displaystyle K_{d+1}}$ has spectrum ${\displaystyle d,-1,-1,\dots ,-1}$, and thus ${\displaystyle \lambda (K_{d+1})=1}$ and the graph is a Ramanujan graph for every ${\displaystyle d>1}$. The complete bipartite graph ${\displaystyle K_{d,d}}$ has spectrum ${\displaystyle d,0,0,\dots ,0,-d}$ and hence is a bipartite Ramanujan graph for every ${\displaystyle d}$.
• The Petersen graph has spectrum ${\displaystyle 3,1,1,1,1,1,-2,-2,-2,-2}$, so it is a 3-regular Ramanujan graph. The icosahedral graph is a 5-regular Ramanujan graph.[4]
• A Paley graph of order ${\displaystyle q}$ is ${\displaystyle {\frac {q-1}{2}}}$-regular with all other eigenvalues being ${\displaystyle {\frac {-1\pm {\sqrt {q}}}{2}}}$, making Paley graphs an infinite family of Ramanujan graphs.
• More generally, let ${\displaystyle f(x)}$ be a degree 2 or 3 polynomial over ${\displaystyle \mathbb {F} _{q}}$. Let ${\displaystyle S=\{f(x)\,:\,x\in \mathbb {F} _{q}\}}$ be the image of ${\displaystyle f(x)}$ as a multiset, and suppose ${\displaystyle S=-S}$. Then the Cayley graph for ${\displaystyle \mathbb {F} _{q}}$ with generators from ${\displaystyle S}$ is a Ramanujan graph.

Mathematicians are often interested in constructing infinite families of ${\displaystyle d}$-regular Ramanujan graphs for every fixed ${\displaystyle d}$. Such families are useful in applications.

Several explicit constructions of Ramanujan graphs arise as Cayley graphs and are algebraic in nature. See Winnie Li's survey on Ramanujan's conjecture and other aspects of number theory relevant to these results.[5]

Lubotzky, Phillips and Sarnak[2] and independently Margulis[6] showed how to construct an infinite family of ${\displaystyle (p+1)}$-regular Ramanujan graphs, whenever ${\displaystyle p}$ is a prime number and ${\displaystyle p\equiv 1{\pmod {4}}}$. Both proofs use the Ramanujan conjecture, which led to the name of Ramanujan graphs. Besides being Ramanujan graphs, these constructions satisfies some other properties, for example, their girth is ${\displaystyle \Omega (\log _{p}(n))}$ where ${\displaystyle n}$ is the number of nodes.

Let us sketch the Lubotzky-Phillips-Sarnak construction. Let ${\displaystyle q\equiv 1{\bmod {4}}}$ be a prime not equal to ${\displaystyle p}$. By Jacobi's four-square theorem, there are ${\displaystyle p+1}$ solutions to the equation ${\displaystyle p=a_{0}^{2}+a_{1}^{2}+a_{2}^{2}+a_{3}^{2}}$ where ${\displaystyle a_{0}>0}$ is odd and ${\displaystyle a_{1},a_{2},a_{3}}$ are even. To each such solution associate the ${\displaystyle \operatorname {PGL} (2,\mathbb {Z} /q\mathbb {Z} )}$ matrix

$${\displaystyle {\tilde {\alpha }}={\begin{pmatrix}a_{0}+ia_{1}&a_{2}+ia_{3}\\-a_{2}+ia_{3}&a_{0}-ia_{1}\end{pmatrix}},\qquad i{\text{ a fixed solution to }}i^{2}=-1{\bmod {q}}.}$$

If ${\displaystyle p}$ is not a quadratic residue modulo ${\displaystyle q}$ let ${\displaystyle X^{p,q}}$ be the Cayley graph of ${\displaystyle \operatorname {PGL} (2,\mathbb {Z} /q\mathbb {Z} )}$ with these ${\displaystyle p+1}$ generators, and otherwise, let ${\displaystyle X^{p,q}}$ be the Cayley graph of ${\displaystyle \operatorname {PSL} (2,\mathbb {Z} /q\mathbb {Z} )}$ with the same generators. Then ${\displaystyle X^{p,q}}$ is a ${\displaystyle (p+1)}$-regular graph on ${\displaystyle n=q(q^{2}-1)}$ or ${\displaystyle q(q^{2}-1)/2}$ vertices depending on whether or not ${\displaystyle p}$ is a quadratic residue modulo ${\displaystyle q}$. It is proved that ${\displaystyle X^{p,q}}$ is a Ramanujan graph.

Morgenstern[7] later extended the construction of Lubotzky, Phillips and Sarnak. His extended construction holds whenever ${\displaystyle p}$ is a prime power.

Arnold Pizer proved that the supersingular isogeny graphs are Ramanujan, although they tend to have lower girth than the graphs of Lubotzky, Phillips, and Sarnak.[8] Like the graphs of Lubotzky, Phillips, and Sarnak, the degrees of these graphs are always a prime number plus one.

Adam Marcus, Daniel Spielman and Nikhil Srivastava[9] proved the existence of infinitely many ${\displaystyle d}$-regular bipartite Ramanujan graphs for any ${\displaystyle d\geq 3}$. Later[10] they proved that there exist bipartite Ramanujan graphs of every degree and every number of vertices. Michael B. Cohen[11] showed how to construct these graphs in polynomial time.

The initial work followed an approach of Bilu and Linial. They considered an operation called a 2-lift that takes a ${\displaystyle d}$-regular graph ${\displaystyle G}$ with ${\displaystyle n}$ vertices and a sign on each edge, and produces a new ${\displaystyle d}$-regular graph ${\displaystyle G'}$ on ${\displaystyle 2n}$ vertices. Bilu & Linial conjectured that there always exists a signing so that every new eigenvalue of ${\displaystyle G'}$ has magnitude at most ${\displaystyle 2{\sqrt {d-1}}}$. This conjecture guarantees the existence of Ramanujan graphs with degree ${\displaystyle d}$ and ${\displaystyle 2^{k}(d+1)}$ vertices for any ${\displaystyle k}$—simply start with the complete graph ${\displaystyle K_{d+1}}$, and iteratively take 2-lifts that retain the Ramanujan property.

Using the method of interlacing polynomials, Marcus, Spielman, and Srivastava[9] proved Bilu & Linial's conjecture holds when ${\displaystyle G}$ is already a bipartite Ramanujan graph, which is enough to conclude the existence result. The sequel[10] proved the stronger statement that a sum of ${\displaystyle d}$ random bipartite matchings is Ramanujan with non-vanishing probability.

It is still an open problem whether there are infinitely many ${\displaystyle d}$-regular (non-bipartite) Ramanujan graphs for any ${\displaystyle d\geq 3}$. In particular, the problem is open for ${\displaystyle d=7}$, the smallest case for which ${\displaystyle d-1}$ is not a prime power and hence not covered by Morgenstern's construction.

Confirming a conjecture of Alon, Friedman[12] showed that many families of random graphs are weakly-Ramanujan. This means that for every ${\displaystyle d}$ and ${\displaystyle \epsilon >0}$ and for sufficiently large ${\displaystyle n}$, a random ${\displaystyle d}$-regular ${\displaystyle n}$-vertex graph ${\displaystyle G}$ satisfies ${\displaystyle \lambda (G)<2{\sqrt {d-1}}+\epsilon }$ with high probability. While this result shows that random graphs are close to being Ramanujan, it cannot be used to prove the existence of Ramanujan graphs. It is conjectured,[13] though, that random graphs are Ramanujan with substantial probability (roughly 52%). In addition to direct numerical evidence, there is some theoretical support for this conjecture: the spectral gap of a ${\displaystyle d}$-regular graph seems to behave according to a Tracy-Widom distribution from random matrix theory, which would predict the same asymptotic.