Independent sets in hypergraphs

Introduction

A great many of the central questions in combinatorics fall into the following general framework: Given a finite set $V$ and a collection $\mathcal{H}\subseteq\mathcal{P}(V)$ of forbidden structures, what can be said about sets $I\subseteq V$ that do not contain any member of $\mathcal{H}$? For example, the celebrated theorem of Szemerédi states that if $V=\{1,\ldots,n\}$ and $\mathcal{H}$ is the collection of $k$-term arithmetic progressions in $\{1,\ldots,n\}$, then every set $I$ that contains no member of $\mathcal{H}$ satisfies $|I|=o(n)$. The archetypal problem studied in extremal graph theory, dating back to the work of Turán and Erdős and Stone , is the problem of characterizing such sets $I$ when $V$ is the edge set of the complete graph on $n$ vertices and $\mathcal{H}$ is the collection of copies of some fixed graph $H$ in $K_{n}$. In this setting, a great deal is known, not only about the maximum size of $I$ that contains no member of $\mathcal{H}$, but also what the largest such sets look like, how many such sets there are, and what the structure of a typical such set is.

A collection $\mathcal{H}\subseteq\mathcal{P}(V)$ as above is usually referred to as a hypergraph on the vertex set $V$ and any set $I\subseteq V$ that contains no element (edge) of $\mathcal{H}$ is called an independent set. Therefore, one might say that a large part of extremal combinatorics is concerned with studying independent sets in various specific hypergraphs. We might add here that in many natural settings, such as the two mentioned above, the hypergraphs considered are uniform, that is, all edges of $\mathcal{H}$ have the same size.

Although it might at first seem somewhat artificial to study concrete questions in such an abstract setting, the past few years have proved that taking such a general approach can be highly beneficial. The recently-proved general transference theorems of Conlon and Gowers and Schacht (see also ), which imply, among other things, sparse random analogues of the classical theorems of Szemerédi and of Erdős and Stone, were stated in the language of hypergraphs. Roughly speaking, these transference theorems say the following: Let $\mathcal{H}$ be a hypergraph whose edges are sufficiently ‘uniformly distributed’. Then the independence number of $\mathcal{H}$ is ‘well-behaved’ with respect to taking subhypergraphs induced by (sufficiently dense) random subsets of the vertex set. More precisely, given $p\in$ and a finite set $V$, we shall write $V_{p}$ to denote the $p$-random subset of $V$, that is, the random subset of $V$ in which each element of $V$ is included with probability $p$, independently of all other elements. We write $\alpha(\mathcal{H})$ and $v(\mathcal{H})$ to denote the size of the largest independent set and the number of vertices in a hypergraph $\mathcal{H}$, respectively. The results of Conlon and Gowers and Schacht imply, in particular, that if the distribution of the edges of some uniform hypergraph $\mathcal{H}$ is sufficiently ‘balanced’, then with probability tending to $1$ as $v(\mathcal{H})\to\infty$,

In this work, we give an approximate structural characterization of the family of all independent sets in uniform hypergraphs whose edge distribution satisfies a certain natural boundedness condition. More precisely, we shall prove that the family $\mathcal{I}(\mathcal{H})$ of independent sets of such a hypergraph $\mathcal{H}$ exhibits a certain clustering phenomenon. Our main result (Theorem 2.2, below) states that $\mathcal{I}(\mathcal{H})$ admits a partition into relatively few classes with the following property: all members of each class are essentially contained in a single ‘almost independent’ subset of $V(\mathcal{H})$ (i.e., one which contains only a tiny proportion of all the edges of $\mathcal{H}$). This somewhat abstract statement has surprisingly many deep and interesting consequences, some of which we list in the remainder of this section. We remark that Theorem 2.2 was partly inspired by the work of Kleitman and Winston , who implicitly considered a statement of this type in the setting of graphs ($2$-uniform hypergraphs) and subsequently used it to bound the number of $n$-vertex graphs without a $4$-cycle. We also note that a result similar to Theorem 2.2 was independently proved by Saxton and Thomason , who also use it to derive many of the statements that we present in Sections 1.1– 1.4.

$m$-subsets of $\{1,\ldots,n\}$ that contain no $k$-term AP.

We remark that Theorem 1.1 and Corollary 1.2 are both sharp up to the value of the constant $C$, see the discussion in Section 4, where both of these statements are proved.

Our main result has a variety of other applications in additive combinatorics, see for example where, jointly with Alon, we used a much simpler version of it to count sum-free sets of fixed size in various Abelian groups and the set $[n]$. In Section 4, we shall mention two other applications: generalizations of Theorem 1.1 to higher dimensions and to $k$-term APs whose common difference is of the form $d^{r}$. In each case, the random version (which was proved in ) follows as an easy corollary.

2. Turán’s problem in random graphs

The famous theorem of Erdős and Stone states that the maximum number of edges in an $H$-free graph on $n$ vertices, the Turán number for $H$, denoted $\operatorname{ex}(n,H)$, satisfies

where $\operatorname{ex}(G,H)$ denotes the maximum number of edges in an $H$-free subgraph of $G$.

By considering a random $(\chi(H)-1)$-partition of the vertex set of $G(n,p)$, it is straightforward to show that the inequality \operatorname{ex}\big{(}G(n,p),H\big{)}\geqslant\left(1-\frac{1}{\chi(H)-1}+o(1)\right)\binom{n}{2}p holds for every $p\in$. On the other hand, if the number of copies of some subgraph $H^{\prime}\subseteq H$ in $G(n,p)$ is much smaller than the number of edges in $G(n,p)$, then the converse inequality cannot hold, since one can make any graph $H$-free by removing from it one edge from each copy of $H^{\prime}$. This observation motivates the notion of $2$-density of $H$, denoted by $m_{2}(H)$, which is defined by

It now follows easily that for every graph $H$ with maximum degree at least $2$ and every \delta\in\big{(}0,1/(\chi(H)-1)\big{)}, there exists a positive constant $c$ such that if $p_{n}\leqslant cn^{-1/m_{2}(H)}$, then a.a.s.

It was conjectured by Haxell, Kohayakawa, and Łuczak and Kohayakawa, Łuczak, and Rödl that the above simple argument, removing an arbitrary edge from each copy of $H^{\prime}$ in $G(n,p)$, is the main obstacle that prevents (2) from holding asymptotically almost surely. The conjecture, often referred to as Turán’s theorem for random graphs, has attracted considerable attention in the past fifteen years. Numerous partial results and special cases had been established by various researchers before the conjecture was finally proved by Conlon and Gowers (under the assumption that $H$ is strictly $2$-balancedA graph $H$ is $2$-balanced if the maximum in (3) is achieved with $H^{\prime}=H$, that is, if $m_{2}(H)=\frac{e(H)-1}{v(H)-2}$. It is strictly $2$-balanced if $m_{2}(H)>m_{2}(H^{\prime})$ for every proper subgraph $H^{\prime}\subsetneq H$.) and by Schacht .

