Editing Expander graph (section)

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