Expander graph

<h2 id="definitions">Definitions</h2>
Intuitively, an expander graph is a finite, undirected <a href="/facts/Multigraph/udmS0Cp0">multigraph</a> in which every subset of the vertices that is not "too large" has a "large" <a href="/facts/Boundary_(graph_theory)/IIv8aKSN">boundary</a>. Different formalisations of these notions give rise to different notions of expanders: edge expanders, vertex expanders, and spectral expanders, as defined below.
A disconnected graph is not an expander, since the boundary of a <a href="/facts/Component_(graph_theory)/5owVSXtY">connected component</a> is empty. Every connected graph is an expander; however, different connected graphs have different expansion parameters. The <a href="/facts/Complete_graph/AYD6hUqI">complete graph</a> has the best expansion property, but it has largest possible <a href="/facts/Degree_(graph_theory)/LnFFpI8v">degree</a>. Informally, a graph is a good expander if it has low degree and high expansion parameters.
Expander graphs are defined as elements of expander families.
Definition<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a>:
A family of finite, non-empty, connected graphs 
 
 
 
 (
 
 Γ
 
 i
 
 
 =
 (
 
 V
 
 i
 
 
 ,
 
 E
 
 i
 
 
 )
 
 )
 
 i
 ∈
 I
 
 
 
 
 {\displaystyle (\Gamma _{i}=(V_{i},E_{i}))_{i\in I}}
 
 is called an expander family (or a family of expanders) if there exist constants 
 
 
 
 v
 ≥
 1
 
 
 {\displaystyle v\geq 1}
 
 and 
 
 
 
 h
 >
 0
 
 
 {\displaystyle h>0}
 
, independent of 
 
 
 
 i
 
 
 {\displaystyle i}
 
, such that:

<ol><li>The number of vertices 
 
 
 
 
 |
 
 
 V
 
 i
 
 
 
 |
 
 
 
 {\displaystyle |V_{i}|}
 
 tends to infinity. That is, for every integer 
 
 
 
 N
 ≥
 1
 
 
 {\displaystyle N\geq 1}
 
, there are only finitely many 
 
 
 
 i
 ∈
 I
 
 
 {\displaystyle i\in I}
 
 such that 
 
 
 
 
 Γ
 
 i
 
 
 
 
 {\displaystyle \Gamma _{i}}
 
 has at most 
 
 
 
 N
 
 
 {\displaystyle N}
 
 vertices.</li>
<li>The maximum degree of the graphs is uniformly bounded:</li></ol>

max
          
            x
            ∈
            
              V
              
                i
              
            
          
        
        deg
        ⁡
        (
        x
        )
        ≤
        v
      
    
    {\displaystyle \max _{x\in V_{i}}\operatorname {deg} (x)\leq v}

<ol><li>The Cheeger (edge expansion) constant of each graph is uniformly bounded below:</li></ol>

h
        (
        
          Γ
          
            i
          
        
        )
        ≥
        h
        >
        0
      
    
    {\displaystyle h(\Gamma _{i})\geq h>0}

That is, the graphs become arbitrarily large, have uniformly bounded degree, and maintain a uniformly positive edge expansion constant.

<h3>Edge expansion</h3>
The edge expansion (also isoperimetric number or <a href="/facts/Cheeger_constant_(graph_theory)/hPDzmgW6">Cheeger constant</a>) h(G) of a graph G on n vertices is defined as

h
 (
 G
 )
 =
 
 min
 
 0
 <
 
 |
 
 S
 
 |
 
 ≤
 
 
 n
 2
 
 
 
 
 
 
 
 
 |
 
 ∂
 S
 
 |
 
 
 
 
 |
 
 S
 
 |
 
 
 
 
 ,
 
 
 {\displaystyle h(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial S|}{|S|}},}

where 
  
    
      
        ∂
        S
        :=
        {
        {
        u
        ,
        v
        }
        ∈
        E
        (
        G
        )
         
        :
         
        u
        ∈
        S
        ,
        v
        ∉
        S
        }
        ,
      
    
    {\displaystyle \partial S:=\{\{u,v\}\in E(G)\ :\ u\in S,v\notin S\},}

which can also be written as ∂S = E(S, S) with S := V(G) \ S the complement of S and

E
        (
        A
        ,
        B
        )
        =
        {
        {
        u
        ,
        v
        }
        ∈
        E
        (
        G
        )
         
        :
         
        u
        ∈
        A
        ,
        v
        ∈
        B
        }
      
    
    {\displaystyle E(A,B)=\{\{u,v\}\in E(G)\ :\ u\in A,v\in B\}}

the edges between the subsets of vertices A,B ⊆ V(G).
In the equation, the minimum is over all nonempty sets S of at most n⁄2 vertices and ∂S is the edge boundary of S, i.e., the set of edges with exactly one endpoint in S.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>
Intuitively,

min
        
          
            |
          
          ∂
          S
          
            |
          
        
        =
        min
        E
        (
        
          S
        
        ,
        
          
            S
            ¯
          
        
        )
      
    
    {\displaystyle \min {|\partial S|}=\min E({S},{\overline {S}})}

is the minimum number of edges that need to be cut in order to split the graph in two.
The edge expansion normalizes this concept by dividing with smallest number of vertices among the two parts.
To see how the normalization can drastically change the value, consider the following example.
Take two complete graphs with the same number of vertices n and add n edges between the two graphs by connecting their vertices one-to-one.
The minimum cut will be n but the edge expansion will be 1.
Notice that in min |∂S|, the optimization can be equivalently done either over 0 ≤ |S| ≤ n⁄2 or over any non-empty subset, since 
 
 
 
 E
 (
 S
 ,
 
 
 S
 ¯
 
 
 )
 =
 E
 (
 
 
 S
 ¯
 
 
 ,
 S
 )
 
 
 {\displaystyle E(S,{\overline {S}})=E({\overline {S}},S)}
 
. The same is not true for h(G) because of the normalization by |S|.
If we want to write h(G) with an optimization over all non-empty subsets, we can rewrite it as

h
        (
        G
        )
        =
        
          min
          
            ∅
            ⊊
            S
            ⊊
            V
            (
            G
            )
          
        
        
          
            
              E
              (
              
                S
              
              ,
              
                
                  S
                  ¯
                
              
              )
            
            
              min
              {
              
                |
              
              S
              
                |
              
              ,
              
                |
              
              
                
                  S
                  ¯
                
              
              
                |
              
              }
            
          
        
        .
      
    
    {\displaystyle h(G)=\min _{\emptyset \subsetneq S\subsetneq V(G)}{\frac {E({S},{\overline {S}})}{\min\{|S|,|{\overline {S}}|\}}}.}

<h3>Vertex expansion</h3>

The vertex isoperimetric number hout(G) (also vertex expansion or magnification) of a graph G is defined as

h
 
 out
 
 
 (
 G
 )
 =
 
 min
 
 0
 <
 
 |
 
 S
 
 |
 
 ≤
 
 
 n
 2
 
 
 
 
 
 
 
 
 |
 
 
 ∂
 
 out
 
 
 (
 S
 )
 
 |
 
 
 
 
 |
 
 S
 
 |
 
 
 
 
 ,
 
 
 {\displaystyle h_{\text{out}}(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial _{\text{out}}(S)|}{|S|}},}

where ∂out(S) is the outer boundary of S, i.e., the set of vertices in V(G) \ S with at least one neighbor in S.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a> In a variant of this definition (called unique neighbor expansion) ∂out(S) is replaced by the set of vertices in V with exactly one neighbor in S.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>
The vertex isoperimetric number hin(G) of a graph G is defined as

h
 
 in
 
 
 (
 G
 )
 =
 
 min
 
 0
 <
 
 |
 
 S
 
 |
 
 ≤
 
 
 n
 2
 
 
 
 
 
 
 
 
 |
 
 
 ∂
 
 in
 
 
 (
 S
 )
 
 |
 
 
 
 
 |
 
 S
 
 |
 
 
 
 
 ,
 
 
 {\displaystyle h_{\text{in}}(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial _{\text{in}}(S)|}{|S|}},}

where 
 
 
 
 
 ∂
 
 in
 
 
 (
 S
 )
 
 
 {\displaystyle \partial _{\text{in}}(S)}
 
 is the inner boundary of S, i.e., the set of vertices in S with at least one neighbor in V(G) \ S.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>

