2017/09/16 by Lev, Vsevolod F.
#Combinatorics (math.CO) #FOS: Mathematics #Number Theory (math.NT)
paper · doi:10.48550/arxiv.1709.05539
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-γ)|S||A| with a real γ∈(0,1], then |A| ≥ 4(1-1/d)γ|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 ⊂ \mathbb Zn is a finite, non-empty downset then, denoting by w(a) the number of non-zero components of the vector a∈ A, we have \frac1|A| ∑a∈ A w(a) ≤ \frac12 log2 |A|.