Editing Expander graph (section)

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