<h3>Spectral expansion</h3>
When G is <a href="/facts/Regular_graph/j9dSoLE6">d-regular</a>, a <a href="/facts/Linear_algebra/8VaB4VWk">linear algebraic</a> definition of expansion is possible based on the <a href="/facts/Eigenvalue/8TjEoT8u">eigenvalues</a> of the <a href="/facts/Adjacency_matrix/jYXNhYGs">adjacency matrix</a> A = A(G) of G, where Aij is the number of edges between vertices i and j.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a> Because A is <a href="/facts/Symmetric_matrix/08CGwjNl">symmetric</a>, the <a href="/facts/Spectral_theorem/Vqc04B21">spectral theorem</a> implies that A has n real-valued eigenvalues λ1 ≥ λ2 ≥ … ≥ λn. It is known that all these eigenvalues are in [−d, d] and more specifically, it is known that λn = −d if and only if G is bipartite.
More formally, we refer to an n-vertex, d-regular graph with

max
          
            i
            ≠
            1
          
        
        
          |
        
        
          λ
          
            i
          
        
        
          |
        
        ≤
        λ
      
    
    {\displaystyle \max _{i\neq 1}|\lambda _{i}|\leq \lambda }

as an (n, d, λ)-graph. The bound given by an (n, d, λ)-graph on λi for i ≠ 1 is useful in many contexts, including the <a href="/facts/Expander_mixing_lemma/JeQMfw7M">expander mixing lemma</a>.
Spectral expansion can be two-sided, as above, with 
 
 
 
 
 max
 
 i
 ≠
 1
 
 
 
 |
 
 
 λ
 
 i
 
 
 
 |
 
 ≤
 λ
 
 
 {\displaystyle \max _{i\neq 1}|\lambda _{i}|\leq \lambda }
 
, or it can be one-sided, with 
 
 
 
 
 max
 
 i
 ≠
 1
 
 
 
 λ
 
 i
 
 
 ≤
 λ
 
 
 {\displaystyle \max _{i\neq 1}\lambda _{i}\leq \lambda }
 
. The latter is a weaker notion that holds also for bipartite graphs and is still useful for many applications, such as the Alon–Chung lemma.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a>
Because G is regular, the uniform distribution 
 
 
 
 u
 ∈
 
 
 R
 
 
 n
 
 
 
 
 {\displaystyle u\in \mathbb {R} ^{n}}
 
 with ui = 1⁄n for all i = 1, …, n is the <a href="/facts/Stationary_distribution/IBLlwnPr">stationary distribution</a> of G. That is, we have Au = du, and u is an <a href="/facts/Eigenvector/8TjEoT8u">eigenvector</a> of A with eigenvalue λ1 = d, where d is the <a href="/facts/Degree_(graph_theory)/LnFFpI8v">degree</a> of the vertices of G. The <a href="/facts/Spectral_gap/jQNDusvk">spectral gap</a> of G is defined to be d − λ2, and it measures the spectral expansion of the graph G.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a>
If we set

λ
        =
        max
        {
        
          |
        
        
          λ
          
            2
          
        
        
          |
        
        ,
        
          |
        
        
          λ
          
            n
          
        
        
          |
        
        }
      
    
    {\displaystyle \lambda =\max\{|\lambda _{2}|,|\lambda _{n}|\}}

as this is the largest eigenvalue corresponding to an eigenvector <a href="/facts/Orthogonal/JVIjYPog">orthogonal</a> to u, it can be equivalently defined using the <a href="/facts/Rayleigh_quotient/yH7sD1K4">Rayleigh quotient</a>:

λ
        =
        
          max
          
            v
            ⊥
            u
            ,
            v
            ≠
            0
          
        
        
          
            
              ‖
              A
              v
              
                ‖
                
                  2
                
              
            
            
              ‖
              v
              
                ‖
                
                  2
                
              
            
          
        
        ,
      
    
    {\displaystyle \lambda =\max _{v\perp u,v\neq 0}{\frac {\|Av\|_{2}}{\|v\|_{2}}},}

where

‖
        v
        
          ‖
          
            2
          
        
        =
        
          
            (
            
              
                ∑
                
                  i
                  =
                  1
                
                
                  n
                
              
              
                v
                
                  i
                
                
                  2
                
              
            
            )
          
          
            1
            
              /
            
            2
          
        
      
    
    {\displaystyle \|v\|_{2}=\left(\sum _{i=1}^{n}v_{i}^{2}\right)^{1/2}}

is the <a href="/facts/2-norm/xIbR4uE1">2-norm</a> of the vector 
 
 
 
 v
 ∈
 
 
 R
 
 
 n
 
 
 
 
 {\displaystyle v\in \mathbb {R} ^{n}}
 
.
The normalized versions of these definitions are also widely used and more convenient in stating some results. Here one considers the matrix ⁠1/d⁠A, which is the <a href="/facts/Markov_transition_matrix/2cRWAqC3">Markov transition matrix</a> of the graph G. Its eigenvalues are between −1 and 1. For not necessarily regular graphs, the spectrum of a graph can be defined similarly using the eigenvalues of the <a href="/facts/Laplacian_matrix/Iwea2mm9">Laplacian matrix</a>. For <a href="/facts/Directed_graph/YBdfQ0um">directed graphs</a>, one considers the <a href="/facts/Singular_values/0QWHnqGG">singular values</a> of the adjacency matrix A, which are equal to the roots of the eigenvalues of the symmetric matrix ATA.

<h2 id="relationships-between-different-expansion-properties">Relationships between different expansion properties</h2>
The expansion parameters defined above are related to each other. In particular, for any d-regular graph G,

h
          
            out
          
        
        (
        G
        )
        ≤
        h
        (
        G
        )
        ≤
        d
        ⋅
        
          h
          
            out
          
        
        (
        G
        )
        .
      
    
    {\displaystyle h_{\text{out}}(G)\leq h(G)\leq d\cdot h_{\text{out}}(G).}

Consequently, for constant degree graphs, vertex and edge expansion are qualitatively the same.

<h3>Cheeger inequalities</h3>
When G is d-regular, meaning each vertex is of degree d, there is a relationship between the isoperimetric constant h(G) and the gap d − λ2 in the spectrum of the adjacency operator of G. By standard spectral graph theory, the trivial eigenvalue of the adjacency operator of a d-regular graph is λ1 = d and the first non-trivial eigenvalue is λ2. If G is connected, then λ2 < d. An inequality due to Dodziuk<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a> and independently <a href="/facts/Noga_Alon/tuqq2GUl">Alon</a> and <a href="/facts/Vitali_Milman/4aHLsgu4">Milman</a><a class="footnote-ref" id="fnref:11" href="#fn:11">11</a> states that<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a>

1
              2
            
          
        
        (
        d
        −
        
          λ
          
            2
          
        
        )
        ≤
        h
        (
        G
        )
        ≤
        
          
            2
            d
            (
            d
            −
            
              λ
              
                2
              
            
            )
          
        
        .
      
    
    {\displaystyle {\tfrac {1}{2}}(d-\lambda _{2})\leq h(G)\leq {\sqrt {2d(d-\lambda _{2})}}.}

In fact, the lower bound is tight. The lower bound is achieved in limit for the <a href="/facts/Hypercube_graph/pwfGEl9J">hypercube</a> Qn, where h(G) = 1 and d – λ2 = 2. The upper bound is (asymptotically) achieved for a cycle, where h(Cn) = 4/n = Θ(1/n) and d – λ2 = 2 – 2cos(2
 
 
 
 π
 
 
 {\displaystyle \pi }
 
/n) ≈ (2
 
 
 
 π
 
 
 {\displaystyle \pi }
 
/n)2 = Θ(1/n2).<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a> A better bound is given in <a class="footnote-ref" id="fnref:14" href="#fn:14">14</a> as

h
        (
        G
        )
        ≤
        
          
            
              d
              
                2
              
            
            −
            
              λ
              
                2
              
              
                2
              
            
          
        
        .
      
    
    {\displaystyle h(G)\leq {\sqrt {d^{2}-\lambda _{2}^{2}}}.}

These inequalities are closely related to the <a href="/facts/Cheeger_bound/sxLwSCyK">Cheeger bound</a> for <a href="/facts/Markov_chains/5oP5hntk">Markov chains</a> and can be seen as a discrete version of <a href="/facts/Cheeger_constant/4FoJFsrP">Cheeger's inequality</a> in <a href="/facts/Riemannian_geometry/pPEzjyQC">Riemannian geometry</a>.
Similar connections between vertex isoperimetric numbers and the spectral gap have also been studied:<a class="footnote-ref" id="fnref:15" href="#fn:15">15</a>