For every graph $H$ with $\Delta(H)\geqslant 2$ and every positive $\delta$, there exists a positive constant $C$ such that if $p_{n}\geqslant Cn^{-1/m_{2}(H)}$, then a.a.s.

Our methods give yet another proof of Theorem 1.3. In fact, we shall deduce from our main result, Theorem 2.2, a version of the general transference theorem of Schacht [58, Theorem 3.3], which easily implies Theorem 1.3 for such graphs $H$. Our version of Schacht’s transference theorem, Theorem 5.2, is stated and proved in Section 5. We then, in Section 7, use it to derive a natural generalization of Theorem 1.3 to $t$-uniform hypergraphs, Theorem 7.2, which was also first proved in and .

In the original version of this paper, we only proved the results concerning $H$-free graphs under the additional assumption that $H$ is $2$-balanced. However, a simple modification of our method (permitting multiple edges in our hypergraphs, as in ) allowed us to remove this condition. We would like to thank David Saxton for pointing this out.

Our methods also yield the following sparse random analogue of the famous stability theorem of Erdős and Simonovits , originally proved by Conlon and Gowers in the case when $H$ is strictly $2$-balanced and then extended to arbitrary $H$ by Samotij , who adapted the argument of Schacht for this purpose.

For every graph $H$ with $\Delta(H)\geqslant 2$ and every positive $\delta$, there exist positive constants $C$ and $\varepsilon$ such that if $p_{n}\geqslant Cn^{-1/m_{2}(H)}$, then a.a.s. the following holds. Every $H$-free subgraph of $G(n,p_{n})$ with at least

edges may be made $(\chi(H)-1)$-partite by removing from it at most $\delta n^{2}p_{n}$ edges.

As with Theorem 1.3, we shall in fact deduce Theorem 1.5 from a more general statement, Theorem 6.2, which is a version of the general transference theorem for stability results proved in . Theorem 6.2 is stated and proved in Section 6; in Section 7, we use it to derive Theorem 1.5.

3. The typical structure of H𝐻H-free graphs

Let $H$ be an arbitrary non-empty graph. For an integer $n$, denote by $f_{n}(H)$ the number of labelled $H$-free graphs on the vertex set $[n]$. Since every subgraph of an $H$-free graph is also $H$-free, it follows that $f_{n}(H)\geqslant 2^{\operatorname{ex}(n,H)}$. Erdős, Frankl, and Rödl proved that this crude lower bound is in a sense tight, namely that

Our next result can be viewed as a ‘sparse version’ of (4). Such a statement was already considered by Łuczak , who derived it from the so-called KŁR conjecture, which we discuss in the next subsection. For integers $n$ and $m$ with $0\leqslant m\leqslant\binom{n}{2}$, let $f_{n,m}(H)$ be the number of labelled $H$-free graphs on the vertex set $[n]$ that have exactly $m$ edges. The following theorem refines (4) to $n$-vertex graphs with $m$ edges.

In fact, we shall deduce from our main result, Theorem 2.2, a ‘counting version’ of the general transference theorem of Schacht [58, Theorem 3.3], which easily implies Theorem 1.6. This ‘counting version’ of Schacht’s theorem (which refines and, in some respects, strengthens the main results of ) is stated and proved in Section 5. We then use it to derive Theorem 1.6 in Section 8. We remark that (4) was refined in a different sense by Balogh, Bollobás, and Simonovits , who showed that $f_{n}(H)=2^{\operatorname{ex}(n,H)+O(n^{2-c(H)})}$, where $c(H)$ is some positive constant, and also gave a very precise structural description of almost all $H$-free graphs. We would also like to point out that our proof of Theorem 1.6 does not use Szemerédi’s regularity lemma, unlike the proof given in or the proofs of Erdős, Frankl, and Rödl and Balogh, Bollobás, and Simonovits .

The result of Erdős, Frankl, and Rödl has, in some cases, a structural counterpart that significantly strengthens (4). For example, Erdős, Kleitman, and Rothschild proved that almost all triangle-free graphs are bipartite, that is, that with probability tending to $1$ as $n\to\infty$, a graph selected uniformly at random from the family of all triangle-free graphs on the vertex set $[n]$ is bipartite or, in other words (since clearly every bipartite graph is triangle-free), $f_{n}(K_{3})$ is asymptotic to the number of bipartite graphs on the vertex set $[n]$. Extending this result, Osthus, Prömel, and Taraz proved that if $m\geqslant Cn^{3/2}\sqrt{\log n}$ for some $C>\sqrt{3}/4$, then almost all $n$-vertex triangle-free graphs with $m$ edges are bipartite. The corresponding result for $K_{r+1}$-free graphs was proved recently in .

Our next result, which is a strengthening of Theorem 1.6, is an approximate version of this statement for an arbitrary graph $H$. Such a statement was also considered by Łuczak , who derived it from the KŁR conjecture. Following , given a positive real $\delta$ and an integer $k$, let us say that a graph $G$ is $(\delta,k)$-partite if $G$ can be made $k$-partite by removing from it at most $\delta e(G)$ edges.

For every graph $H$ with $\chi(H)\geqslant 3$, and every positive $\delta$, there exists a positive constant $C$ such that the following holds. If $m\geqslant Cn^{2-1/m_{2}(H)}$, then almost all $H$-free graphs with $n$ vertices and $m$ edges are \big{(}\delta,\chi(H)-1\big{)}-partite.

As with Theorem 1.6, we shall in fact deduce Theorem 1.7 from a ‘counting version’ of the general transference theorem for stability results proved in . Our version of it, Theorem 6.3, is stated and proved in Section 6. In Section 8, we use it to derive Theorem 1.7. Once again, our proof does not use the regularity lemma, unlike that in . Finally, we would like to mention that, as observed by Łuczak , Theorem 1.7 has the following elegant corollary.

where $G_{n,m}$ is a uniformly selected random $n$-vertex graph with $m$ edges.

4. The KŁR conjecture

