Editing Expander graph (section)

===Lifts===
An [[Covering graph|{{mvar|r}}-lift]] of a graph is formed by replacing each vertex by {{mvar|r}} vertices, and each edge by a matching between the corresponding sets of <math>r</math> vertices. The lifted graph inherits the eigenvalues of the original graph, and has some additional eigenvalues. Bilu and [[Nati Linial|Linial]]<ref>{{cite arXiv|last1=Bilu|first1=Yonatan|last2=Linial|first2=Nathan|date=2004-04-08|title=Constructing expander graphs by 2-lifts and discrepancy vs. spectral gap|eprint=math/0312022}}</ref><ref>{{cite journal|last1=Bilu|first1=Yonatan|last2=Linial|first2=Nathan|title=Lifts, discrepancy and nearly optimal spectral gap|journal=[[Combinatorica]]|volume=26|issue=5|year=2006|pages=495–519|doi=10.1007/s00493-006-0029-7|s2cid=14422668 |issn=0209-9683}}</ref> showed that every {{mvar|d}}-regular graph has a 2-lift in which the additional eigenvalues are at most <math>O(\sqrt{d\log^3 d})</math> in magnitude. They also showed that if the starting graph is a good enough expander, then a good 2-lift can be found in [[polynomial time]], thus giving an efficient construction of {{mvar|d}}-regular expanders for every {{mvar|d}}.

Bilu and Linial conjectured that the bound <math>O(\sqrt{d\log^3 d})</math> can be improved to <math>2\sqrt{d-1}</math>, which would be optimal due to the [[Alon–Boppana bound]]. This conjecture was proved in the bipartite setting by [[Adam Marcus (mathematician)|Marcus]], [[Daniel Spielman|Spielman]] and [[Nikhil Srivastava|Srivastava]],<ref name="mss13"/><ref name="mss15"/> who used the method of interlacing polynomials. As a result, they obtained an alternative construction of [[bipartite graph|bipartite]] [[Ramanujan graph]]s. The original non-constructive proof was turned into an algorithm by 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> Later the method was generalized to {{mvar|r}}-lifts by 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>