h
          
            out
          
        
        (
        G
        )
        ≤
        
          
            (
            
              
                
                  4
                  (
                  d
                  −
                  
                    λ
                    
                      2
                    
                  
                  )
                
              
              +
              1
            
            )
          
          
            2
          
        
        −
        1
      
    
    {\displaystyle h_{\text{out}}(G)\leq \left({\sqrt {4(d-\lambda _{2})}}+1\right)^{2}-1}

h
          
            in
          
        
        (
        G
        )
        ≤
        
          
            8
            (
            d
            −
            
              λ
              
                2
              
            
            )
          
        
        .
      
    
    {\displaystyle h_{\text{in}}(G)\leq {\sqrt {8(d-\lambda _{2})}}.}

Asymptotically speaking, the quantities h2⁄d, hout, and hin2 are all bounded above by the spectral gap O(d – λ2).

<h2 id="constructions">Constructions</h2>
There are four general strategies for explicitly constructing families of expander graphs.<a class="footnote-ref" id="fnref:16" href="#fn:16">16</a> The first strategy is algebraic and group-theoretic, the second strategy is analytic and uses <a href="/facts/Additive_combinatorics/wfvGQVUB">additive combinatorics</a>, the third strategy is combinatorial and uses the <a href="/facts/Zig-zag_product/M7N86Q6n">zig-zag</a> and related graph products, and the fourth strategy is based on lifts. <a href="/facts/Noga_Alon/tuqq2GUl">Noga Alon</a> showed that certain graphs constructed from <a href="/facts/Finite_geometry/GL0nnEk8">finite geometries</a> are the sparsest examples of highly expanding graphs.<a class="footnote-ref" id="fnref:17" href="#fn:17">17</a>

<h3>Margulis–Gabber–Galil</h3>
<a href="/facts/Abstract_algebra/YNNE1CNz">Algebraic</a> constructions based on <a href="/facts/Cayley_graph/QxoxNnys">Cayley graphs</a> are known for various variants of expander graphs. The following construction is due to Margulis and has been analysed by Gabber and Galil.<a class="footnote-ref" id="fnref:18" href="#fn:18">18</a> For every natural number n, one considers the graph Gn with the vertex set 
 
 
 
 
 
 Z
 
 
 n
 
 
 ×
 
 
 Z
 
 
 n
 
 
 
 
 {\displaystyle \mathbb {Z} _{n}\times \mathbb {Z} _{n}}
 
, where 
 
 
 
 
 
 Z
 
 
 n
 
 
 =
 
 Z
 
 
 /
 
 n
 
 Z
 
 
 
 {\displaystyle \mathbb {Z} _{n}=\mathbb {Z} /n\mathbb {Z} }
 
: For every vertex 
 
 
 
 (
 x
 ,
 y
 )
 ∈
 
 
 Z
 
 
 n
 
 
 ×
 
 
 Z
 
 
 n
 
 
 
 
 {\displaystyle (x,y)\in \mathbb {Z} _{n}\times \mathbb {Z} _{n}}
 
, its eight adjacent vertices are

(
        x
        ±
        2
        y
        ,
        y
        )
        ,
        (
        x
        ±
        (
        2
        y
        +
        1
        )
        ,
        y
        )
        ,
        (
        x
        ,
        y
        ±
        2
        x
        )
        ,
        (
        x
        ,
        y
        ±
        (
        2
        x
        +
        1
        )
        )
        .
      
    
    {\displaystyle (x\pm 2y,y),(x\pm (2y+1),y),(x,y\pm 2x),(x,y\pm (2x+1)).}

Then the following holds:

<blockquote>Theorem. For all n, the graph Gn has second-largest eigenvalue 
 
 
 
 λ
 (
 G
 )
 ≤
 5
 
 
 2
 
 
 
 
 {\displaystyle \lambda (G)\leq 5{\sqrt {2}}}
 
.</blockquote>
<h3>Ramanujan graphs</h3>
Main article: <a href="/facts/Ramanujan_graph/T0lXTlmW">Ramanujan graph</a>
By a <a href="/facts/Alon%25E2%2580%2593Boppana_bound/69Xcfg26">theorem of Alon and Boppana</a>, all sufficiently large d-regular graphs satisfy 
 
 
 
 
 λ
 
 2
 
 
 ≥
 2
 
 
 d
 −
 1
 
 
 −
 o
 (
 1
 )
 
 
 {\displaystyle \lambda _{2}\geq 2{\sqrt {d-1}}-o(1)}
 
, where λ2 is the second largest eigenvalue in absolute value.<a class="footnote-ref" id="fnref:19" href="#fn:19">19</a> As a direct consequence, we know that for every fixed d and 
 
 
 
 λ
 <
 2
 
 
 d
 −
 1
 
 
 
 
 {\displaystyle \lambda <2{\sqrt {d-1}}}
 
 , there are only finitely many (n, d, λ)-graphs. <a href="/facts/Ramanujan_graph/T0lXTlmW">Ramanujan graphs</a> are d-regular graphs for which this bound is tight, satisfying <a class="footnote-ref" id="fnref:20" href="#fn:20">20</a>

λ
 =
 
 max
 
 
 |
 
 
 λ
 
 i
 
 
 
 |
 
 <
 d
 
 
 
 |
 
 
 λ
 
 i
 
 
 
 |
 
 ≤
 2
 
 
 d
 −
 1
 
 
 .
 
 
 {\displaystyle \lambda =\max _{|\lambda _{i}|<d}|\lambda _{i}|\leq 2{\sqrt {d-1}}.}

Hence Ramanujan graphs have an asymptotically smallest possible value of λ2. This makes them excellent spectral expanders.
<a href="/facts/Alexander_Lubotzky/S2oDFSAF">Lubotzky</a>, Phillips, and <a href="/facts/Peter_Sarnak/AbX2EeQJ">Sarnak</a> (1988), Margulis (1988), and Morgenstern (1994) show how Ramanujan graphs can be constructed explicitly.<a class="footnote-ref" id="fnref:21" href="#fn:21">21</a>
In 1985, Alon, conjectured that most d-regular graphs on n vertices, for sufficiently large n, are almost Ramanujan.<a class="footnote-ref" id="fnref:22" href="#fn:22">22</a> That is, for ε > 0, they satisfy

λ
 ≤
 2
 
 
 d
 −
 1
 
 
 +
 ε
 
 
 {\displaystyle \lambda \leq 2{\sqrt {d-1}}+\varepsilon }
 
.
In 2003, Joel Friedman both proved the conjecture and specified what is meant by "most d-regular graphs" by showing that <a href="/facts/Random_regular_graph/v1gWMC6h">random d-regular graphs</a> have 
 
 
 
 λ
 ≤
 2
 
 
 d
 −
 1
 
 
 +
 ε
 
 
 {\displaystyle \lambda \leq 2{\sqrt {d-1}}+\varepsilon }
 
 for every ε > 0 with probability 1 – O(n-τ), where<a class="footnote-ref" id="fnref:23" href="#fn:23">23</a><a class="footnote-ref" id="fnref:24" href="#fn:24">24</a>

τ
        =
        
          ⌈
          
            
              
                
                  
                    d
                    −
                    1
                  
                
                +
                1
              
              2
            
          
          ⌉
        
        .
      
    
    {\displaystyle \tau =\left\lceil {\frac {{\sqrt {d-1}}+1}{2}}\right\rceil .}

A simpler proof of a slightly weaker result was given by Puder.<a class="footnote-ref" id="fnref:25" href="#fn:25">25</a><a class="footnote-ref" id="fnref:26" href="#fn:26">26</a><a class="footnote-ref" id="fnref:27" href="#fn:27">27</a>
<a href="/facts/Adam_Marcus_(mathematician)/PwgjlGMr">Marcus</a>, <a href="/facts/Daniel_Spielman/Gspcy7D0">Spielman</a> and <a href="/facts/Nikhil_Srivastava/DondKFN0">Srivastava</a>,<a class="footnote-ref" id="fnref:28" href="#fn:28">28</a><a class="footnote-ref" id="fnref:29" href="#fn:29">29</a> gave a construction of <a href="/facts/Bipartite_graph/xWcXV9MB">bipartite</a> Ramanujan graphs based on lifts.
In 2024 a preprint by Jiaoyang Huang, Theo McKenzieand and <a href="/facts/Horng-Tzer_Yau/kphtrPGw">Horng-Tzer Yau</a> proved that

