Editing Expander graph (section)

==Relationships between different expansion properties==

The expansion parameters defined above are related to each other. In particular, for any {{mvar|d}}-regular graph {{mvar|G}},
:<math>h_{\text{out}}(G) \le h(G) \le d \cdot h_{\text{out}}(G).</math>
Consequently, for constant degree graphs, vertex and edge expansion are qualitatively the same.

===Cheeger inequalities===
When {{mvar|G}} is {{mvar|d}}-regular, meaning each vertex is of degree {{mvar|d}}, there is a relationship between the isoperimetric constant {{math|''h''(''G'')}} and the gap {{math|''d'' − ''λ''{{sub|2}}}} in the spectrum of the adjacency operator of {{mvar|G}}. By standard spectral graph theory, the trivial eigenvalue of the adjacency operator of a {{mvar|d}}-regular graph is {{math|1=''λ''{{sub|1}} = ''d''}} and the first non-trivial eigenvalue is {{math|''λ''{{sub|2}}}}. If {{mvar|G}} is connected, then {{math|''λ''{{sub|2}} < ''d''}}. An inequality due to Dodziuk{{Sfn|Dodziuk|1984}} and independently [[Noga Alon|Alon]] and [[Vitali Milman|Milman]]{{Sfn|Alon|Spencer|2011}} states that<ref>Theorem 2.4 in {{harvtxt|Hoory|Linial|Wigderson|2006}}</ref>
: <math>\tfrac{1}{2}(d - \lambda_2) \le h(G) \le \sqrt{2d(d - \lambda_2)}.</math>
In fact, the lower bound is tight. The lower bound is achieved in limit for the [[Hypercube graph|hypercube]] {{mvar|Q{{sub|n}}}}, where {{math|1=''h''(''G'') = 1}} and {{math|1=''d'' – ''λ''{{sub|2}} = 2}}. The upper bound is (asymptotically) achieved for a cycle, where {{math|1=''h''(''C{{sub|n}}'') = 4/''n'' = Θ(1/''n'')}} and {{math|1=''d'' – ''λ''{{sub|2}} = 2 – 2cos(2<math>\pi</math>/''n'') ≈ (2<math>\pi</math>/''n''){{sup|2}} = Θ(1/''n''{{sup|2}})}}.<ref name="Hoory 2006"/> A better bound is given in <ref>B. Mohar. Isoperimetric numbers of graphs. J. Combin. Theory Ser. B, 47(3):274–291,
1989.</ref> as 
: <math> h(G) \le \sqrt{d^2 - \lambda_2^2}.</math>
These inequalities are closely related to the [[Cheeger bound]] for [[Markov chains]] and can be seen as a discrete version of [[Cheeger constant#Cheeger.27s inequality|Cheeger's inequality]] in [[Riemannian geometry]].

Similar connections between vertex isoperimetric numbers and the spectral gap have also been studied:<ref>See Theorem 1 and p.156, l.1 in {{harvtxt|Bobkov|Houdré|Tetali|2000}}. Note that {{math|''λ''{{sub|2}}}} there corresponds to {{math|2(''d'' − ''λ''{{sub|2}})}} of the current article (see p.153, l.5)</ref>
: <math>h_{\text{out}}(G)\le \left(\sqrt{4 (d-\lambda_2)} + 1\right)^2 -1</math>
: <math>h_{\text{in}}(G) \le \sqrt{8(d-\lambda_2)}.</math>
Asymptotically speaking, the quantities {{math|{{frac|''h''{{sup|2}}|''d''}}}}, {{math|''h''{{sub|out}}}}, and {{math|''h''{{sub|in}}{{sup|2}}}} are all bounded above by the spectral gap {{math|''O''(''d'' – ''λ''{{sub|2}})}}.