Editing Ramanujan graph (section)

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