Editing Ramanujan graph (section)

=== 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.