edge isoperimetric constant (thing)

The edge isoperimetric constant of a graph G=(V,E) is a measure of its rate of growth. It is defined by

ι_e(G) = inf_{F⊂V finite} |Γ_e(F)|/|F|

Examples

The square d-dimensional grid Z^d

ι_e(Z^d)=0: If we take F_m={(x₁,...,x_d): |x_i|≤m} then there are 2*d*m^d-1 edges leaving the cube F_m, but its volume is m^d. So ∀m, ι_e(Z^d) ≤ |Γ_e(F_m)| / |F_m| = 2*d*m^d-1 / m^d = 2*d/m -> 0.

The infinite binary tree B

ι_e(B)=1: If B_k is the first k levels of B, then there are 2^k-1 vertices at the last level of B_k, so 2^k vertices leave B_k. Since there are B_k=2^k-1, ι_e(B)≤1.

On the other hand, if F is any finite subset of the vertices of B, we must show at least |F| edges leave F. Indeed, suppose F is connected and has more than 1 vertex. F itself is a tree; we will show it has at least as many edges leaving it as it has vertices. Every vertex of F has degree 1 or 2 or 3. If it has degree 1, it contributes 2 edges which leave it. If it has degree 2 and is not the root, it contributes one edge which leaves it; this has no effect on the balance, so we can just "elide" it from F, replacing it by an edge, with no effect on the balance of edges leaving F - vertices in F. If it has degree 3 or is the root, it's just one vertex which connects to twice as many subtrees. So everything balances, and |Γ_e(F)|≥|F|. If F consists of more than one connected component, we just apply this argument to each component separately.

A graph with zero isoperimetric constant is called amenable. Otherwise, it's nonamenable.