Counting sum-free sets in Abelian groups

Introduction

An important trend in Combinatorics in recent years has been the formulation and proof of various ‘sparse analogues’ of classical extremal results in Graph Theory and Additive Combinatorics. Due to the recent breakthroughs of Conlon and Gowers and Schacht , many such theorems, e.g., the theorems of Turán and Erdős and Stone in extremal graph theory, and the theorem of Szemerédi on arithmetic progressions, are now known to extend to sparse random sets. For structural and enumerative results, such as the theorem of Kolaitis, Prömel and Rotshchild which states that almost all $K_{r+1}$-free graphs are $r$-colorable, perhaps the most natural sparse analogue is a corresponding statement about subsets of a given fixed size $m$, whenever $m$ is not too small. In this paper, we prove such a result in the context of sum-free subsets of Abelian groups and provide a general framework for solving problems of this type. To be precise, we obtain a sparse analogue of a result of Green and Ruzsa , which describes the structure of a typical sum-free subset of an Abelian group.

For problems of the type we are considering, results are known only in a few special cases. Most notably, Osthus, Prömel and Taraz , confirming (and strengthening) a conjecture of Prömel and Steger , proved that if $m\geqslant\big(\frac{\sqrt{3}}{4}+\varepsilon\big)n^{3/2}\sqrt{\log n}$ then almost all triangle-free graphs with $m$ edges are bipartite; moreover, the constant $\sqrt{3}/4$ is best possible. This result can be seen as a sparse version of the classical theorem of Erdős, Kleitman and Rothschild , which states that almost all triangle-free graphs are bipartite. A similarly sharp result was proved by Friedgut, Rödl, Ruciński and Tetali for the existence of monochromatic triangles in two-colourings of $G_{n,p}$. It is an interesting open problem to prove such a sharp threshold in the setting of Theorem 1.1, below.

A set $A\subseteq G$, where $G$ is an Abelian group, is said to be sum-free if $(A+A)\cap A=\emptyset$, or equivalently, if there is no solution to the equation $x+y=z$ with $x,y,z\in A$. Sum-free subsets of Abelian groups are central objects of interest in Additive Combinatorics, and have been studied intensively in recent years. The main questions are as follows: What are the largest sum-free subsets of $G$? How many sum-free sets are there? And what does a typical such set look like? Over forty years ago, Diananda and Yap determined the maximum density $\mu(G)$ of a sum-free set in $G$ whenever $|G|$ has a prime factor $q\not\equiv 1\pmod{3}$, but it was not until 2005 that Green and Ruzsa completely solved this extremal question for all finite Abelian groups. On the second and third questions, Lev, Łuczak and Schoen and Sapozhenko determined the asymptotic number of sum-free subsets in an Abelian group of even order by showing that almost all such sets We say that almost all sets in a family $\mathcal{F}$ of subsets of $G$ satisfy some property $\mathcal{P}$ if the ratio of the number of sets in $\mathcal{F}$ that have $\mathcal{P}$ to the number of all sets in $\mathcal{F}$ tends to $1$ as $|G|$ tends to infinity. lie in the complement of a subgroup of index $2$. Green and Ruzsa extended this result to Abelian groups which have a prime factor $q\equiv 2\pmod{3}$, and showed also that a general finite Abelian group $G$ has $2^{(1+o(1))\mu(G)|G|}$ sum-free subsets.

For every prime $q\equiv 2\pmod{3}$, there exists a constant $C(q)>0$ such that the following holds. Let $G$ be an Abelian group of Type $I(q)$ and order $n$, and let $m\geqslant C(q)\sqrt{n\log n}$. Then almost every sum-free subset of $G$ of size $m$ is contained in a maximum-size sum-free subset of $G$, and hence

as $n\to\infty$, where $\lambda_{q}=1$ if $q=2$ and $\lambda_{q}=1/2$ otherwise.

Although the factor $\lambda_{q}\cdot\#\{\text{elements of }G\text{of order }q\}$ above may appear mysterious, it is a natural consequence of the characterization of maximum-size sum-free sets in groups of Type I, see Theorem 6.2. We remark that the lower bound $m\geqslant C(q)\sqrt{n\log n}$ is sharp up to a constant factor, since there are at least $(n/2)\big(\mu(G)n-3m\big)^{m-1}/(m-1)!$ sum-free subsets of $G$ which contain exactly one element outside a given maximum-size sum-free subset of $G$, and this is larger than $m^{1/5}{\mu(G)n\choose m}$ if $m\leqslant\frac{1}{5}\sqrt{n\log n}$. (Here, and throughout, $\log$ denotes the natural logarithm.) Hence, assuming $m^{1/5}$ is much larger than the number of elements of order $q$ in $G$, almost no sum-free subset of $G$ of this size is contained in a maximum-size sum-free subset of $G$.

We shall prove Theorem 1.1 using a new theorem (see Section 2) which describes the structure of a typical independent set in a 3-uniform hypergraph $\mathcal{H}$ that satisfies a certain natural ‘stability’ property, see Definition 2.1. The key ingredient in the proof of this theorem is a new method of enumerating independent sets in 3-uniform hypergraphs. We shall also use a simplified version of this method to prove a new bound on the number of independent sets in a certain class of expander graphs known as $(n,d,\lambda)$-graphs.

First, let us recall the definition of $(n,d,\lambda)$-graphs, which are an important class of expanders; for a detailed introduction to expander graphs, we refer the reader to or . Given a graph $\mathcal{G}$, let $\lambda_{1}\geqslant\ldots\geqslant\lambda_{n}$ denote the eigenvalues of the adjacency matrix of $\mathcal{G}$. We call $\max\{|\lambda_{2}|,|\lambda_{n}|\}$ the second eigenvalue of $\mathcal{G}$.

