An Isoperimetric Stability Problem

Vsevolod F. Lev speaks at the Workshop on Additive Combinatorics held at the Center of Mathematical Sciences and Applications in October, 2017.

Abstract: We show that a non-empty subset of an abelian group with a small edge boundary must be large; in particular, if $A$ and $S$ are finite, non-empty subsets of an abelian group such that $S$ is independent, and the edge boundary of $A$ with respect to $S$ does not exceed $(1-c)|S||A|$ with a real $c\in(0,1]$, then $|A|\ge4^{(1-1/d)c|S|}$, where $d$ is the smallest order of an element of $S$. Here the constant $4$ is best possible.

As a corollary, we derive an upper bound for the size of the largest independent subset of the set of popular differences of a finite subset of an abelian group. For groups of exponent $2$ and $3$, our bound translates into a sharp estimate for the additive dimension of the popular difference set.

We also prove, as an auxiliary result, the following estimate of possible independent interest: if $A\subseteq{\mathbb Z}^n$ is a finite, non-empty downset, then, denoting by $w(z)$ the number of non-zero components of the vector $z\in\mathbb{Z}^n$, we have $$ \frac1{|A|} \sum_{a\in A} w(a) \le \frac12\, \log_2 |A|. $$