display | more...

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

ιe(G) = infF⊂V finitee(F)|/|F|
where Γe(F) is the number of edges {f,g}∈E with f∈F and g∉F.


The square d-dimensional grid Zd
ιe(Zd)=0: If we take Fm={(x1,...,xd): |xi|≤m} then there are 2*d*md-1 edges leaving the cube Fm, but its volume is md. So m, ιe(Zd) ≤ |Γe(Fm)| / |Fm| = 2*d*md-1 / md = 2*d/m -> 0.
The infinite binary tree B
ιe(B)=1: If Bk is the first k levels of B, then there are 2k-1 vertices at the last level of Bk, so 2k vertices leave Bk. Since there are Bk=2k-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.

Log in or register to write something here or to contact authors.