Editing Ramanujan graph (section)

== Examples and constructions ==

=== Explicit examples ===

* The [[complete graph]] <math>K_{d+1}</math> has spectrum <math>d, -1, -1, \dots, -1</math>, and thus <math>\lambda(K_{d+1}) = 1</math> and the graph is a Ramanujan graph for every <math>d > 1</math>. The [[complete bipartite graph]] <math>K_{d,d}</math> has spectrum <math>d, 0, 0, \dots, 0, -d</math> and hence is a bipartite Ramanujan graph for every <math>d</math>.
* The [[Petersen graph]] has spectrum <math>3, 1, 1, 1, 1, 1, -2, -2, -2, -2</math>, so it is a 3-regular Ramanujan graph. The [[Regular icosahedron|icosahedral graph]] is a 5-regular Ramanujan graph.<ref>{{Cite web|last=Weisstein|first=Eric W.|title=Icosahedral Graph|url=http://mathworld.wolfram.com/IcosahedralGraph.html|access-date=2019-11-29|website=mathworld.wolfram.com|language=en}}</ref>
* A [[Paley graph]] of order <math>q</math> is <math>\frac{q-1}{2}</math>-regular with all other eigenvalues being <math>\frac{-1\pm\sqrt{q}}{2}</math>, making Paley graphs an infinite family of Ramanujan graphs.
* More generally, let <math>f(x)</math> be a degree 2 or 3 polynomial over <math>\mathbb{F}_q</math>. Let <math>S = \{f(x)\, :\, x \in \mathbb{F}_q\}</math> be the image of <math>f(x)</math> as a multiset, and suppose <math>S = -S</math>. Then the [[Cayley graph]] for <math>\mathbb{F}_q</math> with generators from <math>S</math> is a Ramanujan graph.

Mathematicians are often interested in constructing infinite families of <math>d</math>-regular Ramanujan graphs for every fixed <math>d</math>. Such families are useful in applications.

=== Algebraic constructions ===
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.<ref>{{Cite journal|last=Li|first=Winnie|title=The Ramanujan conjecture and its applications|url=https://doi.org/10.1098/rsta.2018.0441|journal=Philosophical Transactions of the Royal Society A|year=2020|volume=378-2163|issue=2163|doi=10.1098/rsta.2018.0441| pmc=6939229|pmid=31813366|bibcode=2020RSPTA.37880441W}}</ref>

[[Alexander Lubotzky|Lubotzky]], [[Ralph S. Phillips|Phillips]] and [[Peter Sarnak|Sarnak]]<ref name="lps88" /> and independently [[Grigory Margulis|Margulis]]<ref>{{Cite journal|last=Margulis|first=G. A.|date=1988|title=Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators|url=http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=ppi&paperid=686&option_lang=eng|journal=Probl. Peredachi Inf.|volume=24-1|pages=51–60}}</ref> showed how to construct an infinite family of <math>(p+1)</math>-regular Ramanujan graphs, whenever <math>p</math> is a [[prime number]] and <math>p\equiv 1 \pmod 4</math>. 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 (graph theory)|girth]] is <math>\Omega(\log_{p}(n))</math> where <math>n</math> is the number of nodes.

Let us sketch the Lubotzky-Phillips-Sarnak construction. Let <math>q \equiv 1 \bmod 4</math> be a prime not equal to <math>p</math>. By [[Jacobi's four-square theorem]], there are <math>p+1</math> solutions to the equation <math>p=a_0^2+a_1^2+a_2^2+a_3^2</math> where <math>a_0 > 0</math> is odd and <math>a_1, a_2, a_3</math> are even. To each such solution associate the <math>\operatorname{PGL}(2,\Z/q\Z)</math> matrix <math display="block">\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.</math>If <math>p
</math> is not a quadratic residue modulo <math>q</math> let <math>X^{p,q}</math> be the Cayley graph of <math>\operatorname{PGL}(2,\Z/q\Z)</math> with these <math>p+1</math> generators, and otherwise, let <math>X^{p,q}</math> be the Cayley graph of <math>\operatorname{PSL}(2,\Z/q\Z)</math> with the same generators. Then <math>X^{p,q}</math> is a <math>(p+1)</math>-regular graph on <math>n=q(q^2-1)</math> or <math>q(q^2-1)/2</math> vertices depending on whether or not  <math>p
</math> is a quadratic residue modulo <math>q</math>. It is proved that <math>X^{p,q}</math> is a Ramanujan graph.

Morgenstern<ref name="m94">{{cite journal|author=Moshe Morgenstern|year=1994|title=Existence and Explicit Constructions of q+1 Regular Ramanujan Graphs for Every Prime Power q|journal=[[Journal of Combinatorial Theory]] | series=Series B|volume=62|pages=44–62|doi=10.1006/jctb.1994.1054|doi-access=free}}</ref> later extended the construction of Lubotzky, Phillips and Sarnak. His extended construction holds whenever <math>p</math> is a [[prime power]].

Arnold Pizer proved that the [[supersingular isogeny graph]]s are Ramanujan, although they tend to have lower girth than the graphs of Lubotzky, Phillips, and Sarnak.<ref>{{citation|last=Pizer|first=Arnold K.|title=Ramanujan graphs and Hecke operators|journal=Bulletin of the American Mathematical Society|volume=23|issue=1|pages=127–137|year=1990|series=New Series|doi=10.1090/S0273-0979-1990-15918-X|mr=1027904|doi-access=free}}</ref> Like the graphs of Lubotzky, Phillips, and Sarnak, the degrees of these graphs are always a prime number plus one.

=== Probabilistic examples ===
[[Adam Marcus (mathematician)|Adam Marcus]], [[Daniel Spielman]] and [[Nikhil Srivastava]]<ref name="mss13">{{cite conference|author=Adam Marcus|author1-link=Adam Marcus (mathematician)|author2=Daniel Spielman|author2-link=Daniel Spielman|author3=Nikhil Srivastava|author3-link=Nikhil Srivastava|year=2013|title=Interlacing families I: Bipartite Ramanujan graphs of all degrees|url=https://annals.math.princeton.edu/wp-content/uploads/Marcus_Spielman_SrivastavaIFI.pdf|conference=Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium}}</ref> proved the existence of infinitely many <math>d</math>-regular ''bipartite'' Ramanujan graphs for any <math>d\geq 3</math>. Later<ref name="mss15">{{cite conference|author=Adam Marcus|author1-link=Adam Marcus (mathematician)|author2=Daniel Spielman|author2-link=Daniel Spielman|author3=Nikhil Srivastava|author3-link=Nikhil Srivastava|year=2015|title=Interlacing families IV: Bipartite Ramanujan graphs of all sizes|url=https://www.cs.yale.edu/homes/spielman/PAPERS/IF4.pdf|conference=Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium}}</ref> they proved that there exist bipartite Ramanujan graphs of every degree and every number of vertices. Michael B. Cohen<ref name="c16">{{cite conference|author=Michael B. Cohen|year=2016|title=Ramanujan Graphs in Polynomial Time|conference=Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium|arxiv=1604.03544|doi=10.1109/FOCS.2016.37}}</ref> showed how to construct these graphs in polynomial time.

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

Using the method of interlacing polynomials, Marcus, Spielman, and Srivastava<ref name="mss13" /> proved Bilu & Linial's conjecture holds when <math>G</math> is already a bipartite Ramanujan graph, which is enough to conclude the existence result. The sequel<ref name="mss15" /> proved the stronger statement that a sum of <math>d</math> random bipartite matchings is Ramanujan with non-vanishing probability. Hall, Puder and Sawin<ref>{{cite journal|last1=Hall|first1=Chris|last2=Puder|first2=Doron|last3=Sawin|first3=William F.|date=2018|title=Ramanujan coverings of graphs|journal=[[Advances in Mathematics]] |volume=323 |pages=367–410 |doi=10.1016/j.aim.2017.10.042 |arxiv=1506.02335}}</ref> extended the original work of Marcus, Spielman and Srivastava to {{mvar|r}}-lifts.

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