A graph $\mathcal{G}$ is an $(n,d,\lambda)$-graph if it is $d$-regular, has $n$ vertices, and the absolute value of each of its nontrivial eigenvalues is at most $\lambda$.

Alon and Rödl gave an upper bound on the number of independent sets in an $(n,d,\lambda)$-graph, and used their result to give sharp bounds on multicolour Ramsey numbers. When $\lambda=\Omega(d)$ (as $n\to\infty$), Theorem 1.3 below provides a significantly stronger bound than that of Alon and Rödl, for a wider range of $m$; it is moreover asymptotically sharp. In fact, we will not assume anything about the second eigenvalue of a graph $\mathcal{G}$ as our bound on the number of independent sets of $\mathcal{G}$ will depend only on the smallest eigenvalue of $\mathcal{G}$. Given a graph $\mathcal{G}$, let $\lambda(\mathcal{G})$ be the smallest eigenvalue of the adjacency matrix of $\mathcal{G}$ (denoted by $\lambda_{n}$ above) and let $I(\mathcal{G},m)$ be the number of independent sets of size $m$ in $\mathcal{G}$. Observe that $\lambda(\mathcal{G})<0$ for every non-empty $\mathcal{G}$ and that, by definition, every $(n,d,\lambda)$-graph satisfies $\lambda(\mathcal{G})\geqslant-\lambda$.

For every $\varepsilon>0$, there exists a constant $C=C(\varepsilon)$ such that the following holds. If $\mathcal{G}$ is an $n$-vertex $d$-regular graph with $\lambda(\mathcal{G})\geqslant-\lambda$, then

We remark that the constant $\frac{\lambda}{d+\lambda}$ in Theorem 1.3 is best possible, since there exist $n$-vertex $d$-regular graphs with $\lambda(\mathcal{G})\geqslant-\lambda$ and $\alpha(\mathcal{G})=\frac{\lambda}{d+\lambda}n$ for many values of $n$, $d$ and $\lambda$ (here $\alpha(\mathcal{G})$ denotes the independence number of $\mathcal{G}$). For example, consider a blow-up of the complete graph $K_{t+1}$, where each vertex is replaced by a set of size $n/(t+1)$ and each edge is replaced by a random $d/t$-regular bipartite graph with colour classes of size $n/(t+1)$ each. This blown-up graph $\mathcal{G}$ is $d$-regular and, with high probability, it satisfies $\lambda(\mathcal{G})=-d/t$ and $\alpha(\mathcal{G})=n/(t+1)$.

In Section 7, we shall use Theorem 1.3, together with some basic facts about characters of finite Abelian groups, to give a completely self-contained proof of Theorem 1.1 in the case $q=2$. For previous results relating the problem of estimating the number of sum-free subsets of groups, to that of estimating the number of independent sets in regular graphs, see for example . For other results on counting independent sets in graphs and hypergraphs, see Balogh and Samotij , Carroll, Galvin and Tetali , Galvin and Kahn , Kahn , Peled and Samotij , Sapozhenko and Zhao .

The rest of the paper is organised as follows. In Section 2, we state our structural theorem for 3-uniform hypergraphs, and in Section 3 we prove Theorem 1.3. In Sections 4 and 5, we prove the structural theorem, and in Sections 6 we shall apply it to prove Theorem 1.1. Finally, in Section 7, we shall prove Theorem 1.1 again in the case $q=2$.

A structural theorem for 3-uniform hypergraphs

Roughly speaking, a sequence of hypergraphs $(\mathcal{H}_{n})$ is $(\alpha,\mathcal{B})$-stable if for every $A\subseteq V(\mathcal{H}_{n})$ such that $|A|$ is almost as large as the extremal number for $\mathcal{H}_{n}$ (i.e., the size of the largest independent set), the set $A$ is either very close to an extremal set $B\in\mathcal{B}_{n}$, or it contains many (i.e., a positive fraction of all) edges of $\mathcal{H}_{n}$. Observe that classical stability results, such as that of Erdős and Simonovits , are typically of this form.

We shall need two further technical conditions on $\mathcal{H}$. Let

and note that if $\mathcal{H}$ encodes Schur triples then $\Delta_{2}(\mathcal{H}_{n})\leqslant 3$. Also define

and, as usual, write $\alpha(\mathcal{H}_{n})$ for the size of the largest independent set in $\mathcal{H}_{n}$.

The following theorem is the key step in the proof of Theorem 1.1.

then almost every independent set in $\mathcal{H}_{n}$ of size $m$ is a subset of some $B\in\mathcal{B}_{n}$.

We shall prove Theorem 2.2 in Sections 4 and 5. In Section 6, we shall use it to prove Theorem 1.1.

Independent sets in regular graphs with no small eigenvalues

As a warm-up for the proof of Theorem 2.2, we shall prove a bound on the number of independent sets in regular graphs with no small eigenvalues, Theorem 1.3, which improves a theorem of Alon and Rödl . This result will be a key tool in our self-contained proof of Theorem 1.1 in the case $q=2$, see Section 7. Moreover, many of the ideas from the proof of Theorem 1.3 will be used again in the proof of Theorem 2.2. We remark that the technique of enumerating independent sets in graphs used in this section was pioneered by Kleitman and Winston and our proof of Theorem 1.3, below, requires little more than their original method.

