On Isoperimetric Stability

- University of Haifa at Oranim
- More about Vsevolod Lev

### Editorial introduction

On Isoperimetric Stability, Discrete Analysis 2018:14, 11 pp.

Let A be a subset of the Hamming cube {0,1}n. If we regard the cube as a graph in the usual way, by joining two points x and y if they differ in exactly one coordinate, then the *edge boundary* of A is defined to be the set of all edges that join a point in A to a point in its complement {0,1}n∖A. The edge-isoperimetric inequality in the cube tells us that if A has cardinality 2d, then the size of the edge boundary of A is minimized when A is a subcube of dimension d, in which case the number of edges between A and its complement is 2d(n−d). We can regard the graph as a Cayley graph, where the group is Fn2 and the generating set S consists of the n standard basis vectors. Then we find that the size of the edge boundary is always at least |A|(|S|−log2|A|), an inequality that continues to hold when the size of A is not a power of 2. As a consequence, if the size of the edge boundary is at most (1−γ)|A||S|, then A must have size at least 2γ|S|.

The purpose of this paper is to prove a similar statement for Abelian groups in general. Given an Abelian group G, a subset A⊂G, and a generating set S of G, define the edge boundary to be the set of pairs (a,s)∈A×S such that a+s∉A. The precise statement proved is that if the size of the edge boundary is at most (1−γ)|A||S|, then A must have size at least 4(1−1/d)γ|S|, where d is the exponent of G – that is, the smallest order of any element of G. Note that when G=Fn2 , then d=2, and we recover the statement above. Note also that in this case we can rewrite the lower bound for the size of A as |G|γ, 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 |G|γ does not hold, and examples show that we have to settle for the weaker bound 4(1−1/d)γ|S| 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 X of an Abelian group G with the property that if Y and Z are finite subsets of X with ∑x∈Yx=∑x∈Zx, then Y=Z. Equivalently, it is a subset X with a kind of linear independence property: if x1,…,xn are distinct elements of X and ϵ1,…,ϵn are coefficients taken from the set {−1,0,1} such that ∑iϵixi=0, then ϵ1=⋯=ϵn=0. For groups of exponent 2 or 3, all possible integer coefficients can be replaced by ones that belong to the set {−1,0,1}, 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 Fn5, the set {e1,…,en,2e1,…,2en} is dissociated but not independent.

These notions lead naturally to notions of dimension for subsets of Abelian groups: given a finite subset E, we define dimD(E) to be the size of the largest dissociated subset of E and dimI(E) 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 A, which is defined as follows. Given a parameter γ>0, we set Pγ(A) to be the set of all group elements g such that |A∩(A−g)|≥γ|A|. Popular difference sets play an important role in additive combinatorics. A result of Shkredov and Yekhanin states that dimD(Pγ(A)) is at most Cγ−1log|A|, for some absolute constant C. (To see why the factor γ−1 is necessary, consider an arbitrary union of γ−1 subspaces of Fn2 of the same dimension.) In this paper it is shown that if p is the smallest order of a non-zero element of G, then dimI(Pγ(A))≤(2(1−1/p))−1γ−1log2|A|, which is refined to dimI(Pγ(A))≤γ−1log3|A| in the special case p=3. These estimates are sharp when G is homocyclic of exponent p=2 or 3, when the two notions of dimension coincide.

One of the proof ingredients in the paper is a result that stands on its own. A *down-set* in Zn≥0 is a subset A with the property that if x∈A and yi≤xi for every i, then y∈A. The paper gives an upper bound of 12log2|A| for the average number of non-zero coordinates of a vector in a down-set. It is a simple exercise to prove that this bound is sharp.