The celebrated Szemerédi regularity lemma , which is considered to be one of the most important and powerful tools in extremal graph theory, says that the vertex set of every graph may be divided into a bounded number of parts of approximately the same size in such a way that most of the bipartite subgraphs induced between pairs of parts of the partition satisfy a certain pseudo-randomness condition termed $\varepsilon$-regularity. The strength of the regularity lemma lies in the fact that it may be combined with the so-called embedding lemma to show that a graph contains particular subgraphs. The combination of the regularity and embedding lemmas allows one to prove many well-known theorems in extremal graph theory, such as the theorem of Erdős and Stone and the stability theorem of Erdős and Simonovits , both mentioned in Section 1.2.

For sparse graphs, that is, $n$-vertex graphs with $o(n^{2})$ edges, the original version of the regularity lemma is vacuous since if the vertex set of a sparse graph is partitioned into a bounded number of parts, then all induced bipartite subgraphs thus obtained are trivially $\varepsilon$-regular, provided that $n$ is sufficiently large. However, it was independently observed by Kohayakawa and Rödl (unpublished) that the notion of $\varepsilon$-regularity may be extended in a meaningful way to graphs with density tending to zero. Moreover, with this more general notion of regularity, they were also able to prove an associated regularity lemma which applies to a large class of sparse graphs, including (a.a.s.) the random graph $G(n,p)$.

Given a $p\in$ and a positive $\varepsilon$, we say that a bipartite graph between sets $V_{1}$ and $V_{2}$ is $(\varepsilon,p)$-regular if for every $W_{1}\subseteq V_{1}$ and $W_{2}\subseteq V_{2}$ with $|W_{1}|\geqslant\varepsilon|V_{1}|$ and $|W_{2}|\geqslant\varepsilon|V_{2}|$, the density $d(W_{1},W_{2})$ of edges between $W_{1}$ and $W_{2}$ satisfies

A partition of the vertex set of a graph into $r$ parts $V_{1},\ldots,V_{r}$ is said to be $(\varepsilon,p)$-regular if \big{|}|V_{i}|-|V_{j}|\big{|}\leqslant 1 for all $i$ and $j$ and for all but at most $\varepsilon r^{2}$ pairs $(V_{i},V_{j})$, the graph induced between $V_{i}$ and $V_{j}$ is $(\varepsilon,p)$-regular. The class of graphs to which the Kohayakawa-Rödl regularity lemma applies are the so-called upper-uniform graphs. Given positive $\eta$ and $K$, we say that an $n$-vertex graph $G$ is $(\eta,p,K)$-upper-uniform if for all $W\subseteq V(G)$ with $|W|\geqslant\eta n$, the density of edges within $W$ satisfies $d(W)\leqslant Kp$. This condition is satisfied by many natural classes of graphs, including (a.a.s.) all subgraphs of random graphs of density $p$. The sparse regularity lemma of Kohayakawa and Rödl says the following.

For all positive $\varepsilon$, $K$, and $r_{0}$, there exist a positive constant $\eta$ and an integer $R$ such that for every $p\in$, the following holds. Every $(\varepsilon,p,K)$-upper-uniform graph with at least $r_{0}$ vertices admits an $(\varepsilon,p)$-regular partition of its vertex set into $r$ parts, for some $r\in\{r_{0},\ldots,R\}$.

We remark that a version of this theorem avoiding the need for the upper-uniformity assumption was recently proved by Scott .

The aforementioned embedding lemma roughly says that if we start with an arbitrary graph $H$, replace its vertices by large independent sets and its edges by $\varepsilon$-regular bipartite graphs with density much larger than $\varepsilon$, then this blown-up graph will contain a copy of $H$. To make it more precise, let $H$ be a graph on the vertex set $\{1,\ldots,v(H)\}$, let $\varepsilon$ and $p$ be as above, and let $n$ and $m$ be integers satisfying $0\leqslant m\leqslant n^{2}$. Let us denote by $\mathcal{G}(H,n,m,p,\varepsilon)$ the collection of all graphs $G$ constructed in the following way. The vertex set of $G$ is a disjoint union $V_{1}\cup\ldots\cup V_{v(H)}$ of sets of size $n$, one for each vertex of $H$. For each edge $\{i,j\}$ of $H$, we add to $G$ an $(\varepsilon,p)$-regular bipartite graph with $m$ edges between the sets $V_{i}$ and $V_{j}$. These are the only edges of $G$. With this notation in hand, we can state the embedding lemma. Given any graph $G$ as above, we define canonical copies of $H$ to be all copies of $H$ in $G$ in which (the image of) each vertex $i\in V(H)$ lies in the set $V_{i}\subseteq V(G)$.

For every graph $H$ and every positive $d$, there exist a positive $\varepsilon$ and an integer $n_{0}$ such that for every $n$ and $m$ with $n\geqslant n_{0}$ and $m\geqslant dn^{2}$, every $G\in\mathcal{G}(H,n,m,1,\varepsilon)$ contains a canonical copy of $H$.

One might hope that a similar statement holds when one replaces $1$ by an arbitrary $p$ and the assumption $m\geqslant dn^{2}$ by $m\geqslant pdn^{2}$, even if $p$ is a decreasing function of $n$. However, for an arbitrary function $p$, this is too much to hope for. Indeed, consider the random ‘blow-up’ of $H$, that is, the random graph $G$ obtained from $H$ by replacing each vertex of $H$ by an independent set of size $n$ and each edge of $H$ by a random bipartite graph with $pn^{2}$ edges. With high probability, the number of canonical copies of $H$ in $G$ will be about $p^{e(H)}n^{v(H)}$ and hence if $p^{e(H)}n^{v(H)}\ll pn^{2}$, then one can remove all copies of $H$ from $G$ by deleting a tiny proportion of all edges. Since in the above argument one may replace $H$ with an arbitrary subgraph $H^{\prime}\subseteq H$, it follows easilyNote that we also replace $p$ with some $p^{\prime}=(1+o(1))p$, and that the removal of $o(pn^{2})$ edges does not affect the $\varepsilon$-regularity conditions. that if $p\ll n^{-1/m_{2}(H)}$, then there are graphs in $\mathcal{G}(H,n,pn^{2},p,\varepsilon)$ that do not contain any canonical copies of $H$.

As in the case of Turán’s theorem for random graphs, see Section 1.2, one might still hope that if $p\geqslant Cn^{-1/m_{2}(H)}$ for some large constant $C$, then the natural sparse analogue of the embedding lemma discussed above holds. However, it was observed by Łuczak (see ) that, somewhat surprisingly, for any graph $H$ which contains a cycle and any function $p$ satisfying $p=o(1)$, there are graphs in $\mathcal{G}(H,n,pn^{2},p,\varepsilon)$ with no canonical copy of $H$. Nevertheless, it still seemed likely that such atypical graphs comprise so tiny a proportion of $\mathcal{G}(H,n,m,p,\varepsilon)$ that they do not appear in $G(n,p)$ asymptotically almost surely.

