Cheeger constant (graph theory)

<h2 id="definition">Definition</h2>
Let G be an undirected finite graph with vertex set V(G) and edge set E(G). For a collection of vertices A ⊆ V(G), let ∂A denote the collection of all edges going from a vertex in A to a vertex outside of A (sometimes called the edge boundary of A):

∂
        A
        :=
        {
        {
        x
        ,
        y
        }
        ∈
        E
        (
        G
        )
         
        :
         
        x
        ∈
        A
        ,
        y
        ∈
        V
        (
        G
        )
        ∖
        A
        }
        .
      
    
    {\displaystyle \partial A:=\{\{x,y\}\in E(G)\ :\ x\in A,y\in V(G)\setminus A\}.}

Note that the edges are unordered, i.e., 
 
 
 
 {
 x
 ,
 y
 }
 =
 {
 y
 ,
 x
 }
 
 
 {\displaystyle \{x,y\}=\{y,x\}}
 
. The Cheeger constant of G, denoted h(G), is defined by<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a>

h
 (
 G
 )
 :=
 min
 
 {
 
 
 
 
 
 |
 
 ∂
 A
 
 |
 
 
 
 
 |
 
 A
 
 |
 
 
 
 
  
 :
  
 A
 ⊆
 V
 (
 G
 )
 ,
 0
 <
 
 |
 
 A
 
 |
 
 ≤
 
 
 
 1
 2
 
 
 
 
 |
 
 V
 (
 G
 )
 
 |
 
 
 }
 
 .
 
 
 {\displaystyle h(G):=\min \left\{{\frac {|\partial A|}{|A|}}\ :\ A\subseteq V(G),0<|A|\leq {\tfrac {1}{2}}|V(G)|\right\}.}

The Cheeger constant is strictly positive <a href="/facts/If_and_only_if/bYSxGJ66">if and only if</a> G is a <a href="/facts/Connectivity_(graph_theory)/FSNjsYhz">connected graph</a>. Intuitively, if the Cheeger constant is small but positive, then there exists a "bottleneck", in the sense that there are two "large" sets of vertices with "few" links (edges) between them. The Cheeger constant is "large" if any possible division of the vertex set into two subsets has "many" links between those two subsets.

<h2 id="example-computer-networking">Example: computer networking</h2>

In applications to theoretical computer science, one wishes to devise network configurations for which the Cheeger constant is high (at least, bounded away from zero) even when |V(G)| (the number of computers in the network) is large.
For example, consider a <a href="/facts/Ring_network/GDnXYWDv">ring network</a> of N ≥ 3 computers, thought of as a graph GN. Number the computers 1, 2, ..., N clockwise around the ring. Mathematically, the vertex set and the edge set are given by:

V
                (
                
                  G
                  
                    N
                  
                
                )
              
              
                
                =
                {
                1
                ,
                2
                ,
                ⋯
                ,
                N
                −
                1
                ,
                N
                }
              
            
            
              
                E
                (
                
                  G
                  
                    N
                  
                
                )
              
              
                
                =
                
                  
                    {
                  
                
                {
                1
                ,
                2
                }
                ,
                {
                2
                ,
                3
                }
                ,
                ⋯
                ,
                {
                N
                −
                1
                ,
                N
                }
                ,
                {
                N
                ,
                1
                }
                
                  
                    }
                  
                
              
            
          
        
      
    
    {\displaystyle {\begin{aligned}V(G_{N})&=\{1,2,\cdots ,N-1,N\}\\E(G_{N})&={\big \{}\{1,2\},\{2,3\},\cdots ,\{N-1,N\},\{N,1\}{\big \}}\end{aligned}}}

Take A to be a collection of 
 
 
 
 
 ⌊
 
 
 
 N
 2
 
 
 
 ⌋
 
 
 
 {\displaystyle \left\lfloor {\tfrac {N}{2}}\right\rfloor }
 
 of these computers in a connected chain:

A
        =
        
          {
          
            1
            ,
            2
            ,
            ⋯
            ,
            
              ⌊
              
                
                  
                    N
                    2
                  
                
              
              ⌋
            
          
          }
        
        .
      
    
    {\displaystyle A=\left\{1,2,\cdots ,\left\lfloor {\tfrac {N}{2}}\right\rfloor \right\}.}

So,

∂
        A
        =
        
          {
          
            
              {
              
                
                  ⌊
                  
                    
                      
                        N
                        2
                      
                    
                  
                  ⌋
                
                ,
                
                  ⌊
                  
                    
                      
                        N
                        2
                      
                    
                  
                  ⌋
                
                +
                1
              
              }
            
            ,
            {
            N
            ,
            1
            }
          
          }
        
        ,
      
    
    {\displaystyle \partial A=\left\{\left\{\left\lfloor {\tfrac {N}{2}}\right\rfloor ,\left\lfloor {\tfrac {N}{2}}\right\rfloor +1\right\},\{N,1\}\right\},}

and

|
              
              ∂
              A
              
                |
              
            
            
              
                |
              
              A
              
                |
              
            
          
        
        =
        
          
            2
            
              ⌊
              
                
                  
                    N
                    2
                  
                
              
              ⌋
            
          
        
        →
        0
        
          
             as 
          
        
        N
        →
        ∞
        .
      
    
    {\displaystyle {\frac {|\partial A|}{|A|}}={\frac {2}{\left\lfloor {\tfrac {N}{2}}\right\rfloor }}\to 0{\mbox{ as }}N\to \infty .}