λ
 ≤
 2
 
 
 d
 −
 1
 
 
 
 
 {\displaystyle \lambda \leq 2{\sqrt {d-1}}}
 
.
with the fraction of eigenvalues that hit the Alon-Boppana bound approximately 69% from proving that <a href="/facts/Random_matrix/Yqo1lwFW">edge universality</a> holds, that is they follow a <a href="/facts/Tracy%25E2%2580%2593Widom_distribution/kqYFk3SF">Tracy-Widom distribution</a> associated with the <a href="/facts/Gaussian_Orthogonal_Ensemble/Yqo1lwFW">Gaussian Orthogonal Ensemble</a><a class="footnote-ref" id="fnref:30" href="#fn:30">30</a><a class="footnote-ref" id="fnref:31" href="#fn:31">31</a>

<h3>Zig-zag product</h3>
Main article: <a href="/facts/Zig-zag_product/M7N86Q6n">Zig-zag product</a>
<a href="/facts/Omer_Reingold/MaaTa9CF">Reingold</a>, <a href="/facts/Salil_Vadhan/GAnBgrn7">Vadhan</a>, and <a href="/facts/Avi_Wigderson/CVHaUAdI">Wigderson</a> introduced the zig-zag product in 2003.<a class="footnote-ref" id="fnref:32" href="#fn:32">32</a> 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 G is a (n, d, λ1)-graph and H is an (m, d, λ2)-graph, then the zig-zag product G ◦ H is a (nm, d2, φ(λ1, λ2))-graph where φ has the following properties.

<ol><li>If λ1 < 1 and λ2 < 1, then φ(λ1, λ2) < 1;</li>
<li>φ(λ1, λ2) ≤ λ1 + λ2.</li></ol>
Specifically,<a class="footnote-ref" id="fnref:33" href="#fn:33">33</a>

ϕ
        (
        
          λ
          
            1
          
        
        ,
        
          λ
          
            2
          
        
        )
        =
        
          
            1
            2
          
        
        (
        1
        −
        
          λ
          
            2
          
          
            2
          
        
        )
        
          λ
          
            2
          
        
        +
        
          
            1
            2
          
        
        
          
            (
            1
            −
            
              λ
              
                2
              
              
                2
              
            
            
              )
              
                2
              
            
            
              λ
              
                1
              
              
                2
              
            
            +
            4
            
              λ
              
                2
              
              
                2
              
            
          
        
        .
      
    
    {\displaystyle \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}}}.}

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 G is blown up to a "cloud" of m vertices, each associated to a different edge connected to the vertex. Each vertex is now labeled as (v, k) where v refers to an original vertex of G and k refers to the kth edge of v. Two vertices, (v, k) and (w,ℓ) are connected if it is possible to get from (v, k) to (w, ℓ) through the following sequence of moves.