This was formalized in the following conjecture of Kohayakawa, Łuczak, and Rödl , usually referred to as the KŁR conjecture. Given a graph $H$, integers $m$ and $n$, a $p\in$, and a positive $\varepsilon$, let $\mathcal{G}^{*}(H,n,m,p,\varepsilon)$ denote the collection of graphs in $\mathcal{G}(H,n,m,p,\varepsilon)$ that contain no canonical copy of $H$. We will prove the conjecture in Section 9.

It is well-known that Theorem 1.9 easily implies Turán’s theorem for random graphs, Theorem 1.3, and also its stability version, Theorem 1.5. In fact, this was the original motivation behind the KŁR conjecture, see . Moreover, it was proved by Łuczak that Theorem 1.9 implies Theorems 1.6 and 1.7. The work of Conlon and Gowers and Schacht (see also ), as well as this work, have shown that one does not need to appeal to the sparse regularity lemma and to the KŁR conjecture in order to prove such extremal statements in random graphs. Nevertheless, there are still many beautiful corollaries of the conjecture that cannot (yet) be proved by other means. For discussion and derivation of some of them, we refer the reader to . Here, we present only one corollary of the KŁR conjecture, the threshold for asymmetric Ramsey properties of random graphs, which does not follow from the version of the conjecture proved in . The deduction of this result from the KŁR conjecture is essentially due to Kohayakawa and Kreuter .

5. Ramsey properties of random graphs

Let $H$ be a fixed graph and let $r$ be a positive integer. For an arbitrary graph $G$, we write $G\to(H)_{r}$ if every $r$-coloring of the edges of $G$ contains a monochromatic copy of $H$. It follows from the classical result of Ramsey that $K_{n}\to(H)_{r}$, provided that $n$ is sufficiently large. Ramsey properties of random graphs were first investigated by Frankl and Rödl and since then much effort has been devoted to their study. Most notably, Rödl and Ruciński established the following general threshold result.

For every graph $H$ that is not a forest, and every positive integer $r$, there exist positive constants $c$ and $C$ such that

In the above discussion, a copy of the same graph $H$ is forbidden in each of the $r$ color classes. A natural generalization of Theorem 1.10 would determine thresholds for so-called asymmetric Ramsey properties. For any graphs $G$, $H_{1},\ldots,H_{r}$, we write $G\to(H_{1},\ldots,H_{r})$ if for every coloring of the edges of $G$ with colors $1,\ldots,r$, there exists, for some $i\in[r]$, a copy of $H_{i}$ all of whose edges have color $i$. In the context of asymmetric Ramsey properties of random graphs, the following generalization of the $2$-density $m_{2}(\cdot)$ was introduced in . For two graphs $H_{1}$ and $H_{2}$, defineTo motivate this definition, set $p=n^{-1/m_{2}(H_{1},H_{2})}$ and observe that the edges of $G(n,p)$ which are contained in a copy of each subgraph $H_{1}^{\prime}\subseteq H_{1}$ have density roughly $n^{-1/m_{2}(H_{2})}$.

Kohayakawa and Kreuter formulated the following conjecture and proved it in the case when all $H_{i}$ are cycles.

Let $H_{1},\ldots,H_{r}$ be graphs with $1<m_{2}(H_{r})\leqslant\ldots\leqslant m_{2}(H_{1})$. Then there exist constants $c$ and $C$ such that

More accurately, the above conjecture was stated in only in the case $r=2$, but the above generalization is quite natural.To see why the graphs $H_{3},\ldots,H_{r}$ do not appear in the threshold, replace each of $H_{2},\ldots,H_{r}$ by the disjoint union $H^{\prime}=H_{2}\cup\cdots\cup H_{r}$, and note that $m_{2}(H^{\prime})=m_{2}(H_{2})$, see . There had been little progress on Conjecture 1.11 until quite recently, when the -statement was proved by Marciniszyn, Skokan, Spöhel, and Steger in the case where all of the $H_{i}$ are cliques, and the $1$-statement in the case $r=2$ was establishedIn their concluding remarks, the authors of moreover claim that their method can be extended to the setting with more than two colours, using ideas from . by Kohayakawa, Schacht, and Spöhel under very mild extra assumptions on $H_{1}$ and $H_{2}$. It was observed in [47, Theorem 31] that, using Theorem 1.9, the approach of Kohayakawa and Kreuter , which employs the sparse regularity lemma, can be adapted to yield a proof of the $1$-statement in Conjecture 1.11 for the following class of graphs.

Let $H_{1},\ldots,H_{r}$ be graphs with $1<m_{2}(H_{r})\leqslant\ldots\leqslant m_{2}(H_{1})$ and such that $H_{1}$ is strictly $2$-balanced. Then there exists a constant $C$ such that if $p_{n}\geqslant Cn^{-1/m_{2}(H_{1},H_{2})}$, then a.a.s.

For the deduction of Theorem 1.12 from Theorem 1.9, see and [47, Section 4].

6. Outline of the paper

The remainder of this paper is organized as follows. In Section 2, we state and discuss our main result, Theorem 2.2, which we then prove in Section 3. In Section 4, we discuss the applications of Theorem 2.2 in the context of subsets of $[n]$ with no $k$-term arithmetic progressions. In particular, we prove Theorem 1.1 and use it to derive Corollary 1.2. In Section 5, we prove two versions of the general transference theorem of Schacht [58, Theorem 3.3] (obtained independently, in a slightly different form, by Conlon and Gowers ) – a ‘random’ version suited for extremal problems in sparse random discrete structures and its ‘counting’ counterpart that generalizes Theorem 1.1. In Section 6, we prove ‘random’ and ‘counting’ versions of the general stability result of Conlon and Gowers in a form that is easily comparable with [56, Theorem 3.4]. In Section 7, we discuss several applications of Theorem 2.2 in the context of the Turán problem in sparse random graphs. In particular, using the results of Sections 5 and 6 we give new proofs of the sparse random analogues (stated above) of the classical theorems of Erdős and Stone, and Erdős and Simonovits, see Section 1.2. In Section 8, we discuss applications of Theorem 2.2 to the problem of describing the typical structure of a sparse graph without a forbidden subgraph. In particular, we prove sparse analogues of classical theorems of Erdős, Frankl, and Rödl and Erdős, Kleitman, and Rothschild, see Section 1.3. Finally, in Section 9, we use Theorem 2.2 to prove the KŁR conjecture for every graph $H$.

