Editing Isoperimetric inequality (section)

== For graphs ==

{{main|Expander graph}}

In [[graph theory]], isoperimetric inequalities are at the heart of the study of [[expander graphs]], which are [[sparse graph]]s that have strong connectivity properties. Expander constructions have spawned research in pure and applied mathematics, with several applications to [[Computational complexity theory|complexity theory]], design of robust [[computer network]]s, and the theory of [[error-correcting code]]s.<ref>{{harvtxt|Hoory|Linial|Widgerson|2006}}</ref>

Isoperimetric inequalities for graphs relate the size of vertex subsets to the size of their boundary, which is usually measured by the number of edges leaving the subset (edge expansion) or by the number of neighbouring vertices (vertex expansion). For a graph <math>G</math> and a number <math>k</math>, the following are two standard isoperimetric parameters for graphs.<ref>Definitions 4.2 and 4.3 of {{harvtxt|Hoory|Linial|Widgerson|2006}}</ref>

*The edge isoperimetric parameter: <math display="block">\Phi_E(G,k)=\min_{S\subseteq V} \left\{|E(S,\overline{S})| : |S|=k \right\}</math>
*The vertex isoperimetric parameter: <math display="block">\Phi_V(G,k)=\min_{S\subseteq V} \left\{|\Gamma(S)\setminus S| : |S|=k \right\}</math>

Here <math>E(S,\overline{S})</math> denotes the set of edges leaving <math>S</math> and <math>\Gamma(S)</math> denotes the set of vertices that have a neighbour in <math>S</math>. The isoperimetric problem consists of understanding how the parameters <math>\Phi_E</math> and <math>\Phi_V</math> behave for natural families of graphs.

=== Example: Isoperimetric inequalities for hypercubes ===
The <math>d</math>-dimensional [[hypercube]] <math>Q_d</math> is the graph whose vertices are all Boolean vectors of length <math>d</math>, that is, the set <math>\{0,1\}^d</math>. Two such vectors are connected by an edge in <math>Q_d</math> if they are equal up to a single bit flip, that is, their [[Hamming distance]] is exactly one.
The following are the isoperimetric inequalities for the Boolean hypercube.<ref>See {{harvtxt|Bollobás|1986}} and Section 4 in {{harvtxt|Hoory|Linial|Widgerson|2006}}</ref>

==== Edge isoperimetric inequality ====
The edge isoperimetric inequality of the hypercube is <math>\Phi_E(Q_d,k) \geq k(d-\log_2 k)</math>. This bound is tight, as is witnessed by each set <math>S</math> that is the set of vertices of any subcube of <math>Q_d</math>.

==== Vertex isoperimetric inequality ====
Harper's theorem<ref>Cf. {{harvtxt|Calabro|2004}} or {{harvtxt|Bollobás|1986}}</ref> says that ''Hamming balls'' have the smallest vertex boundary among all sets of a given size. Hamming balls are sets that contain all points of [[Hamming weight]] at most <math>r</math> and no points of Hamming weight larger than <math>r+1</math> for some integer <math>r</math>. This theorem implies that any set <math>S\subseteq V</math> with

:<math>|S|\geq\sum_{i=0}^{r} {d\choose i}</math>

satisfies

:<math>|S\cup\Gamma(S)|\geq \sum_{i=0}^{r+1}{d\choose i}.</math><ref>cf. {{harvtxt|Leader|1991}}</ref>

As a special case, consider set sizes <math>k=|S|</math> of the form

:<math>k={d \choose 0} + {d \choose 1} + \dots + {d \choose r}</math>

for some integer <math>r</math>. Then the above implies that the exact vertex isoperimetric parameter is

:<math>\Phi_V(Q_d,k) = {d\choose r+1}.</math><ref>Also stated in {{harvtxt|Hoory|Linial|Widgerson|2006}}</ref>