Given a graph $\mathcal{G}$ on $n$ vertices, and an integer $m\in[n]$, let $I(\mathcal{G})$ denote the number of independent sets in $\mathcal{G}$, and recall that $I(\mathcal{G},m)$ denotes the number of independent sets of size $m$ in $\mathcal{G}$. Alon proved that if $\mathcal{G}$ is a $d$-regular graph on $n$ vertices, then $I(\mathcal{G})\leqslant 2^{n/2+o(n)}$ (as $d\to\infty$), resolving a conjecture of Granville (see ), and suggested that the unique $\mathcal{G}$ that maximizes $I(\mathcal{G})$ among all such (i.e., $n$-vertex $d$-regular) graphs might be a disjoint union of copies of $K_{d,d}$. This conjecture was proven (using the entropy method) by Kahn for bipartite graphs, and recently in full generality by Zhao .

Let $\mathcal{G}$ be a $d$-regular graph on $n$ vertices. Then

where equality holds if and only if $\mathcal{G}$ is a disjoint union of copies of $K_{d,d}$.

Since $-d$ is an eigenvalue of $K_{d,d}$, any $d$-regular graph $\mathcal{G}$ containing a copy of $K_{d,d}$ satisfies $\lambda(\mathcal{G})=-d$. One might hope that a stronger bound on $I(\mathcal{G})$ holds for $d$-regular graphs $\mathcal{G}$ with $\lambda(\mathcal{G})>-d$. Alon and Rödl proved such a bound on $I(\mathcal{G},m)$ for the slightly narrower class of $(n,d,\lambda)$-graphs and used their result to give sharp bounds on Ramsey numbers.

Let $\mathcal{G}$ be an $(n,d,\lambda)$-graph. Then

If $\lambda=\Omega(d)$ as $n\to\infty$, then Theorem 1.3 improves the above result in three ways: it provides a stronger bound for a wider range of values of $m$ in a wider class of graphs. Theorem 1.3 is an immediate consequence of the following theorem, combined with the Alon-Chung lemma (Lemma 3.4, below).

For every $\varepsilon,\delta>0$, there exists a constant $C=C(\varepsilon,\delta)$ such that the following holds. Let $\mathcal{G}$ be a $d$-regular graph on $n$ vertices, and suppose that $2e(A)\geqslant\varepsilon|A|d$ for every $A\subseteq V(\mathcal{G})$ with $|A|\geqslant\big(\alpha+\delta\big)n$. Then

The assumption in Theorem 3.3 that $2e(A)\geqslant\varepsilon|A|d$ might seem somewhat strong; however, it follows from the Expander Mixing Lemma that it is satisfied by every $(n,d,\lambda)$-graph with $\lambda/(d+\lambda)\leqslant\alpha$. For two sets $S,T\subseteq V(\mathcal{G})$, let $e(S,T)$ denote the number of pairs $(x,y)\in S\times T$ such that $\{x,y\}\in E(\mathcal{G})$. In particular, we have $e(S,S)=2e(S)$ for every $S\subseteq V(\mathcal{G})$. The following result is proved Although the result is stated in in a slightly different form, its proof there in fact implies Lemma 3.4. in .

Let $\mathcal{G}$ be an $n$-vertex $d$-regular graph. Then for all $A\subseteq V(G)$,

We first deduce Theorem 1.3 from Theorem 3.3 and Lemma 3.4.

We claim that if $\mathcal{G}$ is an $n$-vertex $d$-regular graph with $\lambda(\mathcal{G})\geqslant-\lambda$ and $\alpha=\lambda/(d+\lambda)$, then $2e(A)\geqslant\varepsilon|A|d$ for every $A\subseteq V(\mathcal{G})$ with $|A|\geqslant(\alpha+\varepsilon)n$. This implies that $\mathcal{G}$ satisfies the assumption of Theorem 3.3 (with $\delta=\varepsilon$), and so the theorem follows.

To prove the claim, suppose that $A\subseteq V(\mathcal{G})$ satisfies $|A|\geqslant(\alpha+\varepsilon)n$. By Lemma 3.4,

Our lower bound on $|A|$ and the choice of $\alpha=\lambda/(d+\lambda)$ now give

In the proof of Theorem 3.3, we shall use an algorithm which uniquely encodes every independent set $I$ of size $m$ in $\mathcal{G}$ as a pair $(S,I\setminus S)$, where $|S|\leqslant 2n/\varepsilon d\leqslant 2m/C\varepsilon$, and $I\setminus S$ is contained in some set $A$, with $|A|\leqslant(\alpha+\delta)n$, which depends only on $S$. At all times, it maintains a partition of $V(\mathcal{G})$ into sets $S$, $X$, and $A$ (short for Selected, eXcluded, and Available), such that $S\subseteq I\subseteq A\cup S$.

At each stage of the algorithm, we will need to order the vertices of $A$ with respect to their degrees. For the sake of brevity and clarity of the presentation, let us make the following definition.

Given a graph $\mathcal{G}$ and a set $A\subseteq V(\mathcal{G})$, the max-degree order on $A$ is the following linear order $(v_{1},\ldots,v_{|A|})$ on the elements of $A$: For every $i\in\{1,\ldots,|A|\}$, $v_{i}$ is the maximum-degree vertex in the graph $\mathcal{G}[A\setminus\{v_{1},\ldots,v_{i-1}\}]$; we break ties by giving preference to vertices that come earlier in some predefined ordering of $V(\mathcal{G})$.

We are now ready to describe the Basic Algorithm.

Set $A=V(\mathcal{G})$ and $S=X=\emptyset$. Now, while $|A|>(\alpha+\delta)n$, we repeat the following:

Let $i$ be the minimal index (in the max-degree order on $A$) such that $v_{i}\in I$.

