Editing Expander graph (section)

==Definitions==
Intuitively, an expander graph is a finite, undirected [[multigraph]] in which every subset of the vertices that  is not "too large" has a "large" [[boundary (graph theory)|boundary]]. 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 [[component (graph theory)|connected component]] is empty. Every connected graph is an expander; however, different connected graphs have different expansion parameters. The [[complete graph]] has the best expansion property, but it has largest possible [[Degree (graph theory)|degree]]. Informally, a graph is a good expander if it has low degree and high expansion parameters.

===Edge expansion===
The ''edge expansion'' (also ''isoperimetric number'' or [[Cheeger constant (graph theory)|Cheeger constant]]) {{math|''h''(''G'')}} of a graph {{mvar|G}} on {{mvar|n}} vertices is defined as
: <math>h(G) = \min_{0 < |S| \le \frac{n}{2} } \frac{|\partial S|}{|S|},</math>
:where <math>\partial S := \{ \{ u, v \} \in E(G) \ : \ u \in S, v \notin S \},</math>
which can also be written as {{math|1=∂''S'' = ''E''(''S'', {{overline|''S''}})}}  with {{math|1={{overline|''S''}} := ''V''(''G'') \ ''S''}} the complement of {{mvar|S}} and 
:<math> E(A,B) = \{ \{ u, v \} \in E(G) \ : \ u \in A , v \in B \}</math> 
the edges between the subsets of vertices {{math|''A'',''B'' ⊆ ''V''(''G'')}}.

In the equation, the minimum is over all nonempty sets {{mvar|S}} of at most {{math|{{frac|''n''|2}}}} vertices and {{math|∂''S''}} is the ''edge boundary'' of {{mvar|S}}, i.e., the set of edges with exactly one endpoint in {{mvar|S}}.<ref>Definition 2.1 in {{harvtxt|Hoory|Linial|Wigderson|2006}}</ref>

Intuitively, 
: <math>\min {|\partial S|} = \min E({S}, \overline{S})</math>
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 {{mvar|n}} and add {{mvar|n}} edges between the two graphs by connecting their vertices one-to-one.
The minimum cut will be {{mvar|n}} but the edge expansion will be 1.

Notice that in {{math|min {{abs|∂''S''}}}}, the optimization can be equivalently done either over {{math|0 ≤ {{abs|''S''}} ≤ {{frac|''n''|2}}}} or over any non-empty subset, since  <math>E(S, \overline{S}) = E(\overline{S}, S)</math>. The same is not true for {{math|''h''(''G'')}} because of the normalization by {{math|{{abs|''S''}}}}.
If we want to write {{math|''h''(''G'')}} with an optimization over all non-empty subsets, we can rewrite it as 
: <math>h(G) = \min_{\emptyset \subsetneq S\subsetneq V(G) } \frac{E({S}, \overline{S})}{\min\{|S|, |\overline{S}|\}}.</math>

===Vertex expansion===
[[File:Vertex expansion.svg|thumb|220px|Here, a subset {{mvar|S}} of the graph {{mvar|G}} (denoted red) has 4 vertices, and 2 vertices outside the subset that are neighbors of {{mvar|S}} (denoted green). The number of neighboring vertices divided by the size of the subset is denoted
<math>|\partial_{out} S|/|S|</math>, which here is <math>2/4 = 0.5</math>.

The '''vertex expansion''' (or vertex isoperimetric number) is the minimum <math>|\partial_{out} S|/|S|</math>of all subsets of the graph {{mvar|G}} which are not empty and whose size is less than or equal to half the size of {{mvar|G}}. For this graph {{mvar|G}}, this subset {{mvar|S}} has the smallest value
<math>|\partial_{out} S|/|S|</math>, and therefore 0.5 is the vertex expansion of {{mvar|G}}.]]

The ''vertex isoperimetric number'' {{math|''h''{{sub|out}}(''G'')}} (also ''vertex expansion'' or ''magnification'') of a graph {{mvar|G}} is defined as
: <math>h_{\text{out}}(G) = \min_{0 < |S|\le \frac{n}{2}} \frac{|\partial_{\text{out}}(S)|}{|S|},</math>
where {{math|∂{{sub|out}}(''S'')}} is the ''outer boundary'' of {{mvar|S}}, i.e., the set of vertices in {{math|''V''(''G'') \ ''S''}} with at least one neighbor in {{mvar|S}}.<ref name="BobkovHoudre">{{harvtxt|Bobkov|Houdré|Tetali|2000}}</ref> In a variant of this definition (called ''unique neighbor expansion'') {{math|∂{{sub|out}}(''S'')}} is replaced by the set of vertices in {{mvar|V}} with ''exactly'' one neighbor in {{mvar|S}}.<ref name="AlonCapalbo">{{harvtxt|Alon|Capalbo|2002}}</ref>