The Main Theorem

In this section, we present the main result of this paper, Theorem 2.2, which gives a structural characterization of the collection of all independent sets in a large class of uniform hypergraphs. Let us stress here that all of the hypergraphs we consider are allowed to have multiple edges; moreover, we shall always count edges with multiplicities.

We start with an important definition. Recall that a family of sets $\mathcal{F}\subseteq\mathcal{P}(V)$ is called increasing (or an upset) if it is closed under taking supersets, that is, if for every $A,B\subseteq V$, $A\in\mathcal{F}$ and $A\subseteq B$ imply that $B\in\mathcal{F}$.

Let $\mathcal{H}$ be a uniform hypergraph with vertex set $V$, let $\mathcal{F}$ be an increasing family of subsets of $V$ and let $\varepsilon\in(0,1]$. We say that $\mathcal{H}$ is $(\mathcal{F},\varepsilon)$-dense if

A moment of thought reveals that for an arbitrary hypergraph $\mathcal{H}$ and $\varepsilon\in(0,1]$, it is extremely simple to find families $\mathcal{F}\subseteq\mathcal{P}(V(\mathcal{H}))$ for which $\mathcal{H}$ is $(\mathcal{F},\varepsilon)$-dense. To this end, let

and note that $\mathcal{F}_{\varepsilon}$ is increasing and $\mathcal{H}$ is $(\mathcal{F}_{\varepsilon},\varepsilon)$-dense. In fact, the families $\mathcal{F}$ for which $\mathcal{H}$ is $(\mathcal{F},\varepsilon)$-dense are precisely all increasing subfamilies of $\mathcal{F}_{\varepsilon}$.

In this work, we will be interested in upsets that admit a much more ‘constructive’ description than that of $\mathcal{F}_{\varepsilon}$. Many such families arise naturally in the study of extremal and structural problems in combinatorics. For example, consider the $k$-uniform hypergraph $\mathcal{H}_{1}$ on the vertex set $[n]$ whose edges are all $k$-term arithmetic progressions in $[n]$ and let $\mathcal{F}_{1}$ be the collection of all subsets of $[n]$ with at least $\delta n$ elements. Clearly, $\mathcal{F}_{1}$ is an upset and it follows from the famous theorem of Szemerédi that $\mathcal{H}_{1}$ is $(\mathcal{F}_{1},\varepsilon)$-dense for some positive $\varepsilon$ depending only on $\delta$ and $k$, see Section 4. Similarly, consider the $3$-uniform hypergraph $\mathcal{H}_{2}$ on the vertex set $E(K_{n})$ whose edges are edge sets of all copies of $K_{3}$ in the complete graph $K_{n}$ and let $\mathcal{F}_{2}$ be the family of all $n$-vertex graphs (subgraphs of $K_{n}$) with at least $(1/2-\varepsilon)\binom{n}{2}$ edges such that every $2$-coloring of its vertices yields at least $\delta n^{2}$ monochromatic edges. Again, $\mathcal{F}_{2}$ is increasing and it follows from the stability theorem of Erdős and Simonovits and the triangle removal lemma of Ruzsa and Szemerédi that $\mathcal{H}_{2}$ is $(\mathcal{F}_{2},\varepsilon)$-dense, provided that $\varepsilon$ is sufficiently small as a function of $\delta$.

Our main result roughly says the following. If $\mathcal{H}$ is a uniform hypergraph that is $(\mathcal{F},\varepsilon)$-dense for some family $\mathcal{F}$ and whose edge distribution satisfies certain natural boundedness conditions, then the collection $\mathcal{I}(\mathcal{H})$ of all independent sets in $\mathcal{H}$ admits a partition into relatively few classes such that all independent sets in one class are essentially contained in a single set $A\not\in\mathcal{F}$. Before we state the result, we first need to quantify the above boundedness conditions for the edge distribution of a hypergraph. Given a hypergraph $\mathcal{H}$, for each $T\subseteq V(\mathcal{H})$, we defineWe emphasize that if $\mathcal{H}$ has multiple edges, then $\{e\in\mathcal{H}\colon T\subseteq e\}$ should be thought of as a multi-set. In other words, $\deg_{\mathcal{H}}(T)$ is the number of edges of $\mathcal{H}$, counted with multiplicities, which contain $T$.

Recall that $\mathcal{I}(\mathcal{H})$ denotes the family of all independent sets in $\mathcal{H}$. The following theorem is our main result.

Then there exists a family $\mathcal{S}\subseteq\binom{V(\mathcal{H})}{\leqslant Cp\cdot v(\mathcal{H})}$ and functions $f\colon\mathcal{S}\to\overline{\mathcal{F}}$ and $g\colon\mathcal{I}(\mathcal{H})\to\mathcal{S}$ such that for every $I\in\mathcal{I}(\mathcal{H})$,

Roughly speaking, if $\mathcal{H}$ satisfies certain technical conditions, then each independent set $I$ in $\mathcal{H}$ can be labelled with a small subset $g(I)$ in such a way that all sets labelled with some $S\in\mathcal{S}$ are essentially contained in a single set $f(S)$ that contains very few edges of $\mathcal{H}$. We remark that the constant $C$ in the theorem has only a polynomial dependence on $\varepsilon$. Unfortunately, however, in most of our applications $\varepsilon$ will have a tower-type dependence on some other parameter.

Theorem 2.2 will be proved in Section 3. We end this section with a short informal discussion of its consequences. As we have already mentioned, Theorem 2.2 combined with some classical extremal results on discrete structures has strikingly strong implications. Let us briefly explain why this is so. Many classical extremal problems ask for an estimate on the number of independent sets (of a certain size) in some auxiliary uniform hypergraph. If applicable, Theorem 2.2 implies that all such independent sets are almost contained in one of very few sets that are almost independent, that is, contain a small number of copies of some forbidden substructure. If we know a good characterization of sets that are almost independent in the above sense, which is often the case, we can easily obtain an upper bound on the number of independent sets. For example, consider the problem of counting subsets of $[n]$ with no $k$-term AP and recall the definition of $\mathcal{H}_{1}$ and $\mathcal{F}_{1}$ from the beginning of this section. Theorem 2.2, applied to this pair, implies that every subset of $[n]$ with no $k$-term AP is essentially contained in one of at most $\binom{n}{O(n^{1-1/(k-1)})}$ sets of size at most $\delta n$ each, where $\delta$ is an arbitrarily small positive constant. This easily implies that if $m\gg n^{1-1/(k-1)}$, then there are at most $\binom{2\delta n}{m}$ sets of size $m$ with no $k$-term AP. For more details, we refer the reader to Section 4.