Move $v_{1},\ldots,v_{i-1}$ from $A$ to $X$ (since they are not in $I$ by the choice of $i$).

Move $N(v_{i})$ from $A$ to $X$ (since $I$ is independent and $v_{i}\in I$).

Finally, when $|A|\leqslant(\alpha+\delta)n$, we output $S$ (which is a subset of $V(\mathcal{G})$) and $I\setminus S$ (which is a subset of $A$).

We remark that, as well as in , algorithms similar to the one above have been considered before to bound the number of independent sets in graphs and hypergraphs .

The theorem is an easy consequence of the following two statements:

where $t_{0}=\displaystyle\frac{n}{\varepsilon d}+1$, and

if $t\leqslant 2n/\varepsilon d$ and $m\geqslant Cn/d$. We shall prove (1) using the Basic Algorithm; (2) follows from a straightforward calculation.

It will thus suffice to show that, given our assumptions on $\mathcal{G}$, the algorithm terminates in at most $t_{0}=\frac{n}{\varepsilon d}+1\leqslant\frac{2n}{\varepsilon d}$ steps. We shall show that $A$ loses at least $\varepsilon d$ elements at each step of the algorithm (except perhaps the last), from which this bound follows immediately. Indeed, consider a step of the algorithm (not the last), in which a vertex $v_{i}$ is moved to $S$, and set $A^{\prime}=A\setminus\{v_{1},\ldots,v_{i-1}\}$. Since this is not the last step, we have $|A^{\prime}|\geqslant(\alpha+\delta)n$, and so $2e(A^{\prime})\geqslant\varepsilon|A^{\prime}|d$, by our assumption on $\mathcal{G}$. Thus $|N(v_{i})\cap A^{\prime}|\geqslant\varepsilon d$, since $v_{i}$ is the vertex of maximum degree in $\mathcal{G}[A^{\prime}]$, and hence $A$ loses at least $\varepsilon d$ elements in this step, as claimed.

To prove (2), we use the fact that, if $t$ is replaced by $t+1$, then the left-hand side is multiplied by

We claim that (3) is at most $\frac{2}{\delta}\cdot\left(\frac{m}{t}\right)^{2}$. To prove this, we consider two cases: if $m\leqslant(\alpha+\delta/2)n$, then (3) is at most

while if $m>(\alpha+\delta/2)n$ then it is at most

since $n\leqslant 2m/\delta$, and our assumptions imply that $\alpha(\mathcal{G})<(\alpha+\delta)n$, so we may assume that $m<(\alpha+\delta)n$. Thus, for each $t$ with $t\leqslant t_{0}\leqslant\frac{2n}{\varepsilon d}$,

as required. In the final inequality we used the fact that $C$ is sufficiently large as a function of $\delta$ and $\varepsilon$, and that $m$ is sufficiently large (as a function of $\delta$), since $m\geqslant Cn/d$. ∎

Algorithm argument

In this section, we shall introduce a more powerful algorithm than that used in Section 3. We shall use this algorithm in the proof of Theorem 2.2 to bound the number of independent sets which contain at least $\delta m$ elements of $V(\mathcal{H}_{n})\setminus B$ for every $B\in\mathcal{B}_{n}$. We shall show that when $m\gg\sqrt{n}$, then the number of such independent sets is exponentially small. The model example that the reader should keep in mind when reading this section is when $\mathcal{H}_{n}$ is the hypergraph of Schur triples in an $n$-element Abelian group of Type I($q$), where $q$ is some prime satisfying $q\equiv 2\pmod{3}$.

Given a hypergraph $\mathcal{H}_{n}$, a family of sets $\mathcal{B}_{n}$, and $\delta>0$, we define

for some $\varepsilon=\varepsilon(\mathcal{H},\delta)>0$.

We shall frequently consider the max-degree order (defined in Section 3) on the vertices of the graph $\mathcal{G}_{T}[A]$.

The idea of the algorithm is quite simple: we apply the Basic Algorithm of Section 3 to the graph $\mathcal{G}_{T}[A]$ as long as it is reasonably dense. If $\mathcal{G}_{T}[A]$ becomes too sparse, then there are four possibilities: either we have arrived at a set $A$ which has at most $(\alpha-\beta)n$ elements, or a set $A$ which is almost contained in some $B\in\mathcal{B}_{n}$; or if not, then we can use the $(\alpha,\mathcal{B})$-stability of $\mathcal{H}$ to find either a new set $T$ for which $\mathcal{G}_{T}$ is dense (see Case 2 below), or a set of linear size that contains very few elements of $I$. Therefore, after moving relatively few vertices of $\mathcal{H}_{n}$ to $S$, our choice for $I\setminus S$ is limited to a set $A\subseteq V(\mathcal{G})$ that is either small or almost contained in some $B\in\mathcal{B}_{n}$. It follows that if $I$ was far from every $B\in\mathcal{B}_{n}$, then (in both cases) the number of ways to choose $I\setminus S$ from $A$ is very small.

We begin by choosing some constants. Let $\gamma>0$ and note that since $\mathcal{H}$ is $(\alpha,\mathcal{B})$-stable, there exists $\beta>0$ so that if $|A|\geqslant(\alpha-\beta)|V(\mathcal{H}_{n})|$ and $|A\setminus B|>\gamma|V(\mathcal{H}_{n})|$ for every $B\in\mathcal{B}_{n}$, then $e(\mathcal{H}_{n}[A])\geqslant\beta e(\mathcal{H}_{n})$. Let us choose $\beta>0$ sufficiently small so that $e(\mathcal{H}_{n})\geqslant\beta n^{2}$ and $\Delta_{2}(\mathcal{H}_{n})\leqslant 1/\beta$ for all sufficiently large $n$. Let $C=C(\beta)>0$ be sufficiently large, and set

