Editing Expander graph (section)

===Ramanujan graphs===
{{main|Ramanujan graph}}
By a [[Alon–Boppana bound|theorem of Alon and Boppana]], all sufficiently large {{mvar|d}}-regular graphs satisfy <math>\lambda_2 \ge 2\sqrt{d-1} - o(1)</math>, where {{math|''λ''{{sub|2}}}} is the second largest eigenvalue in absolute value.<ref>Theorem 2.7 of {{harvtxt|Hoory|Linial|Wigderson|2006}}</ref> As a direct consequence, we know that for every fixed {{mvar|d}} and <math>\lambda< 2 \sqrt{d-1}</math> , there are only finitely many {{math|(''n'', ''d'', ''λ'')}}-graphs. [[Ramanujan graph]]s are {{mvar|d}}-regular graphs for which this bound is tight, satisfying <ref>Definition 5.11 of {{harvtxt|Hoory|Linial|Wigderson|2006}}</ref> 
:<math>\lambda = \max_{|\lambda_i| < d} |\lambda_i| \le 2\sqrt{d-1}.</math>
Hence Ramanujan graphs have an asymptotically smallest possible value of {{math|''λ''{{sub|2}}}}. This makes them excellent spectral expanders.

[[Alexander Lubotzky|Lubotzky]], Phillips, and [[Peter Sarnak|Sarnak]] (1988), Margulis (1988), and Morgenstern (1994) show how Ramanujan graphs can be constructed explicitly.<ref>Theorem 5.12 of {{harvtxt|Hoory|Linial|Wigderson|2006}}</ref>

In 1985, Alon, conjectured that most {{mvar|d}}-regular graphs on {{mvar|n}} vertices, for sufficiently large {{mvar|n}}, are almost Ramanujan.<ref>{{Cite journal|last=Alon|first=Noga|date=1986-06-01|title=Eigenvalues and expanders|journal=Combinatorica|language=en|volume=6|issue=2|pages=83–96|doi=10.1007/BF02579166|s2cid=41083612|issn=1439-6912}}</ref> That is, for {{math|''ε'' > 0}}, they satisfy

:<math>\lambda \le 2\sqrt{d-1}+\varepsilon</math>.

In 2003, Joel Friedman both proved the conjecture and specified what is meant by "most {{mvar|d}}-regular graphs" by showing that [[Random regular graph|random {{mvar|d}}-regular graphs]] have <math>\lambda \le 2\sqrt{d-1}+\varepsilon</math> for every {{math|''ε'' > 0}} with probability {{math|1 – ''O''(''n''{{sup|-τ}})}}, where<ref>{{cite arXiv|last=Friedman|first=Joel|date=2004-05-05|title=A proof of Alon's second eigenvalue conjecture and related problems|eprint=cs/0405020}}</ref><ref>Theorem 7.10 of {{harvtxt|Hoory|Linial|Wigderson|2006}}</ref>
:<math>\tau = \left\lceil\frac{\sqrt{d-1} +1}{2} \right\rceil.</math>
A simpler proof of a slightly weaker result was given by Puder.<ref>{{cite journal|last=Puder|first=Doron|date=2015-08-21|title=Expansion of random graphs: New proofs, new results|journal=Inventiones Mathematicae |volume=201 |issue=3 |pages=845–908 |doi=10.1007/s00222-014-0560-x |arxiv=1212.5216|bibcode=2015InMat.201..845P |s2cid=253743928 }}</ref><ref>{{cite journal|last=Puder|first=Doron|year=2015|title=Expansion of random graphs: new proofs, new results|journal=[[Inventiones Mathematicae]]|language=en|volume=201|issue=3 |pages=845–908|doi=10.1007/s00222-014-0560-x|arxiv=1212.5216 |bibcode=2015InMat.201..845P |s2cid=16411939|issn=0020-9910}}</ref><ref>{{cite journal|last1=Friedman|first1=Joel|last2=Puder|first2=Doron|date=2023|title=A note on the trace method for random regular graphs|journal=[[Israel Journal of Mathematics]] |volume=256 |pages=269–282 |doi=10.1007/s11856-023-2497-5 |arxiv=2006.13605|s2cid=220042379 }}</ref>

[[Adam Marcus (mathematician)|Marcus]], [[Daniel Spielman|Spielman]] and [[Nikhil Srivastava|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><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> gave a construction of [[bipartite graph|bipartite]] Ramanujan graphs based on [[#Lifts|lifts]].

In 2024 a preprint by Jiaoyang Huang, Theo McKenzieand and [[Horng-Tzer Yau]] proved that 

:<math>\lambda \le 2\sqrt{d-1}</math>.
with the fraction of eigenvalues that hit the Alon-Boppana bound approximately 69% from proving that [[Random matrix#Edge statistics|edge universality]] holds, that is they follow a [[Tracy–Widom distribution|Tracy-Widom distribution]] associated with the [[Gaussian Orthogonal Ensemble]]<ref>{{cite arXiv | eprint=2412.20263 | last1=Huang | first1=Jiaoyang | last2=McKenzie | first2=Theo | last3=Yau | first3=Horng-Tzer | title=Ramanujan Property and Edge Universality of Random Regular Graphs | date=2024 | class=math.PR }}</ref><ref>{{Cite web |last=Sloman |first=Leila |date=2025-04-18 |title=New Proof Settles Decades-Old Bet About Connected Networks |url=https://www.quantamagazine.org/new-proof-settles-decades-old-bet-about-connected-networks-20250418/ |access-date=2025-05-06 |website=Quanta Magazine |language=en}}</ref>