Proof of the main theorem

In this section, we shall prove Theorem 2.2. The main ingredient in the proof is the following proposition, which (roughly) says that Theorem 2.2 holds in the special case when $\mathcal{F}$ is the family of all subsets of $V(\mathcal{H})$ with at least $(1-\delta)v(\mathcal{H})$ elements. Theorem 2.2 follows by applying Proposition 3.1 a constant number of times.

Then there exist a family $\mathcal{S}\subseteq\binom{V(\mathcal{H})}{\leqslant(k-1)p\cdot v(\mathcal{H})}$ and functions $f_{0}\colon\mathcal{S}\to\mathcal{P}(V(\mathcal{H}))$ and $g_{0}\colon\mathcal{I}(\mathcal{H})\to\mathcal{S}$ such that for every $I\in\mathcal{I}(\mathcal{H})$,

Moreover, if for some $I,I^{\prime}\in\mathcal{I}(\mathcal{H})$, $g_{0}(I)\subseteq I^{\prime}$ and $g_{0}(I^{\prime})\subseteq I$, then $g_{0}(I)=g_{0}(I^{\prime})$.

The final line of Proposition 3.1 states that the labelling function $g_{0}$ exhibits a certain consistency. This property of $g_{0}$, which may look somewhat puzzling, will be crucial in the proof of Theorem 2.2.

In order to prove Proposition 3.1, given an independent set $I\in\mathcal{I}(\mathcal{H})$, we shall construct a sequence $(B_{k-1},\ldots,B_{q})$ of subsets of $I$ with $|B_{k-1}|,\ldots,|B_{q}|\leqslant pv(\mathcal{H})$, for some $q\in[k-1]$, and use it to define a sequence $(\mathcal{H}_{k-1},\ldots,\mathcal{H}_{r})$, where $r\in\{q,q+1\}$, of hypergraphs such that the following holds for each $i\in\{r,\ldots,k-1\}$:

$\mathcal{H}_{i}$ is an $i$-uniform hypergraph on the vertex set $V(\mathcal{H})$,

$I$ is an independent set in $\mathcal{H}_{i}$,

\Delta_{1}(\mathcal{H}_{i})\leqslant O\big{(}e(\mathcal{H}_{i})/v(\mathcal{H}_{i})\big{)}, and

$e(\mathcal{H}_{i})\geqslant\Omega(p^{k-i}e(\mathcal{H}))$.

We shall be able to do it in such a way that in the end, there will be a set $A\subseteq V(\mathcal{H})$ of size at most $(1-\delta)v(\mathcal{H})$ such that the remaining elements of $I$ (i.e., the set $I\setminus S$, where $S=B_{k}\cup\cdots\cup B_{q}$) must all lie inside $A$. If $r=1$, then we will simply let $A$ be the set of non-edges of the $1$-uniform hypergraph $\mathcal{H}_{1}$; in this case, the upper bound on $|A|$ will follow from (c) and (d). If $r>1$, then we will obtain an appropriate $A$ while trying (and failing) to construct the hypergraph $\mathcal{H}_{r-1}$ using the hypergraph $\mathcal{H}_{r}$ and the set $B_{r}$. Crucially, this set $A$ will depend solely on $S$, that is, if for some pair $I,I^{\prime}\in\mathcal{I}(\mathcal{H})$ our procedure generates $(S,A)$ and $(S^{\prime},A^{\prime})$, respectively, and if $S=S^{\prime}$, then also $A=A^{\prime}$. This will allow us to set $g_{0}(I)=S$ and $f_{0}(S)=A$.

For the remainder of this section, let us fix $k$, $c$, $p$, and $\mathcal{H}$ as in the statement of Proposition 3.1. Without loss of generality, we may assume that $c\geqslant 1$. Let $I$ be an independent set in $\mathcal{H}$. We shall describe a procedure of choosing the sets $B_{i}\subseteq I$ and constructing the hypergraphs $\mathcal{H}_{i}$ as above. This procedure, which we shall term the Scythe Algorithm, lies at the heart of the proof of Proposition 3.1.

The general strategy used in the Scythe Algorithm, that of selecting a small set $S$ of high-degree vertices and using it to define a set $A$ such that $S\subseteq I\subseteq A\cup S$, dates back to the work of Kleitman and Winston , who used it to bound the number of independent sets in graphs satisfying the following local density condition: all sufficiently large vertex sets induce subgraphs with many edges. Recently, Balogh and Samotij refined the ideas of Kleitman and Winston and obtained a bound on the number of independent sets in uniform hypergraphs satisfying a similar local density condition. Even more recently, Alon, Balogh, Morris and Samotij used similar ideas to bound the number of independent sets in ‘almost linear’ $3$-uniform hypergraphs satisfying a more general density condition termed $(\alpha,\mathcal{B})$-stability, see Definition 6.1. Here, we combine, generalize, and refine all of the above approaches and make them work in the general setting of $(\mathcal{F},\varepsilon)$-dense uniform hypergraphs.

At each step of the Scythe Algorithm, we shall order the vertices of a certain subhypergraph of $\mathcal{H}$ with respect to their degrees in that subhypergraph. For the sake of brevity and clarity of the presentation, let us make the following definition.

Given a hypergraph $\mathcal{G}$, we define the max-degree order on $V(\mathcal{G})$ as follows:

Fix an arbitrary total ordering of $V(\mathcal{G})$.

For each $j\in\{1,\ldots,v(\mathcal{G})\}$, let $u_{j}$ be the maximum-degree vertex in the hypergraph \mathcal{G}\big{[}V(\mathcal{G})\setminus\{u_{1},\ldots,u_{j-1}\}\big{]}; ties are broken by giving preference to vertices which come earlier in the order chosen in (1).

The max-degree order on $V(\mathcal{G})$ is $(u_{1},\ldots,u_{v(\mathcal{G})})$.

Finally, we write $W(u)$ to denote the initial segment of the max-degree order on $V(\mathcal{G})$ that ends with $u$, i.e., for every $j$, we let $W(u_{j})=\{u_{1},\ldots,u_{j}\}$.

We remark here that the only property of the max-degree order that will be important for us is that for every $j\in\{1,\ldots,v(\mathcal{G})\}$, the degree of the vertex $u_{j}$ in the hypergraph $\mathcal{G}[V(\mathcal{G})\setminus W(u_{j-1})]$ is at least as large as the average degree of this hypergraph.