We are ready to describe the Main Algorithm; this is the key step in our proof of Theorem 2.2.

We initiate the algorithm with $T=S\subseteq I$, a deterministically chosen subset of $I$ of size $d$ (the first $d$ elements of $I$ in our ordering of $V(\mathcal{H}_{n})$, say), and with $A=V(\mathcal{H}_{n})\setminus S$ and $X=\emptyset$. Now, while $|A|>(\alpha-\beta)n$ and $|A\setminus B|>\gamma n$ for every $B\in\mathcal{B}_{n}$, we repeat the following steps:

Case 1: If the average degree in $\mathcal{G}_{T}[A]$ is at least $\beta^{4}d$, then:

Let $i$ be the minimal index in the max-degree order on $V(\mathcal{G}_{T}[A])$ such that $v_{i}\in I$.

Move $v_{1},\ldots,v_{i-1}$ from $A$ to $X$ (since they are not in $I$ by the choice of $i$).

Move $N(v_{i})$ from $A$ to $X$ (since $I$ is independent and $v_{i}\in I$).

Case 2: If the average degree of $\mathcal{G}_{T}[A]$ is less than $\beta^{4}d$, then we find a new set $T$ as follows. Since $\mathcal{H}$ is $(\alpha,\mathcal{B})$-stable, $|A|>(\alpha-\beta)n$, and $|A\setminus B|>\gamma n$ for every $B\in\mathcal{B}_{n}$, then $A$ contains at least $\beta e(\mathcal{H}_{n})$ edges of $\mathcal{H}_{n}$. Set

where $\mathcal{G}_{z}[A]$ is the graph with vertex set $A$ and edge set $\big\{\{x,y\}:\{x,y,z\}\in E(\mathcal{H}_{n})\big\}$. We call the elements of $Z$ useful. Since $e(\mathcal{H}_{n})\geqslant\beta n^{2}$, we have $e\big(\mathcal{H}_{n}[A]\big)\geqslant\beta^{2}n^{2}$, and so

Moreover, we have $e\big(\mathcal{G}_{z}[A]\big)\leqslant\Delta(\mathcal{H}_{n})\leqslant\Delta_{2}(\mathcal{H}_{n})n\leqslant n/\beta$ for every $z\in V(\mathcal{G})$. Thus, by the pigeonhole principle, it follows that $|Z|\geqslant 2\beta^{3}n$.

If $I$ contains fewer than $d$ useful elements, then move these elements from $A$ to $S$ and move the other useful elements from $A$ to $X$.

If $I$ contains more than $d$ useful elements, choose $d$ of them $u_{1},\ldots,u_{d}$ (the first $d$ in our ordering, say) and move them from $A$ to $S$. Moreover, set $T=\{u_{1},\ldots,u_{d}\}$.

Finally, when $|A|\leqslant(\alpha-\beta)n$, or $|A\setminus B|\leqslant\gamma n$ for some $B\in\mathcal{B}_{n}$, then we output $S$ (which is a subset of $V(\mathcal{G})$) and $I\setminus S$ (which is a subset of $A$) and stop.

We shall show that the Main Algorithm encodes at most $\beta^{2}m$ elements of $I$ in $S$, and that $S$ determines $A$. Theorem 4.1 then follows from some simple counting.

2. Proof of Theorem 4.1

We begin by proving three straightforward claims about the Main Algorithm; these, together with some simple counting, will be enough to prove the theorem. The following statements all hold under the assumptions of Theorem 4.1.

The Main Algorithm passes through Case $1$ at most $2n/(\beta^{4}d)$ times, and through Case $2$ at most $1/\beta^{5}$ times.

We prove the second statement first. To do so, simply observe that each time we pass through Case $2(a)$, we move at least $2\beta^{3}n-d\geqslant\beta^{3}n$ vertices from $A$ to $X$, and each time we pass through Case $2(b)$, we obtain a graph $\mathcal{G}_{T}[A]$ with at least $\beta^{2}nd/\Delta_{2}(\mathcal{H}_{n})-O(d^{2})\geqslant 2\beta^{4}nd$ edges. In the latter case, we must remove at least $\beta^{4}nd$ edges from $\mathcal{G}_{T}[A]$ before we can return to Case $2$. Since $\Delta_{2}(\mathcal{H}_{n})\leqslant 1/\beta$, it follows that $\Delta(\mathcal{G}_{T})\leqslant|T|/\beta=d/\beta$, since if $xy\in E(\mathcal{G}_{T})$ then there exists $z\in T$ such that $\{x,y,z\}\in E(\mathcal{H}_{n})$, and for each pair $\{x,z\}$ there are at most $\Delta_{2}(\mathcal{H}_{n})$ such $y$. Thus we must remove at least $\beta^{5}n$ vertices from $A$ before returning to Case $2$, and hence the algorithm can pass through Case $2$ at most $1/\beta^{5}$ times before the set $A$ shrinks to size $\alpha n$, as claimed.

To prove the first statement, note that each time we pass through Case 1 on two successive steps of the algorithm, we remove at least $\beta^{4}d$ vertices of $A$ in the first of these. Indeed, since $\mathcal{G}_{T}[A]$ (for the second step) has average degree at least $\beta^{4}d$, then by the definition of the max-degree order, the vertex we removed in the first step must have had forward degree at least $\beta^{4}d$. By the argument above, there are at most $1/\beta^{5}$ steps at which this fails to hold, and therefore the algorithm passes through Case $1$ at most

The next claim is a simple consequence of Claim 1 and our choice of $d$.

