On Isoperimetric Stability
Abstract
We show that a nonempty subset of an abelian group with a small edge boundary must be large; in particular, if $A$ and $S$ are finite, nonempty subsets of an abelian group such that $S$ is independent, and the edge boundary of $A$ with respect to $S$ does not exceed $(1\gamma)SA$ with a real $\gamma\in(0,1]$, then $A \ge 4^{(11/d)\gamma 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 \subset \mathbb Z^n$ is a finite, nonempty downset then, denoting by $w(a)$ the number of nonzero components of the vector $a\in A$, we have \[\frac1{A} \sum_{a\in A} w(a) \le \frac12\, \log_2 A.\]
 Publication:

arXiv eprints
 Pub Date:
 September 2017
 arXiv:
 arXiv:1709.05539
 Bibcode:
 2017arXiv170905539L
 Keywords:

 Mathematics  Combinatorics;
 Mathematics  Number Theory