Let $b=pv(\mathcal{H})$ and for each $i\in[k]$, let $c_{i}=(ck2^{k+1})^{i-k}$.

The key properties that we would like the constructed hypergraph $\mathcal{H}_{i}$ to possess are:

$\mathcal{H}_{i}$ is $i$-uniform and $V(\mathcal{H}_{i})=V(\mathcal{H})$,

$I$ is an independent set in $\mathcal{H}_{i}$,

$e(\mathcal{H}_{i})\geqslant c_{i}p^{k-i}e(\mathcal{H})$.

Set $\mathcal{H}_{k}=\mathcal{H}$ and note that (P1)–(P4) are vacuously satisfied for $i=k$. The main step of the Scythe Algorithm will be a procedure that, given $\mathcal{H}_{i+1}$ and $I$ satisfying (P1)–(P4), outputs a set $B_{i}\subseteq I$ of cardinality at most $b$, a set $A_{i}\subseteq V(\mathcal{H})$ with the property that $I\setminus B_{i}\subseteq A_{i}$, and a hypergraph $\mathcal{H}_{i}$ satisfying (P1)–(P3). Moreover, if the constructed $\mathcal{H}_{i}$ does not satisfy (P4), then we have $|A_{i}|\leqslant(1-c_{i})v(\mathcal{H})$. Crucially, these $A_{i}$ and $\mathcal{H}_{i}$ depend solely on $B_{i}$ and $\mathcal{H}_{i+1}$, that is, if on two inputs $(\mathcal{H}_{i+1},I)$ and $(\mathcal{H}_{i+1},I^{\prime})$, the procedure outputs the same set $B_{i}$, it also outputs the same $A_{i}$ and $\mathcal{H}_{i}$.

Given an $(i+1)$-uniform hypergraph $\mathcal{H}_{i+1}$ and an independent set $I\in\mathcal{I}(\mathcal{H}_{i+1})$, set $\mathcal{A}_{i+1}^{(0)}=\mathcal{H}_{i+1}$ and let $\mathcal{H}_{i}^{(0)}$ be the empty hypergraph on the vertex set $V(\mathcal{H})$. For $j=0,\ldots,b-1$, do the following:

If I\cap V\big{(}\mathcal{A}_{i+1}^{(j)}\big{)}=\emptyset, then set $\mathcal{H}_{i}=\mathcal{H}_{i}^{(0)}$, $A_{i}=\emptyset$, and $B_{i}=\{u_{0},\ldots,u_{j-1}\}$ and STOP.

Let $u_{j}$ be the first vertex of $I$ in the max-degree order on V\big{(}\mathcal{A}_{i+1}^{(j)}\big{)}.

Let $\mathcal{H}_{i}^{(j+1)}$ be the hypergraph on the vertex set $V(\mathcal{H})$ defined by:

Let $\mathcal{A}_{i+1}^{(j+1)}$ be the hypergraph on the vertex set V\big{(}\mathcal{A}_{i+1}^{(j)}\big{)}\setminus W(u_{j}) defined by:We emphasize that $W(u_{j})$ is defined relative to the max-degree order on $V(\mathcal{A}_{i+1}^{(j)})$.

Finally, set $\mathcal{H}_{i}=\mathcal{H}_{i}^{(b)}$, A_{i}=V\big{(}\mathcal{A}_{i+1}^{(b)}\big{)}, and $B_{i}=\{u_{0},\ldots,u_{b-1}\}$.

We shall now establish various properties of the Scythe Algorithm. We begin by making some basic (but key) observations.

The following hold for every $i\in[k-1]$:

$\mathcal{H}_{i}$ is $i$-uniform and $V(\mathcal{H}_{i})=V(\mathcal{H})$.

If $I\in\mathcal{I}(\mathcal{H}_{i+1})$, then $I\in\mathcal{I}(\mathcal{H}_{i})$.

$B_{i}\subseteq I\subseteq A_{i}\cup B_{i}$.

The hypergraph $\mathcal{H}_{i}$ and the set $A_{i}$ depend only on $\mathcal{H}_{i+1}$ and the set $B_{i}$.

Property (a) is trivial. To see (b), simply observe that each edge of $\mathcal{H}_{i}$ is of the form $D\setminus\{u\}$ for some $D\in\mathcal{H}_{i+1}$ and $u\in I$. Thus, if $I$ contains an edge of $\mathcal{H}_{i}$, it must also contain an edge of $\mathcal{H}_{i+1}$. To see (c), observe that for each $j$, $u_{j}$ is the first vertex of $I$ in the max-degree order on V\big{(}\mathcal{A}_{i+1}^{(j)}\big{)} and hence $W(u_{j})\cap I=\{u_{j}\}$. It follows that $B_{i}\subseteq I$ and that $I\setminus A_{i}=B_{i}$. Note in particular that if $A_{i}=\emptyset$, then I\cap V\big{(}\mathcal{A}_{i+1}^{(j)}\big{)}=\emptyset for some $j\in\{0,\ldots,b\}$, which implies that $B_{i}=I$. Finally, to prove (d), observe that all steps of the Scythe Algorithm are deterministic and that every element of $I$ that we need to observe in order to define $A_{i}$ and $\mathcal{H}_{i}$ is placed in $B_{i}$. More precisely, note that while choosing the vertex $u_{j}$, we only need to know the first vertex of $I$ in the max-degree order on V\big{(}\mathcal{A}_{i+1}^{(j)}\big{)}; the remaining vertices remain unobserved. Since we have $W(u_{j})\cap B_{i}=W(u_{j})\cap I=\{u_{j}\}$, this information can be recovered from $B_{i}$. Thus, at each step, the hypergraph $\mathcal{H}_{i}^{(j+1)}$ can be recovered from $\mathcal{H}_{i}^{(j)}$ and $B_{i}$, and the hypergraph $\mathcal{A}_{i+1}^{(j+1)}$ can be recovered from $\mathcal{A}_{i+1}^{(j)}$, $\mathcal{H}_{i}^{(j+1)}$ and $B_{i}$. Hence, a trivial inductive argument proves that, if the algorithm does not stop in step (1), for each $j\in\{0,\ldots,b\}$, the hypergraphs $\mathcal{H}_{i}^{(j)}$ and $\mathcal{A}_{i+1}^{(j)}$ are determined by $\mathcal{H}_{i+1}$ and the set $B_{i}$, as required. Finally, the algorithm stops in step (1) if and only if $|B_{i}|<b$. If this happens, then $\mathcal{H}_{i}$ and $A_{i}$ are empty. ∎

