Back in high school, we have all learned and loved the isoperimetric inequality: “If one wants to enclose a region of area on the plane, one needs a rope of length at least .” or equivalently, given bounded open, we always have
Of course this generalizes to :
Theorem: Given any open set , we have
Here is the volume of the unit n-ball. Note that the inequality is sharp for balls in .
One nature question to ask should be: for which other kind of spaces do we have such an inequality. i.e. when can we lower bound the volume of the boundary by in terms of the volume of the open set? If such inequality exists, how does the lower bound depend on the volume of the set?
I recently learned to produce such bounds on groups:
Let be a discrete group, fix a set of generators and let be its Cayley graph, equipped with the word metric .
Let be the cardinality of the ball of radius around the identity.
For any set , we define i.e. points that’s not in but there is an edge in the Cayley graph connecting it to some point in .
Theorem:For any group with the property that , then for any set with ,
i.e. If the volume of balls grow (w.r.t. radius) as fast as what we have in , then we can lower bound the size of boundary any open set in terms of its volume just like what we have in .
Proof: We make use of the fact that right multiplications by elements of the group are isometries on Cayley graph.
Let , so we have .
For each element , we look at how many elements of went outside of i.e. . (Here the idea being the size of the boundary can be lower bounded in terms of the length of the translation vector and the volume shifted outside the set. Hence we are interested in finding an element that’s not too far away from the identity but shifts a large volume of outside of .)
The average value of as varies in the ball is:
The sum part is counting the elements of that’s translated outside by then sum over all , this is same as first fixing any , count how many sends outside , and sum over all ( In fact this is just Fubini, where we exchange the order of two summations ). “how mant sends outside of ” is merely .
Hence the average is
But we know , hence is at least .
Now we can pick some where (at least as large as average).
Since has norm at most , we can find a word .
For any , since and , there must be some s.t. and .
Hence , .
We deduce that i.e. a union of copies of .
Since , we have . , hence we have
Establishes the claim.
Remark: The same argument carries through as long as we have a lower bound on the volume of balls, not necessarily polynomial. For example, on expander graphs, the volume of balls grow exponentially: , then trancing through the argument we get bound
Which is a very strong isoperimetric inequality. However in fact the sharp bound for expanders is . But to get that one needs to use more information of the expander than merely the volume of balls.
On the same vein, we can also prove a version on Lie groups:
Theorem:Let be a Lie group, be a left invariant metric on . If then for any open set with no more than half of the volume of ,
Note that to satisfy the condition , our Lie group must be at least n-dimensional since if not the condition would fail for small balls. might be strictly larger than the dimension of the manifold depending on how ‘neigatively curved’ the manifold is in large scale.
Sketch of proof: As above, take a ball twice the size of the set around the identity, say it’s . Now we consider all left translates of the set by element in . In average an element shifts at least half of outside of . Pick element where is above average.
Let be a unit speed geodesic connecting to . Consider the union of left translates of by elements in , this must contain all of since for any the segment must cross the boundary of , i.e. there is where , hence
But since the geodesic has derivative , the n-dimensional volume of the union of those translates is at most .
Now since we have growth condition
Conbine the two inequalities we obtain
Establishes the theorem.
Remark: In general, this argument produces a lower bound on the size of the boundary in terms of the volume of the set as long as:
1. There is a way to ‘continuously translate’ the set by elements in the space.
2. We have a lower bound on the growth of balls in terms of radius.
The key observation is that the translated set minus the original set is always contained in a ‘flattened cylinder’ of the boundary in direction of the translate, which then has volume controlled by the boundary size and the length of the translating element. Because of this, the constant is almost never strict as the difference (translate subtract original) can never be the whole cylinder (in case of a ball, this difference is a bit more than half of the cylinder).
5 thoughts on “Isoperimetric inequality on groups”
The last theorem for Lie group should be for bounded U? Is there a general theorem for noncompact Riemannian manifolds with certain curvature condition?
For the argument I think one only need the volume of U is no more than 1/2 the volume of the whole Lie group. (Otherwise there is no ball with twice the volume) So you are right, I should put a condition (in fact on both cases) that the size of the open set cannot be more than 1/2 the total size of the space. ^_^ thanks
However, it does make sense to only consider those sets since the boundary of the complement is essentially the boundary of the set, so of course one should bound the size of the boundary by the smaller set it encloses.
To the second question, even manifolds with constant negative curvature can have thin Margulis tubes, hence forming an open set with boundary only cutting through the tubes will give large volume with arbitrarily small boundary. perhaps, after lifting to the universal cover something would hold.
This is so algebraic for you Conan…good to see it! :)
[…] Isoperimetric inequality on groups […]
thanks for the very nice post! Do you know who is(are) the author(s) of the very nice “probabilistic” argument giving the isoperimetric inequality on Cayley graphs? Or simply a bibliographic reference for it?