Editing Ramanujan graph (section)

=== Random graphs ===
Confirming a conjecture of [[Noga Alon|Alon]], Friedman<ref>{{Cite journal|last=Friedman|first=Joel|date=2003|title=Relative expanders or weakly relatively Ramanujan graphs|journal=Duke Mathematical Journal |volume=118|issue=1|pages=19–35|doi=10.1215/S0012-7094-03-11812-8|mr=1978881}}</ref> showed that many families of random graphs are ''weakly-Ramanujan''. This means that for every <math>d</math> and <math>\epsilon > 0</math> and for sufficiently large <math>n</math>, a random <math>d</math>-regular <math>n</math>-vertex graph <math>G</math> satisfies <math>\lambda(G) < 2\sqrt{d-1} + \epsilon</math> 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,<ref>{{cite journal
| last1=Miller | first1=Steven J.
| last2=Novikoff | first2=Tim
| last3=Sabelli | first3=Anthony
| date=2008
| title=The Distribution of the Largest Non-trivial Eigenvalues in Families of Random Regular Graphs
| arxiv=math/0611649
| journal=Experimental Mathematics
| volume=17
| issue=2
| pages=231–244
| doi=10.1080/10586458.2008.10129029
| url=https://projecteuclid.org/journals/experimental-mathematics/volume-17/issue-2/The-Distribution-of-the-Largest-Nontrivial-Eigenvalues-in-Families-of/em/1227118974.full}}</ref> 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 <math>d</math>-regular graph seems to behave according to a  [[Tracy-Widom distribution]] from random matrix theory, which would predict the same asymptotic.

In 2024 a preprint by Jiaoyang Huang, Theo McKenzieand and [[Horng-Tzer Yau]] proved that <math>\lambda(G) \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>