We next show that the Scythe Algorithm exhibits a certain ‘consistency’ while generating its output. This property will be important in the proof of Proposition 3.1.

Suppose that on inputs $(\mathcal{H}_{i+1},I)$ and $(\mathcal{H}_{i+1},I^{\prime})$, the Scythe Algorithm outputs $(A_{i},B_{i},\mathcal{H}_{i})$ and $(A_{i}^{\prime},B_{i}^{\prime},\mathcal{H}_{i}^{\prime})$, respectively. If $B_{i}\subseteq I^{\prime}$ and $B_{i}^{\prime}\subseteq I$, then $(A_{i},B_{i},\mathcal{H}_{i})=(A_{i}^{\prime},B_{i}^{\prime},\mathcal{H}_{i}^{\prime})$.

By Lemma 3.5, it suffices to show that $B_{i}=B_{i}^{\prime}$. Let us first consider the (degenerate) case when $\min\{|B_{i}|,|B_{i}^{\prime}|\}<b$. Without loss of generality, we may assume that $|B_{i}|<b$. This means that, while running on $(\mathcal{H}_{i+1},I)$, the Scythe Algorithm stopped in step (1). By Lemma 3.5, it follows that $B_{i}=I$ and hence $B_{i}^{\prime}\subseteq B_{i}$, which means that $|B_{i}^{\prime}|<b$ and therefore $B_{i}^{\prime}=I^{\prime}$. Hence, $B_{i}=B_{i}^{\prime}$, as claimed. On the other hand, if $|B_{i}|=|B_{i}^{\prime}|=b$ and $B_{i}\neq B_{i}^{\prime}$, then there must exist some $j$ such that $u_{j}\neq u_{j}^{\prime}$. Let $j$ be the smallest such index. Note that by the minimality of $j$, we have \mathcal{A}_{i+1}^{(j)}=\big{(}\mathcal{A}_{i+1}^{(j)}\big{)}^{\prime}=\mathcal{A}. Since $u_{j}\neq u_{j}^{\prime}$, one of these vertices comes earlier in the max-degree order on $V(\mathcal{A})$; without loss of generality, we may suppose that it is $u_{j}$. Since $B_{i}\subseteq I^{\prime}$, it follows that $u_{j}\in I^{\prime}$ and hence the Algorithm, while running on the input $(\mathcal{H}_{i+1},I^{\prime})$, would not pick $u_{j}^{\prime}$ in step $j$, a contradiction. This shows that in fact $B_{i}=B_{i}^{\prime}$, as required. ∎

where the last inequality follows from (7). ∎

Next, let us establish an easy bound on the numbers $\Delta_{1}^{i}$.

$\Delta_{1}^{i}\leqslant c2^{k}p^{k-i}\frac{e(\mathcal{H})}{v(\mathcal{H})}$ for every $i\in\{1,\ldots,k\}$.

Finally, we show that if $\mathcal{H}_{i+1}$ satisfies (P3) and (P4), then either $\mathcal{H}_{i+1}$ also satisfies (P4) or we have $|A_{i}|\leqslant(1-c_{i})v(\mathcal{H})$. Recall that $c_{i}=(ck2^{k+1})^{i-k}$.

or $|A_{i}|\leqslant(1-c_{i})v(\mathcal{H})$.

If the Scythe Algorithm stops in step (1), then $|A_{i}|=0$ and there is nothing to prove. Hence, we may assume that steps (2)–(4) are executed $b$ times. Note that, for each $j\in\{0,\ldots,b-1\}$, we have

Hence, if (i+1)e\big{(}\mathcal{A}_{i+1}^{(j+1)}\big{)}\geqslant e\big{(}\mathcal{H}_{i+1}\big{)} for every $j\in\{0,\ldots,b-1\}$, then

since $b=p\cdot v(\mathcal{H})$, as required. Thus, we may assume that for some $j$,

Recall that $\mathcal{A}_{i+1}^{(0)}=\mathcal{H}_{i+1}$ and observe that for every $j\in\{0,\ldots,b-1\}$,

Since we assumed that e(\mathcal{A}_{i+1}^{(b)})<e\big{(}\mathcal{H}_{i+1}\big{)}/(i+1), see (11), and $\mathcal{H}_{i}=\mathcal{H}_{i}^{(b)}$, it follows that if

Case 2: $\sum_{j=0}^{b-1}|W(u_{j})|\geqslant\frac{1}{4\Delta_{1}^{i+1}}\cdot e(\mathcal{H}_{i+1})$.

We claim that in this case, $|A_{i}|\leqslant(1-c_{i})v(\mathcal{H})$. Indeed, we have

Recall that $\Delta_{1}^{i+1}\leqslant c2^{k}p^{k-i-1}\frac{e(\mathcal{H})}{v(\mathcal{H})}$ by Lemma 3.8. Thus,

since $e(\mathcal{H}_{i+1})\geqslant c_{i+1}p^{k-(i+1)}e(\mathcal{H})$ and $c_{i+1}/(c2^{k+2})\geqslant c_{i}$. ∎

2. The proof of Proposition 3.1 and Theorem 2.2

Let $k$ be an integer and let $c$ be a positive constant. Furthermore, let $p\in(0,1)$ and let $\mathcal{H}$ be a $k$-uniform hypergraph that satisfy the assumptions of Proposition 3.1. Let $\delta=(ck2^{k+1})^{-k}$ and $b=pv(\mathcal{H})$. We will use the Scythe Algorithm, described in Section 3.1, to construct a family $\mathcal{S}$ and functions $f_{0}$ and $g_{0}$ as in the statement of Proposition 3.1. We obtain them by running the following algorithm (with $\mathcal{H}_{k}=\mathcal{H}$) on every independent set $I\in\mathcal{I}(\mathcal{H})$. We shall define $f_{0}$ somewhat implicitly by defining a function $f_{0}^{*}\colon\mathcal{I}(\mathcal{H})\to\mathcal{P}(V(\mathcal{H}))$ that is constant on the set $g_{0}^{-1}(S)$ for every $S\in\mathcal{S}$.

Given an $I\in\mathcal{I}(\mathcal{H})$, set $i=k-1$ and repeat the following:

Apply the Scythe Algorithm to $\mathcal{H}_{i+1}$ and $I$. Suppose that it outputs $\mathcal{H}_{i}$, $A_{i}$ and $B_{i}$.

If $|A_{i}|\leqslant(1-\delta)v(\mathcal{H})$, then set $q=i$, $r=i+1$ and STOP.