The ''vertex isoperimetric number'' {{math|''h''{{sub|in}}(''G'')}} of a graph {{mvar|G}} is defined as
: <math>h_{\text{in}}(G) = \min_{0 < |S|\le \frac{n}{2}} \frac{|\partial_{\text{in}}(S)|}{|S|},</math>
where <math>\partial_{\text{in}}(S)</math> is the ''inner boundary'' of {{mvar|S}}, i.e., the set of vertices in {{mvar|S}} with at least one neighbor in {{math|''V''(''G'') \ ''S''}}.<ref name="BobkovHoudre" />

===Spectral expansion===
When {{mvar|G}} is [[regular graph|{{mvar|d}}-regular]], a [[linear algebra]]ic definition of expansion is possible based on the [[Eigenvalue#Eigenvalues of matrices|eigenvalues]] of the [[adjacency matrix]] {{math|1=''A'' = ''A''(''G'')}} of {{mvar|G}}, where {{mvar|A{{sub|ij}}}} is the number of edges between vertices {{mvar|i}} and {{mvar|j}}.<ref>cf. Section 2.3 in {{harvtxt|Hoory|Linial|Wigderson|2006}}</ref> Because {{mvar|A}} is [[symmetric matrix|symmetric]], the [[spectral theorem]] implies that {{mvar|A}} has {{mvar|n}} real-valued eigenvalues {{math|''λ''{{sub|1}} ≥ ''λ''{{sub|2}} ≥ … ≥ ''λ''{{sub|''n''}}}}.  It is known that all these eigenvalues are in {{math|[−''d'', ''d'']}} and more specifically, it is known that {{math|1=''λ''{{sub|''n''}} = −''d''}} if and only if {{mvar|G}} is bipartite.

More formally, we refer to an {{mvar|n}}-vertex, {{mvar|d}}-regular graph with 
:<math>\max_{i \neq 1}|\lambda_i| \leq \lambda</math> 
as an {{math|(''n'', ''d'', ''λ'')}}-''graph''. The bound given by an {{math|(''n'', ''d'', ''λ'')}}-graph on {{math|''λ''{{sub|''i''}}}} for {{math|''i'' ≠ 1}} is useful in many contexts, including the [[expander mixing lemma]].

Spectral expansion can be ''two-sided'', as above, with <math>\max_{i \neq 1}|\lambda_i| \leq \lambda</math>, or it can be ''one-sided'', with <math>\max_{i \neq 1}\lambda_i \leq \lambda</math>. 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.<ref>N. Alon and F. R. K. Chung, Explicit construction of linear sized tolerant networks. Discrete Math., vol. 72, pp. 15–19, 1988.</ref>

Because {{mvar|G}} is regular, the uniform distribution <math>u\in\R^n</math> with {{math|1=''u{{sub|i}}'' = {{frac|1|''n''}}}} for all {{math|1=''i'' = 1, …, ''n''}} is the [[stationary distribution]] of {{mvar|G}}. That is, we have {{math|1=''Au'' = ''du''}}, and {{mvar|u}} is an [[eigenvector]] of {{mvar|A}} with eigenvalue {{math|1=''λ''{{sub|1}} = ''d''}}, where {{mvar|d}} is the [[degree (graph theory)|degree]] of the vertices of {{mvar|G}}. The ''[[spectral gap]]'' of {{mvar|G}} is defined to be {{math|''d'' − ''λ''{{sub|2}}}}, and it measures the spectral expansion of the graph {{mvar|G}}.<ref>This definition of the spectral gap is from Section 2.3 in {{harvtxt|Hoory|Linial|Wigderson|2006}}</ref>

If we set
:<math>\lambda=\max\{|\lambda_2|, |\lambda_n|\}</math>
as this is the largest eigenvalue corresponding to an eigenvector [[orthogonal]] to {{mvar|u}}, it can be equivalently defined using the [[Rayleigh quotient]]:
:<math>\lambda=\max_{v \perp u , v \neq 0} \frac{\|Av\|_2}{\|v\|_2},</math>
where 
:<math>\|v\|_2=\left(\sum_{i=1}^n v_i^2\right)^{1/2}</math> 
is the [[2-norm]] of the vector <math>v\in\R^n</math>.

The normalized versions of these definitions are also widely used and more convenient in stating some results. Here one considers the matrix {{math|{{sfrac|1|''d''}}''A''}}, which is the [[Markov transition matrix]] of the graph {{mvar|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 [[Laplacian matrix]]. For [[directed graph]]s, one considers the [[singular values]] of the adjacency matrix {{mvar|A}}, which are equal to the roots of the eigenvalues of the symmetric matrix {{math|''A''{{sup|T}}''A''}}.