On Isoperimetric Stability
On Isoperimetric Stability, Discrete Analysis 2018:14, 11 pp.
Let be a subset of the Hamming cube . If we regard the cube as a graph in the usual way, by joining two points and if they differ in exactly one coordinate, then the edge boundary of is defined to be the set of all edges that join a point in to a point in its complement . The edge-isoperimetric inequality in the cube tells us that if has cardinality , then the size of the edge boundary of is minimized when is a subcube of dimension , in which case the number of edges between and its complement is . We can regard the graph as a Cayley graph, where the group is and the generating set consists of the standard basis vectors. Then we find that the size of the edge boundary is always at least , an inequality that continues to hold when the size of is not a power of 2. As a consequence, if the size of the edge boundary is at most , then must have size at least .
The purpose of this paper is to prove a similar statement for Abelian groups in general. Given an Abelian group , a subset , and a generating set of , define the edge boundary to be the set of pairs such that . The precise statement proved is that if the size of the edge boundary is at most , then must have size at least , where is the exponent of – that is, the smallest order of any element of . Note that when , then , and we recover the statement above. Note also that in this case we can rewrite the lower bound for the size of as , a bound that is shown to be valid for groups of exponent 3 or 4 as well. However, for larger exponents the lower bound of does not hold, and examples show that we have to settle for the weaker bound proved in this paper.
The reason that groups of low exponent are a special case is connected with the notion of a dissociated set, which is a subset of an Abelian group with the property that if and are finite subsets of with , then . Equivalently, it is a subset with a kind of linear independence property: if are distinct elements of and are coefficients taken from the set such that , then . For groups of exponent 2 or 3, all possible integer coefficients can be replaced by ones that belong to the set , so this is just normal independence over the integers (and therefore, when these groups are considered as vector spaces, linear independence), but for groups of higher exponent that ceases to be the case. For example, in the group , the set is dissociated but not independent.
These notions lead naturally to notions of dimension for subsets of Abelian groups: given a finite subset , we define to be the size of the largest dissociated subset of and to be the size of the largest independent subset. A corollary of the main results of this paper is a sharp bound for the dimension of the popular difference set of a set , which is defined as follows. Given a parameter , we set to be the set of all group elements such that . Popular difference sets play an important role in additive combinatorics. A result of Shkredov and Yekhanin states that is at most