If $C\geqslant 3/\beta^{7}$, then $|S|\leqslant\beta^{2}m$ at the end of the Main Algorithm.

Each time the Main Algorithm passes through Case 1, $|S|$ increases by one; each time it passes through Case 2, $|S|$ increases by at most $d$. Thus, by Claim 1 and our choice of $d$,

if $C\geqslant 3/\beta^{7}$, as claimed. ∎

We next make the key observation that the set $S$ contains all the information we need to recover the final set $A$ produced by the algorithm.

The set $A$ is uniquely determined by the set $S$ of selected elements.

This follows because all steps of the Main Algorithm are deterministic, and every element of $I$ which we need to observe is placed in $S$. Indeed, in Case 1 we observe only that $v_{i}\in I$, and that the elements $v_{1},\ldots,v_{i-1}\not\in I$. Since $v_{i}\in S$ and $v_{1}\ldots,v_{i-1}\not\in S$, this can be deduced from $S$. In Case $2$, the set $Z$ does not depend on $I$. If at most $d-1$ elements of $Z$ are in $S$, then we are in Case $2(a)$ and the remaining elements of $Z$ are in $X$; otherwise, we are in Case $2(b)$ and the first $d$ elements of $S\cap Z$ (in the order on $V(\mathcal{H}_{n})$) form the set $T$. Thus, inductively, we see that at each stage of the algorithm, the set $A$ is determined by the set $S$. ∎

After all this preparation, we are ready to prove Theorem 4.1.

We claim first that the number of such sets $I$ is at most

Indeed, let $S$ and $A$ be the selected and available sets at the end of the algorithm, set $t=|S|$, and recall that $t\leqslant\beta^{2}m$ by Claim 2. We have at most ${n\choose t}$ choices for $S$ and, by Claim 3, the set $S$ determines the set $A$. Let $B\in\mathcal{B}_{n}$ be such that $|A\setminus B|\leqslant\gamma n$ and recall that $|I\setminus B|\geqslant\delta m$ by our assumption on $I$. Thus we must choose the set $B\in\mathcal{B}_{n}$, at least $\delta m-t$ elements of $A\setminus B$, and the remaining elements from $B$.

Note that $t\leqslant\delta m/2$ by our choice of $\beta$ and so either $m\leqslant(2\gamma/\delta)n$ or the number of choices for $I$ is zero. Since $\|B_{n}\|\geqslant\alpha n$ and $\gamma$ is small, it follows that the summand in (4) is maximized exactly when $r=\delta m$. Now, using the inequalities ${n\choose k}\leqslant\big(\frac{en}{k}\big)^{k}$ and

which holds for every $a>b>c\geqslant 0$, and since $t\leqslant\delta m/2$, $m\leqslant(2\gamma/\delta)n\leqslant(\alpha/2)n$ and $\|\mathcal{B}_{n}\|\geqslant\alpha n$, we can bound each summand in (4) from above by

Since $t\leqslant\delta m/2$ and $t\mapsto(c/t)^{t}$ is increasing on $(0,c/e)$, this is at most

if $\gamma\leqslant(\alpha\delta/4e)^{2}\cdot\delta^{4/\delta}$. Since $m^{2}\cdot\delta^{2m}\leqslant\delta^{m}$, the claim follows. ∎

Finally, we deal with the case in which $|A|\leqslant(\alpha-\beta)n$ for some $B\in\mathcal{B}_{n}$.

As in the previous claim, we have $t=|S|\leqslant\beta^{2}m$, by Claim 2, and the set $S$ determines the set $A$, by Claim 3. Thus, the number of choices for $I$ is at most

Now, using the inequality $\binom{b}{c}\leqslant\left(\frac{b}{a}\right)^{c}\binom{a}{c}$, which is valid for all $a>b>c\geqslant 0$, and recalling that $t\leqslant\beta^{2}m$ and that $t\mapsto(c/t)^{t}$ is increasing on $(0,c/e)$, we get

Since $\|B_{n}\|\geqslant\alpha n$, the right-hand side is at most $\frac{1}{m}\cdot 2^{-\varepsilon m}{\|\mathcal{B}_{n}\|\choose m}$ if $\beta>0$ and $\varepsilon=\varepsilon(\beta)>0$ are sufficiently small, as required. ∎

Combining Claims 4 and 5, we obtain Theorem 4.1. ∎

Janson argument

In this section, we shall complete the proof of Theorem 2.2 by showing that, under certain conditions, almost all independent (i.e., sum-free) sets $I$ of size $m$ in $\mathcal{H}_{n}$ either satisfy $I\subseteq B$ for some $B\in\mathcal{B}_{n}$, or $|I\setminus B|\geqslant\delta m$ for every $B\in\mathcal{B}_{n}$. The key properties of $\mathcal{H}$ which we will use are that $\Delta_{2}(\mathcal{H}_{n})=O(1)$, and that $\delta(\mathcal{H}_{n},\mathcal{B}_{n})=\Omega(n)$; our key tool will be Janson’s inequality. An argument similar to that presented in this section was used in to study sum-free sets in random subsets of Abelian groups.

Given a hypergraph $\mathcal{H}_{n}$, a family of sets $\mathcal{B}_{n}$ and $\delta>0$, we define

Note that $\delta$ and $C_{0}$ in the statement of Proposition 5.1 may depend on $\mathcal{H}$, $\mathcal{B}$, $\alpha$ and $\beta$. We begin by recalling the Janson inequalities, and some basic facts about the hypergeometric distribution.

The following well-known inequality (see [20, page 35], for example) allows us to deduce bounds in the hypergeometric distribution from results on product measure. For completeness we give a proof.

