On Isoperimetric Stability

The edge isoperimetric inequality in the discrete cube specifies, for each pair of integers $m$ and $n$, the minimum size $g_n(m)$ of the edge boundary of an $m$-element subset of $\{0,1\}^{n}$; the extremal families (up to automorphisms of the discrete cube) are initial segments of the lexicographic ordering on $\{0,1\}^n$. We show that for any $m$-element subset $\mathcal{F} \subset \{0,1\}^n$ and any integer $l$, if the edge boundary of $\mathcal{F}$ has size at most $g_n(...

Let $G$ be a finite abelian abelian group of exponent $m\ge 2$. For subsets $A,S\subset G$, denote by $\partial_S(A)$ the number of edges from $A$ to its complement $G\setminus A$ in the directed Cayley graph, induced by $S$ on $G$. We show that if $S$ generates $G$, and $A$ is non-empty, then $$ \partial_S(A) \ge \frac{e}m\,|A|\ln\frac{|G|}{|A|}. $$ Here the coefficient $e=2.718...$ is best possible and cannot be replaced with a number larger than $e$. For homocyclic g...

For a subset A of a finite abelian group G we define Sigma(A)={sum_{a\in B}a:B\subset A}. In the case that Sigma(A) has trivial stabiliser, one may deduce that the size of Sigma(A) is at least quadratic in |A|; the bound |Sigma(A)|>= |A|^{2}/64 has recently been obtained by De Vos, Goddyn, Mohar and Samal. We improve this bound to the asymptotically best possible result |Sigma(A)|>= (1/4-o(1))|A|^{2}. We also study a related problem in which A is any subset of Z_{n} with al...

Let A be a subset of an abelian group G. We say that A is sum-free if there do not exist x,y and z in A satisfying x + y = z. We determine, for any G, the cardinality of the largest sum-free subset of G. This equals c(G)|G| where c(G) is a constant depending on G and lying in the interval [2/7,1/2]. We also estimate the number of sum-free subsets of G. It turns out that log_2 of this number is c(G)|G| + o(|G|), which is tight up to the o-term. For certain abelian groups, ...

Let $A=\{a_1,a_2,\dots, a_m\}$ be a subset of a finite abelian group $G$. We call $A$ {\it $t$-independent} in $G$, if whenever $$\lambda_1a_1+\lambda_2a_2+\cdots +\lambda_m a_m=0$$ for some integers $\lambda_1, \lambda_2, \dots , \lambda_m$ with $$|\lambda_1|+|\lambda_2|+\cdots +|\lambda_m| \leq t,$$ we have $\lambda_1=\lambda_2= \cdots = \lambda_m=0$, and we say that $A$ is {\it $s$-spanning} in $G$, if every element $g$ of $G$ can be written as $$g=\lambda_1a_1+\lambda_2a_...

We present proofs of the basic isopermetric structure theory, obtaining some new simplified proofs. As an application, we obtain simple descriptions for subsets $S$ of an abelian group with $|kS|\le k|S|-k+1$ or $|kS-rS|- (k+r)|S|,$ where $1\le r \le k.$ These results may be applied to several questions in Combinatorics and Additive Combinatorics (Frobenius Problem, Waring's problem in finite fields and Cayley graphs with a big diameter, ....).

We prove an arithmetic regularity lemma for stable subsets of finite abelian groups, generalising our previous result for high-dimensional vector spaces over finite fields of prime order. A qualitative version of this generalisation was recently obtained by the first author in joint work with Conant and Pillay, using model-theoretic techniques. In contrast, the approach in the present paper is highly quantitative and relies on several key ingredients from arithmetic combinato...

Given a finite subset A of an abelian group G, we study the set k \wedge A of all sums of k distinct elements of A. In this paper, we prove that |k \wedge A| >= |A| for all k in {2,...,|A|-2}, unless k is in {2,|A|-2} and A is a coset of an elementary 2-subgroup of G. Furthermore, we characterize those finite subsets A of G for which |k \wedge A| = |A| for some k in {2,...,|A|-2}. This result answers a question of Diderrich. Our proof relies on an elementary property of prope...

We show that any connected Cayley graph $\Gamma$ on an Abelian group of order $2n$ and degree $\tilde{\Omega}(\log n)$ has at most $2^{n+1}(1 + o(1))$ independent sets. This bound is tight up to to the $o(1)$ term when $\Gamma$ is bipartite. Our proof is based on Sapozhenko's graph container method and uses the Pl\"{u}nnecke-Rusza-Petridis inequality from additive combinatorics.

In an abelian group G, a more sums than differences (MSTD) set is a subset A of G such that |A+A|>|A-A|. We provide asymptotics for the number of MSTD sets in finite abelian groups, extending previous results of Nathanson. The proof contains an application of a recently resolved conjecture of Alon and Kahn on the number of independent sets in a regular graph.