<ol><li>Zig – Move from (v, k) to (v, k' ), using an edge of H.</li>
<li>Jump across clouds using edge k' in G to get to (w, ℓ′).</li>
<li>Zag – Move from (w, ℓ′) to (w, ℓ) using an edge of H.<a class="footnote-ref" id="fnref:34" href="#fn:34">34</a></li></ol>
<h3>Lifts</h3>
An <a href="/facts/Covering_graph/0pJVjV86">r-lift</a> of a graph is formed by replacing each vertex by r vertices, and each edge by a matching between the corresponding sets of 
 
 
 
 r
 
 
 {\displaystyle r}
 
 vertices. The lifted graph inherits the eigenvalues of the original graph, and has some additional eigenvalues. Bilu and <a href="/facts/Nati_Linial/YDkX3Dyk">Linial</a><a class="footnote-ref" id="fnref:35" href="#fn:35">35</a><a class="footnote-ref" id="fnref:36" href="#fn:36">36</a> showed that every d-regular graph has a 2-lift in which the additional eigenvalues are at most 
 
 
 
 O
 (
 
 
 d
 
 log
 
 3
 
 
 ⁡
 d
 
 
 )
 
 
 {\displaystyle O({\sqrt {d\log ^{3}d}})}
 
 in magnitude. They also showed that if the starting graph is a good enough expander, then a good 2-lift can be found in <a href="/facts/Polynomial_time/77T62gmf">polynomial time</a>, thus giving an efficient construction of d-regular expanders for every d.
Bilu and Linial conjectured that the bound 
 
 
 
 O
 (
 
 
 d
 
 log
 
 3
 
 
 ⁡
 d
 
 
 )
 
 
 {\displaystyle O({\sqrt {d\log ^{3}d}})}
 
 can be improved to 
 
 
 
 2
 
 
 d
 −
 1
 
 
 
 
 {\displaystyle 2{\sqrt {d-1}}}
 
, which would be optimal due to the <a href="/facts/Alon%25E2%2580%2593Boppana_bound/69Xcfg26">Alon–Boppana bound</a>. This conjecture was proved in the bipartite setting by <a href="/facts/Adam_Marcus_(mathematician)/PwgjlGMr">Marcus</a>, <a href="/facts/Daniel_Spielman/Gspcy7D0">Spielman</a> and <a href="/facts/Nikhil_Srivastava/DondKFN0">Srivastava</a>,<a class="footnote-ref" id="fnref:37" href="#fn:37">37</a><a class="footnote-ref" id="fnref:38" href="#fn:38">38</a> who used the method of interlacing polynomials. As a result, they obtained an alternative construction of <a href="/facts/Bipartite_graph/xWcXV9MB">bipartite</a> <a href="/facts/Ramanujan_graph/T0lXTlmW">Ramanujan graphs</a>. The original non-constructive proof was turned into an algorithm by Michael B. Cohen.<a class="footnote-ref" id="fnref:39" href="#fn:39">39</a> Later the method was generalized to r-lifts by Hall, Puder and Sawin.<a class="footnote-ref" id="fnref:40" href="#fn:40">40</a>

<h3>Randomized constructions</h3>
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<a class="footnote-ref" id="fnref:41" href="#fn:41">41</a> who showed that for a randomly chosen n vertex left d regular <a href="/facts/Bipartite_graph/xWcXV9MB">bipartite graph</a>, |N(S)| ≥ (d – 2)|S| for all subsets of vertices |S| ≤ cdn with high probability, where cd is a constant depending on d that is O(d-4). Alon and Roichman <a class="footnote-ref" id="fnref:42" href="#fn:42">42</a> showed that for every 1 > ε > 0, there is some c(ε) > 0 such that the following holds: For a group G of order n, consider the Cayley graph on G with c(ε) log2 n randomly chosen elements from G. Then, in the limit of n getting to infinity, the resulting graph is almost surely an ε-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.<a class="footnote-ref" id="fnref:43" href="#fn:43">43</a> 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.

<h2 id="applications-and-useful-properties">Applications and useful properties</h2>
The original motivation for expanders is to build economical robust networks (phone or computer): an expander with bounded degree is precisely an asymptotic robust graph with the number of edges growing linearly with size (number of vertices), for all subsets.
Expander graphs have found extensive applications in <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, in designing <a href="/facts/Algorithm/fnl5NmRt">algorithms</a>, <a href="/facts/Expander_code/DrUIuEbH">error correcting codes</a>, <a href="/facts/Extractor_(mathematics)/UC1j6bn9">extractors</a>, <a href="/facts/Pseudorandom_generator/sdRrlm8Y">pseudorandom generators</a>, <a href="/facts/Sorting_network/ceMfQqSh">sorting networks</a> (Ajtai, Komlós & Szemerédi (1983)) and robust <a href="/facts/Computer_network/3w5RM99p">computer networks</a>. They have also been used in proofs of many important results in <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a>, such as <a href="/facts/SL_(complexity)/NHcut8wL">SL</a> = <a href="/facts/L_(complexity)/vCMV0edS">L</a> (Reingold (2008)) and the <a href="/facts/PCP_theorem/GwlBcYH6">PCP theorem</a> (Dinur (2007)). In <a href="/facts/Cryptography/e94PEVau">cryptography</a>, expander graphs are used to construct <a href="/facts/Hash_function/rk6MlCt3">hash functions</a>.
In a <a href="https://www.ams.org/journals/bull/2006-43-04/S0273-0979-06-01126-8/">2006 survey of expander graphs</a>, Hoory, Linial, and Wigderson split the study of expander graphs into four categories: <a href="/facts/Extremal_graph_theory/mdkBX6yN">extremal problems</a>, typical behavior, explicit constructions, and algorithms. Extremal problems focus on the bounding of expansion parameters, while typical behavior problems characterize how the expansion parameters are distributed over <a href="/facts/Random_graph/gfQhq1Sz">random graphs</a>. Explicit constructions focus on constructing graphs that optimize certain parameters, and algorithmic questions study the evaluation and estimation of parameters.

<h3>Expander mixing lemma</h3>
Main article: <a href="/facts/Expander_mixing_lemma/JeQMfw7M">Expander mixing lemma</a>
The expander mixing lemma states that for an (n, d, λ)-graph, for any two subsets of the vertices S, T ⊆ V, the number of edges between S and T is approximately what you would expect in a random d-regular graph. The approximation is better the smaller λ is. In a random d-regular graph, as well as in an <a href="/facts/Erd%25C5%2591s%25E2%2580%2593R%25C3%25A9nyi_model/F6BQ8gIj">Erdős–Rényi random graph</a> with edge probability d⁄n, we expect d⁄n • |S| • |T| edges between S and T.
More formally, let E(S, T) denote the number of edges between S and T. If the two sets are not disjoint, edges in their intersection are counted twice, that is,

E
        (
        S
        ,
        T
        )
        =
        2
        
          |
        
        E
        (
        G
        [
        S
        ∩
        T
        ]
        )
        
          |
        
        +
        E
        (
        S
        ∖
        T
        ,
        T
        )
        +
        E
        (
        S
        ,
        T
        ∖
        S
        )
        .
      
    
    {\displaystyle E(S,T)=2|E(G[S\cap T])|+E(S\setminus T,T)+E(S,T\setminus S).}

Then the expander mixing lemma says that the following inequality holds:

|
          
            E
            (
            S
            ,
            T
            )
            −
            
              
                
                  d
                  ⋅
                  
                    |
                  
                  S
                  
                    |
                  
                  ⋅
                  
                    |
                  
                  T
                  
                    |
                  
                
                n
              
            
          
          |
        
        ≤
        λ
        
          
            
              |
            
            S
            
              |
            
            ⋅
            
              |
            
            T
            
              |
            
          
        
        .
      
    
    {\displaystyle \left|E(S,T)-{\frac {d\cdot |S|\cdot |T|}{n}}\right|\leq \lambda {\sqrt {|S|\cdot |T|}}.}

Many properties of (n, d, λ)-graphs are corollaries of the expander mixing lemmas, including the following.<a class="footnote-ref" id="fnref:44" href="#fn:44">44</a>

<ul><li>An <a href="/facts/Independent_set_(graph_theory)/ksu46kdz">independent set</a> of a graph is a subset of vertices with no two vertices adjacent. In an (n, d, λ)-graph, an independent set has size at most λn⁄d.</li>
<li>The <a href="/facts/Graph_coloring/J6HoBfP0">chromatic number</a> of a graph G, χ(G), is the minimum number of colors needed such that adjacent vertices have different colors. Hoffman showed that d⁄λ ≤ χ(G),<a class="footnote-ref" id="fnref:45" href="#fn:45">45</a> while Alon, Krivelevich, and Sudakov showed that if d < 2n⁄3, then<a class="footnote-ref" id="fnref:46" href="#fn:46">46</a></li></ul>

 
 
 
 χ
 (
 G
 )
 ≤
 O
 
 (
 
 
 d
 
 log
 ⁡
 (
 1
 +
 d
 
 /
 
 λ
 )
 
 
 
 )
 
 .
 
 
 {\displaystyle \chi (G)\leq O\left({\frac {d}{\log(1+d/\lambda )}}\right).}

<ul><li>The <a href="/facts/Diameter_(graph_theory)/EmQFKvqa">diameter</a> of a graph is the maximum distance between two vertices, where the distance between two vertices is defined to be the shortest path between them. Chung showed that the diameter of an (n, d, λ)-graph is at most<a class="footnote-ref" id="fnref:47" href="#fn:47">47</a></li></ul>

 
 
 
 
 ⌈
 
 log
 ⁡
 
 
 n
 
 log
 ⁡
 (
 d
 
 /
 
 λ
 )
 
 
 
 
 ⌉
 
 .
 
 
 {\displaystyle \left\lceil \log {\frac {n}{\log(d/\lambda )}}\right\rceil .}

<h3>Expander walk sampling</h3>
Main article: <a href="/facts/Expander_walk_sampling/J1sYcnq8">Expander walk sampling</a>
The <a href="/facts/Chernoff_bound/RLC6VlRU">Chernoff bound</a> states that, when sampling many independent samples from a random variable in the range [−1, 1], with high probability the average of our samples is close to the expectation of the random variable. The expander walk sampling lemma, due to Ajtai, Komlós & Szemerédi (1987) and Gillman (1998), states that this also holds true when sampling from a walk on an expander graph. This is particularly useful in the theory of <a href="/facts/Derandomization/Fngl1zgk">derandomization</a>, since sampling according to an expander walk uses many fewer random bits than sampling independently.

<h3>AKS sorting network and approximate halvers</h3>
Main article: <a href="/facts/Sorting_network/ceMfQqSh">Sorting network</a>
Sorting networks take a set of inputs and perform a series of parallel steps to sort the inputs. A parallel step consists of performing any number of disjoint comparisons and potentially swapping pairs of compared inputs. The depth of a network is given by the number of parallel steps it takes. Expander graphs play an important role in the AKS sorting network, which achieves depth O(log n). While this is asymptotically the best known depth for a sorting network, the reliance on expanders makes the constant bound too large for practical use.
Within the AKS sorting network, expander graphs are used to construct bounded depth ε-halvers. An ε-halver takes as input a length n permutation of (1, …, n) and halves the inputs into two disjoint sets A and B such that for each integer k ≤ n⁄2 at most εk of the k smallest inputs are in B and at most εk of the k largest inputs are in A. The sets A and B are an ε-halving.
Following Ajtai, Komlós & Szemerédi (1983), a depth d ε-halver can be constructed as follows. Take an n vertex, degree d bipartite expander with parts X and Y of equal size such that every subset of vertices of size at most εn has at least ⁠1 – ε/ε⁠ neighbors.
The vertices of the graph can be thought of as registers that contain inputs and the edges can be thought of as wires that compare the inputs of two registers. At the start, arbitrarily place half of the inputs in X and half of the inputs in Y and decompose the edges into d perfect matchings. The goal is to end with X roughly containing the smaller half of the inputs and Y containing roughly the larger half of the inputs. To achieve this, sequentially process each matching by comparing the registers paired up by the edges of this matching and correct any inputs that are out of order. Specifically, for each edge of the matching, if the larger input is in the register in X and the smaller input is in the register in Y, then swap the two inputs so that the smaller one is in X and the larger one is in Y. It is clear that this process consists of d parallel steps.
After all d rounds, take A to be the set of inputs in registers in X and B to be the set of inputs in registers in Y to obtain an ε-halving. To see this, notice that if a register u in X and v in Y are connected by an edge uv then after the matching with this edge is processed, the input in u is less than that of v. Furthermore, this property remains true throughout the rest of the process. Now, suppose for some k ≤ n⁄2 that more than εk of the inputs (1, …, k) are in B. Then by expansion properties of the graph, the registers of these inputs in Y are connected with at least ⁠1 – ε/ε⁠k registers in X. Altogether, this constitutes more than k registers so there must be some register A in X connected to some register B in Y such that the final input of A is not in (1, …, k), while the final input of B is. This violates the previous property however, and thus the output sets A and B must be an ε-halving.

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Algebraic_connectivity/z7kP4K3s">Algebraic connectivity</a></li>
<li><a href="/facts/Zig-zag_product/M7N86Q6n">Zig-zag product</a></li>
<li><a href="/facts/Superstrong_approximation/WbVtJP1p">Superstrong approximation</a></li>
<li><a href="/facts/Spectral_graph_theory/tBttgGTh">Spectral graph theory</a></li></ul>
<h2 id="notes">Notes</h2>

<ul><li>Alexander, Clark (2021). "On Near Optimal Spectral Expander Graphs of Fixed Size". <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/2110.01407">2110.01407</a> [<a href="https://arxiv.org/archive/cs.DM">cs.DM</a>].</li></ul>

<h3>Textbooks and surveys</h3>
<ul><li><a href="/facts/Noga_Alon/tuqq2GUl">Alon, N.</a>; <a href="/facts/Joel_Spencer/dhg8jEo4">Spencer, Joel H.</a> (2011). "9.2. Eigenvalues and Expanders". The Probabilistic Method (3rd ed.). John Wiley & Sons.</li>
<li>Chung, Fan R. K. (1997), Spectral Graph Theory, CBMS Regional Conference Series in Mathematics, vol. 92, <a href="/facts/American_Mathematical_Society/fr5gotCt">American Mathematical Society</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-8218-0315-8</li>
<li>Davidoff, Guiliana; Sarnak, Peter; Valette, Alain (2003), <a href="/facts/Elementary_Number_Theory%2c_Group_Theory_and_Ramanujan_Graphs/KnWFDXrq">Elementary number theory, group theory and Ramanujan graphs</a>, LMS student texts, vol. 55, <a href="/facts/Cambridge_University_Press/fgEBSSRq">Cambridge University Press</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-521-53143-6</li>
<li>Hoory, Shlomo; <a href="/facts/Nati_Linial/YDkX3Dyk">Linial, Nathan</a>; <a href="/facts/Avi_Wigderson/CVHaUAdI">Wigderson, Avi</a> (2006), <a href="http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf">"Expander graphs and their applications"</a> (PDF), Bulletin of the American Mathematical Society, New Series, 43 (4): 439–561, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1090%2FS0273-0979-06-01126-8">10.1090/S0273-0979-06-01126-8</a></li>
<li>Krebs, Mike; Shaheen, Anthony (2011), Expander families and Cayley graphs: A beginner's guide, Oxford University Press, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-19-976711-3</li></ul>
<h3>Research articles</h3>
<ul><li><a href="/facts/Mikl%25C3%25B3s_Ajtai/xwP2qpPq">Ajtai, M.</a>; <a href="/facts/J%25C3%25A1nos_Koml%25C3%25B3s_(mathematician)/HeELHvHq">Komlós, J.</a>; <a href="/facts/Endre_Szemer%25C3%25A9di/bE2Ezgbl">Szemerédi, E.</a> (1983), "An O(n log n) sorting network", Proceedings of the 15th Annual ACM Symposium on Theory of Computing, pp. 1–9, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F800061.808726">10.1145/800061.808726</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-89791-099-6, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:15311122">15311122</a></li>
<li>Ajtai, M.; Komlós, J.; Szemerédi, E. (1987), "Deterministic simulation in LOGSPACE", Proceedings of the 19th Annual ACM Symposium on Theory of Computing, ACM, pp. 132–140, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F28395.28410">10.1145/28395.28410</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-89791-221-1, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:15323404">15323404</a></li>
<li>Alon, N.; Capalbo, M. (2002), "Explicit unique-neighbor expanders", The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings, p. 73, <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.103.967">10.1.1.103.967</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1109%2FSFCS.2002.1181884">10.1109/SFCS.2002.1181884</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-7695-1822-0, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:6364755">6364755</a></li>
<li>Bobkov, S.; Houdré, C.; <a href="/facts/Prasad_V._Tetali/4FBqt7jl">Tetali, P.</a> (2000), "λ∞, vertex isoperimetry and concentration", Combinatorica, 20 (2): 153–172, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2Fs004930070018">10.1007/s004930070018</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:1173532">1173532</a>.</li>
<li>Dinur, Irit (2007), <a href="http://www.cs.huji.ac.il/~dinuri/mypapers/combpcp.pdf">"The PCP theorem by gap amplification"</a> (PDF), Journal of the ACM, 54 (3): 12–es, <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.103.2644">10.1.1.103.2644</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F1236457.1236459">10.1145/1236457.1236459</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:53244523">53244523</a>.</li>
<li>Dodziuk, Jozef (1984), "Difference equations, isoperimetric inequality and transience of certain random walks", Trans. Amer. Math. Soc., 284 (2): 787–794, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.2307%2F1999107">10.2307/1999107</a>, <a href="/facts/JSTOR_(identifier)/YTeVmaJ7">JSTOR</a> <a href="https://www.jstor.org/stable/1999107">1999107</a>.</li>
<li>Gillman, D. (1998), "A Chernoff Bound for Random Walks on Expander Graphs", SIAM Journal on Computing, 27 (4): 1203–1220, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1137%2FS0097539794268765">10.1137/S0097539794268765</a></li>
<li>Goldreich, Oded (2011), "Basic Facts about Expander Graphs", <a href="http://www.wisdom.weizmann.ac.il/%7Eoded/COL/expander.pdf">Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation</a> (PDF), Lecture Notes in Computer Science (Vol. 6650), vol. 6650, pp. 451–464, <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.231.1388">10.1.1.231.1388</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F978-3-642-22670-0_30">10.1007/978-3-642-22670-0_30</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-642-22669-4</li>
<li><a href="/facts/Omer_Reingold/MaaTa9CF">Reingold, Omer</a> (2008), "Undirected connectivity in log-space", <a href="/facts/Journal_of_the_ACM/qkIF9LLS">Journal of the ACM</a>, 55 (4): 1–24, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F1391289.1391291">10.1145/1391289.1391291</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:207168478">207168478</a></li>
<li>Yehudayoff, Amir (2012), "Proving expansion in three steps", <a href="/facts/ACM_SIGACT_News/E4QBwEy8">ACM SIGACT News</a>, 43 (3): 67–84, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F2421096.2421115">10.1145/2421096.2421115</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:18098370">18098370</a></li></ul>
<h3>Recent Applications</h3>
<ul><li>Hartnett, Kevin (2018), <a href="https://www.quantamagazine.org/universal-method-to-sort-complex-information-found-20180813/">"Universal Method to Sort Complex Information Found"</a>, Quanta Magazine (published 13 August 2018)</li></ul>

<h2 id="external-links">External links</h2>
<ul><li><a href="https://www.ams.org/notices/200407/what-is.pdf">Brief introduction in Notices of the American Mathematical Society</a></li>
<li><a href="http://michaelnielsen.org/blog/archive/notes/expander_graphs.pdf">Introductory paper by Michael Nielsen</a> <a href="https://web.archive.org/web/20160817025506/http://michaelnielsen.org/blog/archive/notes/expander_graphs.pdf">Archived</a> 2016-08-17 at the <a href="/facts/Wayback_Machine/nmQ3a6JC">Wayback Machine</a></li>
<li><a href="https://web.archive.org/web/20160629170338/http://www.math.ias.edu/~boaz/ExpanderCourse/">Lecture notes from a course on expanders (by Nati Linial and Avi Wigderson)</a></li>
<li><a href="http://ttic.uchicago.edu/~prahladh/teaching/spring05/index.html">Lecture notes from a course on expanders (by Prahladh Harsha)</a></li>
<li><a href="https://web.archive.org/web/20070523090323/http://www.yann-ollivier.org/specgraph/specgraph.html">Definition and application of spectral gap</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Hoory, Linial & Wigderson (2006) - Hoory, Shlomo; Linial, Nathan; Wigderson, Avi (2006), "Expander graphs and their applications" (PDF), Bulletin of the American Mathematical Society, New Series, 43 (4): 439–561, doi:10.1090/S0273-0979-06-01126-8 <a href="http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf" target="_blank">http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Definition 3.1.8 in "An introduction to expander graphs" by Kowalski(2024) <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Definition 2.1 in Hoory, Linial & Wigderson (2006) - Hoory, Shlomo; Linial, Nathan; Wigderson, Avi (2006), "Expander graphs and their applications" (PDF), Bulletin of the American Mathematical Society, New Series, 43 (4): 439–561, doi:10.1090/S0273-0979-06-01126-8 <a href="http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf" target="_blank">http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Bobkov, Houdré & Tetali (2000) - Bobkov, S.; Houdré, C.; Tetali, P. (2000), "λ∞, vertex isoperimetry and concentration", Combinatorica, 20 (2): 153–172, doi:10.1007/s004930070018, S2CID 1173532 <a href="https://doi.org/10.1007%2Fs004930070018" target="_blank">https://doi.org/10.1007%2Fs004930070018</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Alon & Capalbo (2002) - Alon, N.; Capalbo, M. (2002), "Explicit unique-neighbor expanders", The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings, p. 73, CiteSeerX 10.1.1.103.967, doi:10.1109/SFCS.2002.1181884, ISBN 978-0-7695-1822-0, S2CID 6364755 <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.103.967" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.103.967</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Bobkov, Houdré & Tetali (2000) - Bobkov, S.; Houdré, C.; Tetali, P. (2000), "λ∞, vertex isoperimetry and concentration", Combinatorica, 20 (2): 153–172, doi:10.1007/s004930070018, S2CID 1173532 <a href="https://doi.org/10.1007%2Fs004930070018" target="_blank">https://doi.org/10.1007%2Fs004930070018</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">cf. Section 2.3 in Hoory, Linial & Wigderson (2006) - Hoory, Shlomo; Linial, Nathan; Wigderson, Avi (2006), "Expander graphs and their applications" (PDF), Bulletin of the American Mathematical Society, New Series, 43 (4): 439–561, doi:10.1090/S0273-0979-06-01126-8 <a href="http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf" target="_blank">http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">N. Alon and F. R. K. Chung, Explicit construction of linear sized tolerant networks. Discrete Math., vol. 72, pp. 15–19, 1988. <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">This definition of the spectral gap is from Section 2.3 in Hoory, Linial & Wigderson (2006) - Hoory, Shlomo; Linial, Nathan; Wigderson, Avi (2006), "Expander graphs and their applications" (PDF), Bulletin of the American Mathematical Society, New Series, 43 (4): 439–561, doi:10.1090/S0273-0979-06-01126-8 <a href="http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf" target="_blank">http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Dodziuk 1984. - Dodziuk, Jozef (1984), "Difference equations, isoperimetric inequality and transience of certain random walks", Trans. Amer. Math. Soc., 284 (2): 787–794, doi:10.2307/1999107, JSTOR 1999107 <a href="https://doi.org/10.2307%2F1999107" target="_blank">https://doi.org/10.2307%2F1999107</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Alon & Spencer 2011. - Alon, N.; Spencer, Joel H. (2011). "9.2. Eigenvalues and Expanders". The Probabilistic Method (3rd ed.). John Wiley & Sons. <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Theorem 2.4 in Hoory, Linial & Wigderson (2006) - Hoory, Shlomo; Linial, Nathan; Wigderson, Avi (2006), "Expander graphs and their applications" (PDF), Bulletin of the American Mathematical Society, New Series, 43 (4): 439–561, doi:10.1090/S0273-0979-06-01126-8 <a href="http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf" target="_blank">http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Hoory, Linial & Wigderson (2006) - Hoory, Shlomo; Linial, Nathan; Wigderson, Avi (2006), "Expander graphs and their applications" (PDF), Bulletin of the American Mathematical Society, New Series, 43 (4): 439–561, doi:10.1090/S0273-0979-06-01126-8 <a href="http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf" target="_blank">http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">B. Mohar. Isoperimetric numbers of graphs. J. Combin. Theory Ser. B, 47(3):274–291,
1989. <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">See Theorem 1 and p.156, l.1 in Bobkov, Houdré & Tetali (2000). Note that λ2 there corresponds to 2(d − λ2) of the current article (see p.153, l.5) - Bobkov, S.; Houdré, C.; Tetali, P. (2000), "λ∞, vertex isoperimetry and concentration", Combinatorica, 20 (2): 153–172, doi:10.1007/s004930070018, S2CID 1173532 <a href="https://doi.org/10.1007%2Fs004930070018" target="_blank">https://doi.org/10.1007%2Fs004930070018</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
<li id="fn:16">see, e.g., Yehudayoff (2012) - Yehudayoff, Amir (2012), "Proving expansion in three steps", ACM SIGACT News, 43 (3): 67–84, doi:10.1145/2421096.2421115, S2CID 18098370 <a href="https://doi.org/10.1145%2F2421096.2421115" target="_blank">https://doi.org/10.1145%2F2421096.2421115</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></li>
<li id="fn:17">Alon, Noga (1986). "Eigenvalues, geometric expanders, sorting in rounds, and ramsey theory". Combinatorica. 6 (3): 207–219. CiteSeerX 10.1.1.300.5945. doi:10.1007/BF02579382. S2CID 8666466. <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></li>
<li id="fn:18">see, e.g., p.9 of Goldreich (2011) - Goldreich, Oded (2011), "Basic Facts about Expander Graphs", Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation (PDF), Lecture Notes in Computer Science (Vol. 6650), vol. 6650, pp. 451–464, CiteSeerX 10.1.1.231.1388, doi:10.1007/978-3-642-22670-0_30, ISBN 978-3-642-22669-4 <a href="http://www.wisdom.weizmann.ac.il/%7Eoded/COL/expander.pdf" target="_blank">http://www.wisdom.weizmann.ac.il/%7Eoded/COL/expander.pdf</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></li>
<li id="fn:19">Theorem 2.7 of Hoory, Linial & Wigderson (2006) - Hoory, Shlomo; Linial, Nathan; Wigderson, Avi (2006), "Expander graphs and their applications" (PDF), Bulletin of the American Mathematical Society, New Series, 43 (4): 439–561, doi:10.1090/S0273-0979-06-01126-8 <a href="http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf" target="_blank">http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></li>
<li id="fn:20">Definition 5.11 of Hoory, Linial & Wigderson (2006) - Hoory, Shlomo; Linial, Nathan; Wigderson, Avi (2006), "Expander graphs and their applications" (PDF), Bulletin of the American Mathematical Society, New Series, 43 (4): 439–561, doi:10.1090/S0273-0979-06-01126-8 <a href="http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf" target="_blank">http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf</a> <a href="#fnref:20" class="footnote-back-ref">↩</a></li>
<li id="fn:21">Theorem 5.12 of Hoory, Linial & Wigderson (2006) - Hoory, Shlomo; Linial, Nathan; Wigderson, Avi (2006), "Expander graphs and their applications" (PDF), Bulletin of the American Mathematical Society, New Series, 43 (4): 439–561, doi:10.1090/S0273-0979-06-01126-8 <a href="http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf" target="_blank">http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf</a> <a href="#fnref:21" class="footnote-back-ref">↩</a></li>
<li id="fn:22">Alon, Noga (1986-06-01). "Eigenvalues and expanders". Combinatorica. 6 (2): 83–96. doi:10.1007/BF02579166. ISSN 1439-6912. S2CID 41083612. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:22" class="footnote-back-ref">↩</a></li>
<li id="fn:23">Friedman, Joel (2004-05-05). "A proof of Alon's second eigenvalue conjecture and related problems". arXiv:cs/0405020. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:23" class="footnote-back-ref">↩</a></li>
<li id="fn:24">Theorem 7.10 of Hoory, Linial & Wigderson (2006) - Hoory, Shlomo; Linial, Nathan; Wigderson, Avi (2006), "Expander graphs and their applications" (PDF), Bulletin of the American Mathematical Society, New Series, 43 (4): 439–561, doi:10.1090/S0273-0979-06-01126-8 <a href="http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf" target="_blank">http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf</a> <a href="#fnref:24" class="footnote-back-ref">↩</a></li>
<li id="fn:25">Puder, Doron (2015-08-21). "Expansion of random graphs: New proofs, new results". Inventiones Mathematicae. 201 (3): 845–908. arXiv:1212.5216. Bibcode:2015InMat.201..845P. doi:10.1007/s00222-014-0560-x. S2CID 253743928. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:25" class="footnote-back-ref">↩</a></li>
<li id="fn:26">Puder, Doron (2015). "Expansion of random graphs: new proofs, new results". Inventiones Mathematicae. 201 (3): 845–908. arXiv:1212.5216. Bibcode:2015InMat.201..845P. doi:10.1007/s00222-014-0560-x. ISSN 0020-9910. S2CID 16411939. <a href="/wiki/Inventiones_Mathematicae" target="_blank">/wiki/Inventiones_Mathematicae</a> <a href="#fnref:26" class="footnote-back-ref">↩</a></li>
<li id="fn:27">Friedman, Joel; Puder, Doron (2023). "A note on the trace method for random regular graphs". Israel Journal of Mathematics. 256: 269–282. arXiv:2006.13605. doi:10.1007/s11856-023-2497-5. S2CID 220042379. <a href="/wiki/Israel_Journal_of_Mathematics" target="_blank">/wiki/Israel_Journal_of_Mathematics</a> <a href="#fnref:27" class="footnote-back-ref">↩</a></li>
<li id="fn:28">Adam Marcus; Daniel Spielman; Nikhil Srivastava (2013). Interlacing families I: Bipartite Ramanujan graphs of all degrees (PDF). Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium. <a href="/wiki/Adam_Marcus_(mathematician)" target="_blank">/wiki/Adam_Marcus_(mathematician)</a> <a href="#fnref:28" class="footnote-back-ref">↩</a></li>
<li id="fn:29">Adam Marcus; Daniel Spielman; Nikhil Srivastava (2015). Interlacing families IV: Bipartite Ramanujan graphs of all sizes (PDF). Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium. <a href="/wiki/Adam_Marcus_(mathematician)" target="_blank">/wiki/Adam_Marcus_(mathematician)</a> <a href="#fnref:29" class="footnote-back-ref">↩</a></li>
<li id="fn:30">Huang, Jiaoyang; McKenzie, Theo; Yau, Horng-Tzer (2024). "Ramanujan Property and Edge Universality of Random Regular Graphs". arXiv:2412.20263 [math.PR]. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:30" class="footnote-back-ref">↩</a></li>
<li id="fn:31">Sloman, Leila (2025-04-18). "New Proof Settles Decades-Old Bet About Connected Networks". Quanta Magazine. Retrieved 2025-05-06. <a href="https://www.quantamagazine.org/new-proof-settles-decades-old-bet-about-connected-networks-20250418/" target="_blank">https://www.quantamagazine.org/new-proof-settles-decades-old-bet-about-connected-networks-20250418/</a> <a href="#fnref:31" class="footnote-back-ref">↩</a></li>
<li id="fn:32">Reingold, O.; Vadhan, S.; Wigderson, A. (2000). "Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors". Proceedings 41st Annual Symposium on Foundations of Computer Science. IEEE Comput. Soc. pp. 3–13. doi:10.1109/sfcs.2000.892006. ISBN 0-7695-0850-2. S2CID 420651. <a href="0-7695-0850-2" target="_blank">0-7695-0850-2</a> <a href="#fnref:32" class="footnote-back-ref">↩</a></li>
<li id="fn:33">Reingold, O.; Vadhan, S.; Wigderson, A. (2000). "Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors". Proceedings 41st Annual Symposium on Foundations of Computer Science. IEEE Comput. Soc. pp. 3–13. doi:10.1109/sfcs.2000.892006. ISBN 0-7695-0850-2. S2CID 420651. <a href="0-7695-0850-2" target="_blank">0-7695-0850-2</a> <a href="#fnref:33" class="footnote-back-ref">↩</a></li>
<li id="fn:34">Reingold, O.; Vadhan, S.; Wigderson, A. (2000). "Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors". Proceedings 41st Annual Symposium on Foundations of Computer Science. IEEE Comput. Soc. pp. 3–13. doi:10.1109/sfcs.2000.892006. ISBN 0-7695-0850-2. S2CID 420651. <a href="0-7695-0850-2" target="_blank">0-7695-0850-2</a> <a href="#fnref:34" class="footnote-back-ref">↩</a></li>
<li id="fn:35">Bilu, Yonatan; Linial, Nathan (2004-04-08). "Constructing expander graphs by 2-lifts and discrepancy vs. spectral gap". arXiv:math/0312022. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:35" class="footnote-back-ref">↩</a></li>
<li id="fn:36">Bilu, Yonatan; Linial, Nathan (2006). "Lifts, discrepancy and nearly optimal spectral gap". Combinatorica. 26 (5): 495–519. doi:10.1007/s00493-006-0029-7. ISSN 0209-9683. S2CID 14422668. <a href="/wiki/Combinatorica" target="_blank">/wiki/Combinatorica</a> <a href="#fnref:36" class="footnote-back-ref">↩</a></li>
<li id="fn:37">Adam Marcus; Daniel Spielman; Nikhil Srivastava (2013). Interlacing families I: Bipartite Ramanujan graphs of all degrees (PDF). Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium. <a href="/wiki/Adam_Marcus_(mathematician)" target="_blank">/wiki/Adam_Marcus_(mathematician)</a> <a href="#fnref:37" class="footnote-back-ref">↩</a></li>
<li id="fn:38">Adam Marcus; Daniel Spielman; Nikhil Srivastava (2015). Interlacing families IV: Bipartite Ramanujan graphs of all sizes (PDF). Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium. <a href="/wiki/Adam_Marcus_(mathematician)" target="_blank">/wiki/Adam_Marcus_(mathematician)</a> <a href="#fnref:38" class="footnote-back-ref">↩</a></li>
<li id="fn:39">Michael B. Cohen (2016). Ramanujan Graphs in Polynomial Time. Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium. arXiv:1604.03544. doi:10.1109/FOCS.2016.37. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:39" class="footnote-back-ref">↩</a></li>
<li id="fn:40">Hall, Chris; Puder, Doron; Sawin, William F. (2018). "Ramanujan coverings of graphs". Advances in Mathematics. 323: 367–410. arXiv:1506.02335. doi:10.1016/j.aim.2017.10.042. <a href="/wiki/Advances_in_Mathematics" target="_blank">/wiki/Advances_in_Mathematics</a> <a href="#fnref:40" class="footnote-back-ref">↩</a></li>
<li id="fn:41">Pinkser, M. (1973). "On the Complexity of a Concentrator". SIAM Journal on Computing. SIAM. CiteSeerX 10.1.1.393.1430. <a href="/wiki/SIAM_Journal_on_Computing" target="_blank">/wiki/SIAM_Journal_on_Computing</a> <a href="#fnref:41" class="footnote-back-ref">↩</a></li>
<li id="fn:42">Alon, N.; Roichman, Y. (1994). "Random Cayley graphs and Expanders". Random Structures and Algorithms. 5 (2). Wiley Online Library: 271–284. doi:10.1002/rsa.3240050203. <a href="https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.3240050203" target="_blank">https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.3240050203</a> <a href="#fnref:42" class="footnote-back-ref">↩</a></li>
<li id="fn:43">Alexander, Clark (2021). "On Near Optimal Spectral Expander Graphs of Fixed Size". arXiv:2110.01407 [cs.DM]. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:43" class="footnote-back-ref">↩</a></li>
<li id="fn:44">Hoory, Linial & Wigderson (2006) - Hoory, Shlomo; Linial, Nathan; Wigderson, Avi (2006), "Expander graphs and their applications" (PDF), Bulletin of the American Mathematical Society, New Series, 43 (4): 439–561, doi:10.1090/S0273-0979-06-01126-8 <a href="http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf" target="_blank">http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf</a> <a href="#fnref:44" class="footnote-back-ref">↩</a></li>
<li id="fn:45">Hoffman, A. J.; Howes, Leonard (1970). "On Eigenvalues and Colorings of Graphs, Ii". Annals of the New York Academy of Sciences. 175 (1): 238–242. Bibcode:1970NYASA.175..238H. doi:10.1111/j.1749-6632.1970.tb56474.x. ISSN 1749-6632. S2CID 85243045. <a href="https://onlinelibrary.wiley.com/doi/abs/10.1111/j.1749-6632.1970.tb56474.x" target="_blank">https://onlinelibrary.wiley.com/doi/abs/10.1111/j.1749-6632.1970.tb56474.x</a> <a href="#fnref:45" class="footnote-back-ref">↩</a></li>
<li id="fn:46">Alon, Noga; Krivelevich, Michael; Sudakov, Benny (1999-09-01). "Coloring Graphs with Sparse Neighborhoods". Journal of Combinatorial Theory. Series B. 77 (1): 73–82. doi:10.1006/jctb.1999.1910. ISSN 0095-8956. <a href="/wiki/Noga_Alon" target="_blank">/wiki/Noga_Alon</a> <a href="#fnref:46" class="footnote-back-ref">↩</a></li>
<li id="fn:47">Chung, F. R. K. (1989). "Diameters and eigenvalues". Journal of the American Mathematical Society. 2 (2): 187–196. doi:10.1090/S0894-0347-1989-0965008-X. ISSN 0894-0347. <a href="https://www.ams.org/jams/1989-02-02/S0894-0347-1989-0965008-X/" target="_blank">https://www.ams.org/jams/1989-02-02/S0894-0347-1989-0965008-X/</a> <a href="#fnref:47" class="footnote-back-ref">↩</a></li>
</ol>

Expander graph open-in-new

Expander graph