Moreover, if $\mathcal{Q}$ is monotone decreasing and $m\leqslant n-1$, then

For the first part, simply note that a random $p$-subset of $[n]$ has size $m=pn$ with probability at least $1/(3\sqrt{m})$. If $\mathcal{Q}$ is monotone decreasing, say, then we apply the ‘Local LYM inequality’ to $\mathcal{Q}_{m}$, the set of $m$-sets in $\mathcal{Q}$, and deduce that

for every $k\leqslant m$. It is well-known that the median of the binomial distribution lies between $\lfloor pn\rfloor$ and $\lceil pn\rceil$, and if $m\leqslant n-1$ then it is easy to see that $\textup{Bin}(n,p)=\lceil pn\rceil$ has probability at most $(1-1/n)^{n-1}\to 1/e$ as $n\to\infty$. Thus, if $m\leqslant n-1$ and $n$ is sufficiently large, then a random $p$-subset of $[n]$ has size at most $m=pn$ with probability at least $1/2-1/e+o(1)$ as $n\to\infty$, and the result follows. ∎

The following result is an easy corollary of Janson’s inequality (see ), combined with Pittel’s inequality.

Suppose that $\{U_{i}\}_{i\in I}$ is a family of subsets of an $n$-element set $X$ and let $m\in\{0,\ldots,n\}$. Let

where the second sum is over ordered pairs $(i,j)$ such that $i\neq j$ and $U_{i}\cap U_{j}\neq\emptyset$. Let $R$ be a uniformly chosen random $m$-subset of $X$. Then

where $C>0$ is the constant in Pittel’s inequality.

We now return to the proof of Proposition 5.1.

2. Proof of Proposition 5.1

In order to prove Lemma 5.4, we shall apply the following lemma to the Cayley graph of $S$, restricted to $B$. The lemma is a straightforward consequence of the Hypergeometric Janson’s inequality.

For every $\beta>0$, there exists a constant $C_{0}>0$ such that the following holds. Let $\mathcal{G}$ be a graph on $n$ vertices with maximum degree at most $d$. If

Let $\{U_{i}\}_{i\in I}$ be the collection of pairs of vertices which span an edge of $\mathcal{G}$, so $U_{i}\nsubseteq R$ for all $i\in I$ if and only if $R$ is an independent set in $\mathcal{G}$. It is easy to see that, letting $\mu$ and $\Delta$ to be the quantities defined in the statement of Lemma 5.3,

Thus, by our bounds on $e(\mathcal{G})$ and $m$, and assuming $C\geqslant 4/\beta$,

Recall that, given $\mathcal{H}_{n}$, the Cayley graph $\mathcal{G}_{S}$ of $S$ is defined to be the graph with vertex set $V(\mathcal{H}_{n})$ and edge set

In order to apply Lemma 5.5, we shall need the following easy property of the Cayley graph.

$\Delta(\mathcal{G}_{S})\leqslant|S|\Delta_{2}(\mathcal{H}_{n})$.

We can now easily deduce Lemma 5.4 from Lemma 5.5 and Observation 5.6.

If $I$ is an independent set in $\mathcal{H}_{n}$ containing $S$, then $I\setminus S$ is an independent set in $\mathcal{G}_{S}$, so

where $k=|S|$. Choose $\beta>0$ sufficiently small so that $\Delta_{2}(\mathcal{H}_{n})\leqslant 1/(2\beta)$, recall that $\delta(\mathcal{H}_{n},B)\geqslant\beta n$, note that $d=\Delta(\mathcal{G}_{S})\leqslant|S|\Delta_{2}(\mathcal{H}_{n})\leqslant|S|/(2\beta)$, and observe that therefore

Thus, by Lemma 5.5, if $\beta<1/10$ then $d\geqslant 5|S|=5k$ and

for every $m\geqslant C\sqrt{n\log n}$, as required. ∎

Finally, let us deduce Proposition 5.1 from Lemma 5.4.

Summing over all sets $B\in\mathcal{B}_{n}$ and subsets $S\subseteq[n]\setminus B$, and applying Lemma 5.4, we have

for every $m\geqslant C\sqrt{n\log n}$, since $\delta(\mathcal{H}_{n},\mathcal{B}_{n})\geqslant\beta n$ and $\Delta_{2}(\mathcal{H}_{n})=O(1)$ together imply that $|B|=\Theta(n)$ for every $B\in\mathcal{B}_{n}$. We consider three cases.

Case 1: If $n^{-4(C+k)}\geqslant e^{-\beta^{3}m}$, then

since ${\|\mathcal{B}_{n}\|\choose{m-k}}\,\leqslant\,{n\choose k}{\|\mathcal{B}_{n}\|\choose{m}}$.

Case 2: If $n^{-4(C+k)}\leqslant e^{-\beta^{3}m}$ and $m\leqslant\alpha n/2$, then by (5) we have

since $\|\mathcal{B}_{n}\|\geqslant\alpha n$. Thus, using the bound ${n\choose k}\leqslant\big(\frac{en}{k}\big)^{k}$, we have

if $\delta=\delta(\alpha,\beta)>0$ is sufficiently small, since $k\leqslant\delta m$.

Case 3: If $\|\mathcal{B}_{n}\|^{-4(C+k)}\leqslant e^{-\beta^{3}m}$ and $m\geqslant\alpha n/2$, then we again use the (trivial) bound ${\|\mathcal{B}_{n}\|\choose{m-k}}\,\leqslant\,{n\choose k}{\|\mathcal{B}_{n}\|\choose{m}}$, to obtain

