#
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}\setminus A$. The edge-isoperimetric inequality in the cube tells us that if $A$ has cardinality ${2}^{d}$, 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 ${2}^{d}(n-d)$. We can regard the graph as a Cayley graph, where the group is ${\mathbb{F}}_{2}^{n}$ 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|-{\mathrm{log}}_{2}|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-\gamma )|A||S|$, then $A$ must have size at least ${2}^{\gamma |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\subset G$, and a generating set $S$ of $G$, define the edge boundary to be the set of pairs $(a,s)\in A\times S$ such that $a+s\notin A$. The precise statement proved is that if the size of the edge boundary is at most $(1-\gamma )|A||S|$, then $A$ must have size at least ${4}^{(1-1/d)\gamma |S|}$, where $d$ is the exponent of $G$ – that is, the smallest order of any element of $G$. Note that when $G={\mathbb{F}}_{2}^{n}$ , 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{|}^{\gamma}$, 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{|}^{\gamma}$ does not hold, and examples show that we have to settle for the weaker bound ${4}^{(1-1/d)\gamma |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 $\sum _{x\in Y}x=\sum _{x\in Z}x$, then $Y=Z$. Equivalently, it is a subset $X$ with a kind of linear independence property: if ${x}_{1},\dots ,{x}_{n}$ are distinct elements of $X$ and ${\u03f5}_{1},\dots ,{\u03f5}_{n}$ are coefficients taken from the set $\{-1,0,1\}$ such that $\sum _{i}{\u03f5}_{i}{x}_{i}=0$, then ${\u03f5}_{1}=\cdots ={\u03f5}_{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 ${\mathbb{F}}_{5}^{n}$, the set $\{{e}_{1},\dots ,{e}_{n},2{e}_{1},\dots ,2{e}_{n}\}$ 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 ${\mathrm{d}\mathrm{i}\mathrm{m}}_{D}(E)$ to be the size of the largest dissociated subset of $E$ and ${\mathrm{d}\mathrm{i}\mathrm{m}}_{I}(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 $\gamma >0$, we set ${P}_{\gamma}(A)$ to be the set of all group elements $g$ such that $|A\cap (A-g)|\ge \gamma |A|$. Popular difference sets play an important role in additive combinatorics. A result of Shkredov and Yekhanin states that ${\mathrm{d}\mathrm{i}\mathrm{m}}_{D}({P}_{\gamma}(A))$ is at most