This example provides an upper bound for the Cheeger constant h(GN), which also tends to zero as N → ∞. Consequently, we would regard a ring network as highly "bottlenecked" for large N, and this is highly undesirable in practical terms. We would only need one of the computers on the ring to fail, and network performance would be greatly reduced. If two non-adjacent computers were to fail, the network would split into two disconnected components.

<h2 id="cheeger-inequalities">Cheeger Inequalities</h2>
The Cheeger constant is especially important in the context of <a href="/facts/Expander_graphs/21stncb0">expander graphs</a> as it is a way to measure the edge expansion of a graph. The so-called <a href="/facts/Expander_graph/21stncb0">Cheeger inequalities</a> relate the eigenvalue gap of a graph with its Cheeger constant. More explicitly

2
        h
        (
        G
        )
        ≥
        λ
        ≥
        
          
            
              
                h
                
                  2
                
              
              (
              G
              )
            
            
              2
              Δ
              (
              G
              )
            
          
        
      
    
    {\displaystyle 2h(G)\geq \lambda \geq {\frac {h^{2}(G)}{2\Delta (G)}}}

in which 
 
 
 
 Δ
 (
 G
 )
 
 
 {\displaystyle \Delta (G)}
 
 is the maximum degree for the nodes in 
 
 
 
 G
 
 
 {\displaystyle G}
 
 and 
 
 
 
 λ
 
 
 {\displaystyle \lambda }
 
 is the <a href="/facts/Spectral_gap/jQNDusvk">spectral gap</a> of the <a href="/facts/Laplacian_matrix/Iwea2mm9">Laplacian matrix</a> of the graph.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> The Cheeger inequality is a fundamental result and motivation for <a href="/facts/Spectral_graph_theory/tBttgGTh">spectral graph theory</a>.

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Spectral_graph_theory/tBttgGTh">Spectral graph theory</a></li>
<li><a href="/facts/Algebraic_connectivity/z7kP4K3s">Algebraic connectivity</a></li>
<li><a href="/facts/Cheeger_bound/sxLwSCyK">Cheeger bound</a></li>
<li><a href="/facts/Conductance_(graph_theory)/y29dPtPz">Conductance</a></li>
<li><a href="/facts/Connectivity_(graph_theory)/FSNjsYhz">Connectivity</a></li>
<li><a href="/facts/Expander_graph/21stncb0">Expander graph</a></li></ul>
<h2 id="notes">Notes</h2>

<ul><li><a href="/facts/Bojan_Mohar/5Djly8Ax">Mohar, Bojan</a> (1989). <a href="https://doi.org/10.1016%2F0095-8956%2889%2990029-4">"Isoperimetric numbers of graphs"</a>. Journal of Combinatorial Theory, Series B. 47 (3): 274–291. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0095-8956%2889%2990029-4">10.1016/0095-8956(89)90029-4</a>.</li>
<li>Montenegro, Ravi; Tetali, Prasad (2006). "Mathematical Aspects of Mixing Times in Markov Chains". Foundations and Trends in Theoretical Computer Science. 1 (3): 237–354. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1561%2F0400000003">10.1561/0400000003</a>. <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/1551-305X">1551-305X</a>.</li>
<li>Donetti, Luca; Neri, Franco; Muñoz, Miguel A (2006-08-07). "Optimal network topologies: expanders, cages, Ramanujan graphs, entangled networks and all that". Journal of Statistical Mechanics: Theory and Experiment. 2006 (08): P08007 – P08007. <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/cond-mat/0605565">cond-mat/0605565</a>. <a href="/facts/Bibcode_(identifier)/9HtdQSGB">Bibcode</a>:<a href="https://ui.adsabs.harvard.edu/abs/2006JSMTE..08..007D">2006JSMTE..08..007D</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1088%2F1742-5468%2F2006%2F08%2FP08007">10.1088/1742-5468/2006/08/P08007</a>. <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/1742-5468">1742-5468</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:16192273">16192273</a>.</li>
<li>Lackenby, Marc (2006). "Heegaard splittings, the virtually Haken conjecture and Property (τ)". Inventiones mathematicae. 164 (2): 317–359. <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/math/0205327">math/0205327</a>. <a href="/facts/Bibcode_(identifier)/9HtdQSGB">Bibcode</a>:<a href="https://ui.adsabs.harvard.edu/abs/2006InMat.164..317L">2006InMat.164..317L</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2Fs00222-005-0480-x">10.1007/s00222-005-0480-x</a>. <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/0020-9910">0020-9910</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:12847770">12847770</a>.</li></ul>

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

<ol>
<li id="fn:1">Mohar 1989, pp. 274–291. - Mohar, Bojan (1989). "Isoperimetric numbers of graphs". Journal of Combinatorial Theory, Series B. 47 (3): 274–291. doi:10.1016/0095-8956(89)90029-4. <a href="https://doi.org/10.1016%2F0095-8956%2889%2990029-4" target="_blank">https://doi.org/10.1016%2F0095-8956%2889%2990029-4</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Montenegro & Tetali 2006, pp. 237–354. - Montenegro, Ravi; Tetali, Prasad (2006). "Mathematical Aspects of Mixing Times in Markov Chains". Foundations and Trends in Theoretical Computer Science. 1 (3): 237–354. doi:10.1561/0400000003. ISSN 1551-305X. <a href="https://doi.org/10.1561%2F0400000003" target="_blank">https://doi.org/10.1561%2F0400000003</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
</ol>

Cheeger constant (graph theory) open-in-new

Cheeger constant (graph theory)