if $\delta=\delta(\alpha,\beta)>0$ is sufficiently small, since ${n\choose k}\leqslant\binom{2m/\alpha}{k}\leqslant\left(\frac{2e}{\alpha\delta}\right)^{\delta m}\leqslant e^{-\beta^{3}m/6}$ for $k\leqslant\delta m$.

Since $e^{-\beta^{3}m/2}\ll n^{-2C}$ for $m\geqslant C\sqrt{n\log n}$, the claimed bound follows. ∎

We finish this section by observing that Theorem 4.1 and Proposition 5.1 together imply Theorem 2.2.

then almost every independent set in $\mathcal{H}_{n}$ of size $m$ is a subset of some $B\in\mathcal{B}_{n}$.

Indeed, by Theorem 4.1, the number of independent sets $I$ in $\mathcal{H}_{n}$ of size $m$ for which $|I\setminus B|\geqslant\delta m$ for every $B\in\mathcal{B}_{n}$ is at most

for some $\varepsilon>0$ and by Proposition 5.1, the number of such sets for which $1\leqslant|I\setminus B|\leqslant\delta m$ for some $B\in\mathcal{B}_{n}$ is at most

Since $|\mathcal{B}_{n}|\leqslant n^{1/\beta}$, $C>1/\beta$, and $\alpha(\mathcal{H}_{n})\geqslant\|\mathcal{B}_{n}\|$, the result follows. ∎

Abelian groups of Type I

In this section, we shall use Theorem 2.2 to prove Theorem 1.1 for all $q>2$. We remark that the proof below can also be adapted to cover the case $q=2$; however, since we shall give a different proof of the case $q=2$ in Section 7, we leave the details to the reader. (If $\mathcal{H}_{n}$ denotes the hypergraph that encodes Schur triples in a group $G$ of even order $n$ and $\mathcal{B}_{n}$ denotes the collection of maximum-size sum-free subsets of $G$, then it is not always true that $\Omega(\mathcal{H}_{n},\mathcal{B}_{n})=\Omega(n)$. This problem can be easily overcome by considering triples of the form $(x,x,2x)$, cf. the proof of the $1$-statement in [6, Theorem 1.2].)

Let $G$ be a finite Abelian group of Type $I(q)$, where $q\equiv 2\pmod{3}$ and let $0<\gamma<\gamma(q)$ and $0<\beta<\beta_{0}(\gamma,q)$ be sufficiently small. Let $A\subseteq G$, and suppose that

$A$ contains at least $\beta|G|^{2}$ Schur triples.

We shall also use the following classification of extremal sum-free sets for Type I groups.

Combining Theorem 6.2 with Kronecker’s Decomposition Theorem, we easily obtain the following well-known corollary.

It is now straightforward to deduce Theorem 1.1 from Theorem 2.2, Proposition 6.1, and Corollary 6.3.

We claim that $\mathcal{H}$ and $\mathcal{B}$ satisfy the conditions of Theorem 2.2. Indeed, $\mathcal{H}_{n}$ is 3-uniform, has $\Theta(n^{2})$ edges, and satisfies $\Delta_{2}(\mathcal{H}_{n})=3$. Setting $\alpha=\mu(G)$, we have $\alpha(\mathcal{H}_{n})=\|\mathcal{B}_{n}\|=\alpha n$ and $|\mathcal{B}_{n}|\leqslant n$, as observed above. Moreover, the statement that $\mathcal{H}$ is $(\alpha,\mathcal{B})$-stable is exactly Proposition 6.1. Thus it will suffice to show that $\delta(\mathcal{H}_{n},\mathcal{B}_{n})=\Omega(n)$.

whenever $h\in H$ and $y+h\neq z-h$. Moreover, since $|G|$ is odd, there is at most one $h\in H$ such that $2h=z-y$, so $|C(x)|\geqslant(|H|-1)/2=n/2q-1/2$, as required. ∎

Thus the pair $(\mathcal{H},\mathcal{B})$ satisfies the conditions of Theorem 2.2 and hence if $C(q)$ is sufficiently large and $m\geqslant C(q)\sqrt{n\log n}$, then almost every sum-free set of size $m$ in $G_{n}$ is contained in some $B\in\mathcal{B}_{n}$, as required.

Finally, let us deduce that if $G$ is an Abelian group of Type I($q$), and $m\geqslant C(q)\sqrt{n\log n}$, then

Abelian groups of even order

In this section, we shall prove the following theorem, which implies Theorem 1.1 in the case $q=2$. We shall use Theorem 1.3 and some ideas from Section 5, but otherwise this section is self-contained. In particular, we shall not use Proposition 6.1 and thus we give a new proof of the main theorem of and .

If $G$ is an Abelian group of order $n$, then

We remark that we shall prove the theorem for all finite Abelian groups, not just those of even order. We begin by partitioning the collection of sum-free sets into two pieces. Given an Abelian group $G$, let

Let $G$ be an Abelian group of order $n$, and let $\delta>0$ be sufficiently small. Then

Let $G$ be an Abelian group of order $n$, and let $\delta>0$. If $\varepsilon=\varepsilon(\delta)>0$ is sufficiently small and $C=C(\delta)$ is sufficiently large, then

We begin by proving Proposition 7.2. In this section, we shall use a slightly different notion of Cayley graph than that used earlier. Given $S\subseteq G$, define $\mathcal{G}^{*}_{S}$ to be the graph with vertex set $G\setminus S$ and edge set $\big\{xy\colon x-y\in S\big\}$, and note that if $I$ is a sum-free set in $G$ with $S\subseteq I$, then $I\setminus S$ is an independent set in $\mathcal{G}^{*}_{S}$.