Editing Expander graph (section)

==Constructions==
There are four general strategies for explicitly constructing families of expander graphs.<ref>see, e.g., {{harvtxt|Yehudayoff|2012}}</ref> The first strategy is algebraic and group-theoretic, the second strategy is analytic and uses [[additive combinatorics]], the third strategy is combinatorial and uses the [[zig-zag product|zig-zag]] and related graph products, and the fourth strategy is based on lifts. [[Noga Alon]] showed that certain graphs constructed from [[finite geometry|finite geometries]] are the sparsest examples of highly expanding graphs.<ref>{{cite journal | doi=10.1007/BF02579382 | volume=6 |issue = 3| title=Eigenvalues, geometric expanders, sorting in rounds, and ramsey theory | journal=Combinatorica | pages=207–219 | year=1986 | last1 = Alon | first1 = Noga| citeseerx=10.1.1.300.5945 | s2cid=8666466 }}</ref>

===Margulis–Gabber–Galil===
[[Abstract algebra|Algebraic]] constructions based on [[Cayley graph]]s are known for various variants of expander graphs. The following construction is due to Margulis and has been analysed by Gabber and Galil.<ref>see, e.g., p.9 of {{harvtxt|Goldreich|2011}}</ref> For every natural number {{mvar|n}}, one considers the graph {{mvar|G{{sub|n}}}} with the vertex set <math>\mathbb Z_n \times \mathbb Z_n</math>, where <math>\mathbb Z_n=\mathbb Z/n\mathbb Z</math>: For every vertex <math>(x,y)\in\mathbb Z_n \times \mathbb Z_n</math>, its eight adjacent vertices are

:<math>(x \pm 2y,y), (x \pm (2y+1),y), (x,y \pm 2x), (x,y \pm (2x+1)).</math>

Then the following holds:

<blockquote>'''Theorem.''' For all {{mvar|n}}, the graph {{mvar|G{{sub|n}}}} has second-largest eigenvalue <math>\lambda(G)\leq 5 \sqrt{2}</math>.</blockquote>

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

=== Zig-zag product ===
{{Main|Zig-zag product}}
[[Omer Reingold|Reingold]], [[Salil Vadhan|Vadhan]], and [[Avi Wigderson|Wigderson]] introduced the zig-zag product in 2003.<ref name=":0">{{Cite book|last1=Reingold|first1=O.|last2=Vadhan|first2=S.|last3=Wigderson|first3=A.|title=Proceedings 41st Annual Symposium on Foundations of Computer Science |chapter=Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors |chapter-url=http://dx.doi.org/10.1109/sfcs.2000.892006|year=2000|pages=3–13|publisher=IEEE Comput. Soc|doi=10.1109/sfcs.2000.892006|isbn=0-7695-0850-2|s2cid=420651}}</ref>  Roughly speaking, the zig-zag product of two expander graphs produces a graph with only slightly worse expansion. Therefore, a zig-zag product can also be used to construct families of expander graphs. If {{mvar|G}} is a {{math|(''n'', ''d'', ''λ''{{sub|1}})}}-graph and {{mvar|H}} is an {{math|(''m'', ''d'', ''λ''{{sub|2}})}}-graph, then the zig-zag product {{math|''G'' ◦ ''H''}} is a {{math|(''nm'', ''d''{{sup|2}}, ''φ''(''λ''{{sub|1}}, ''λ''{{sub|2}}))}}-graph where {{mvar|φ}} has the following properties.

# If {{math|''λ''{{sub|1}} < 1}} and {{math|''λ''{{sub|2}} < 1}}, then {{math|''φ''(''λ''{{sub|1}}, ''λ''{{sub|2}}) < 1}};
# {{math|''φ''(''λ''{{sub|1}}, ''λ''{{sub|2}}) ≤  ''λ''{{sub|1}} + ''λ''{{sub|2}}}}.
Specifically,<ref name=":0" />
:<math>\phi(\lambda_1, \lambda_2)=\frac{1}{2}(1-\lambda^2_2)\lambda_2 +\frac{1}{2}\sqrt{(1-\lambda^2_2)^2\lambda_1^2 +4\lambda^2_2}.</math>

Note that property (1) implies that the zig-zag product of two expander graphs is also an expander graph, thus zig-zag products can be used inductively to create a family of expander graphs.

Intuitively, the construction of the zig-zag product can be thought of in the following way. Each vertex of {{mvar|G}} is blown up to a "cloud" of {{mvar|m}} vertices, each associated to a different edge connected to the vertex. Each vertex is now labeled as {{math|(''v'', ''k'')}} where {{mvar|v}} refers to an original vertex of {{mvar|G}} and {{mvar|k}} refers to the {{mvar|k}}th edge of {{mvar|v}}. Two vertices, {{math|(''v'', ''k'')}} and {{math|(''w'',''ℓ'')}} are connected if it is possible to get from {{math|(''v'', ''k'')}} to {{math|(''w'', ''ℓ'')}} through the following sequence of moves.

# ''Zig'' – Move from {{math|(''v'', ''k'')}} to {{math|(''v'', ''k' '')}}, using an edge of {{mvar|H}}.
# Jump across clouds using edge {{mvar|k'}} in {{mvar|G}} to get to {{math|(''w'', ''ℓ&prime;'')}}.
# ''Zag'' – Move from {{math|(''w'', ''ℓ&prime;'')}} to {{math|(''w'', ''ℓ'')}} using an edge of {{mvar|H}}.<ref name=":0" />

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

===Randomized constructions===
There are many results that show the existence of graphs with good expansion properties through probabilistic arguments. In fact, the existence of expanders was first proved by Pinsker<ref>{{Cite journal|last=Pinkser|first=M.|title=On the Complexity of a Concentrator|journal=[[SIAM Journal on Computing]]|year=1973|publisher=SIAM|citeseerx=10.1.1.393.1430}}</ref> who showed that for a randomly chosen {{mvar|n}} vertex left {{mvar|d}} regular [[bipartite graph]],  {{math|{{abs|''N''(''S'')}} ≥ (''d'' – 2){{abs|''S''}}}} for all subsets of vertices {{math|{{abs|''S''}} ≤ ''c{{sub|d}}n''}} with high probability, where {{mvar|c{{sub|d}}}} is a constant depending on {{mvar|d}} that is {{math|''O''(''d''{{sup|-4}})}}. Alon and Roichman <ref>{{Cite journal|last1=Alon|first1=N.|last2=Roichman|first2=Y.|title=Random Cayley graphs and Expanders|url=https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.3240050203|journal=Random Structures and Algorithms|year=1994|volume=5|issue=2|pages=271–284|publisher=Wiley Online Library|doi=10.1002/rsa.3240050203}}</ref> showed that for every {{math|1 > ''ε'' > 0}}, there is some {{math|''c''(''ε'') > 0}} such that the following holds: For a group {{mvar|G}} of order {{mvar|n}}, consider the Cayley graph on {{mvar|G}} with {{math|''c''(''ε'') log{{sub|2}} ''n''}} randomly chosen elements from {{mvar|G}}. Then, in the limit of {{mvar|n}} getting to infinity, the resulting graph is almost surely an {{math|''ε''}}-expander.

In 2021, Alexander modified an MCMC algorithm to look for randomized constructions to produce Ramanujan graphs with a fixed vertex size and degree of regularity.<ref>{{cite arXiv | eprint=2110.01407 | last1=Alexander | first1=Clark | title=On Near Optimal Spectral Expander Graphs of Fixed Size | date=2021 | class=cs.DM }}</ref> The results show the Ramanujan graphs exist for every vertex size and degree pair up to 2000 vertices.  

In 2024 Alon produced an explicit construction for near Ramanujan graphs of every vertex size and degree pair.