Short proof of the hypergraph container theorem

Rajko Nenadov School of Computer Science, University of Auckland, New Zealand. Email: [email protected]. Research supported by the New Zealand Marsden Fund. Huy Tuan Pham Department of Mathematics, Stanford University, Stanford, CA 94305. Email: [email protected]. Research supported by a Clay Research Fellowship and a Stanford Science Fellowship.

Abstract

We present a short and simple proof of the celebrated hypergraph container theorem of Balogh–Morris–Samotij and Saxton–Thomason. On a high level, our argument utilises the idea of iteratively taking vertices of largest degree from an independent set and constructing a hypergraph of lower uniformity which preserves independent sets and inherits edge distribution. The original algorithms for constructing containers also remove in each step vertices of high degree which are not in the independent set. Our modified algorithm postpones this until the end, which surprisingly results in a significantly simplified analysis.

1 Introduction

The method of containers is a powerful technique in combinatorics used to produce a small number of clusters encompassing independent sets of a given hypergraph. While in some applications one follows the idea of the method and the general principles for building such clusters, quite often one can apply off the shelf tools. The most such applicable tool has been developed independently by Balogh, Morris, and Samorij [1] and Saxton and Thomason [9], and it is this result that is commonly referred to as the hypergraph container theorem. For an introduction to the method, the hypergraph container theorem, and its many suprising applications, we refer the reader the ICM survey [2]. A number of different proofs and versions of this result have been obtained since [3, 4, 5, 7, 8, 10, 11]. We present a simple and short proof of a slight generalisation of the original theorem. Two other short proofs have been obtained very recently by Campos and Samotij [6].

Let $V$ be a finite set. Given a subset $X\subseteq V$ , let $\langle X\rangle=\{S\subseteq V\colon X\subseteq S\}$ . We say a probability measure $\nu$ over $2^{V}$ is $(p,K)$ -uniformly-spread if for every non-empty $X\subseteq V$ we have $\nu(\langle X\rangle)\leq Kp^{|X|-1}/|V|$ . Uniform signifies that the measure is fairly uniform from the point of view of elements of $V$ . Throughout the paper we use $V=V(\mathcal{H})$ and $N=|V|$ , where $\mathcal{H}$ is a given hypergraph. If all edges in a hypergraph $\mathcal{H}$ have size at most $\ell$ , we say that $\mathcal{H}$ is an $(\leq\ell)$ -graph.

Theorem 1.1.

For every $\ell\in\mathbb{N}$ and $K,\varepsilon>0$ there exists $T>0$ such that the following holds. Suppose $\mathcal{H}$ is an $(\leq\ell)$ -graph, and let $\nu$ be $(p,K)$ -uniformly-spread measure over $2^{V}$ supported on $\mathcal{H}$ , for some $p\in(0,1]$ . Then for every independent set $I\subseteq V(\mathcal{H})$ there exists $F\subseteq I$ and $C=C(F)\subseteq V$ such that $|F|\leq TNp$ , $\nu(\mathcal{H}[C])<\varepsilon$ , and $I\subseteq C\cup F$ .

If $\nu$ is uniform on $\mathcal{H}$ , we obtain original hypergraph container theorems [1, 9]. Dependence of $T$ on the uniformity is of order $O(2^{\ell^{2}})$ , which is also along the lines of the original results. Near-optimal dependence was obtained by Balogh and Samotij [3] and Campos and Samotij [6].

2 Proof

Our proof bears resemblance with the proof from [1, 9]. On a high level, we choose $F$ in Theorem 1.1 by greedily taking vertices from $I$ with largest degree with respect to $\nu$ and construct a hypergraph of lower uniformity given by (parts) of hyperedges containing vertices from $F$ . A common feature in many of the proofs utilising a similar idea is that one also keeps track of the vertices which are not in $I$ but have larger degree than the last chosen vertex in $F$ . The main novelty here is that we completely avoid this, unless we are in the case the resulting hypergraph of lower uniformity is not sufficiently dense to proceed with the induction. In this case, we show that removing vertices of high degree immediately yields a desired container. It is worth noting that the proofs from [1, 9] also have a similar case distinction, however the analysis in our cases turns out to be significantly simpler.

Theorem 1.1 follows by iterated application of the following lemma, known as the hypergraph container lemma.

Lemma 2.1.

For every $\ell\in\mathbb{N}$ and $K>0$ there exists $\delta>0$ such that the following holds. Suppose $\mathcal{H}$ is an $(\leq\ell)$ -graph, and let $\nu$ be a $(p,K)$ -uniformly-spread measure over $2^{V}$ supported on $\mathcal{H}$ , for some $p\in(0,1]$ . Then for every independent set $I\subseteq V$ there exists $F\subseteq I$ and $C=C(F)\subseteq V$ such that $|F|\leq\ell Np$ , $|C|\leq(1-\delta)N$ , and $I\subseteq C\cup F$ . Moreover, $C$ can be unambigously constructed from any $F\subseteq\hat{F}\subseteq I$ .

Proof.

We prove the lemma by induction on $\ell$ . For $\ell=1$ , take $F=\varnothing$ and $C\subseteq V$ to be the set of all vertices $v\in V$ with $\nu(v)=0$ . As there are at least $N/K$ vertices with strictly positive measure, the lemma holds for $\delta=1/K$ . We now prove the lemma for $\ell\geq 2$ . Without loss of generality, we may assume $|I|\geq Np$ .

Set $F=\varnothing\subseteq I$ , $\mathcal{L}=\varnothing\subseteq 2^{V}$ , and $\mathcal{D},\mathcal{H}^{\prime}=\varnothing\subseteq\mathcal{H}$ . Repeat the following for $Np$ rounds: Take $v\in I\smallsetminus F$ to be a largest vertex with respect to $\nu(\langle v\rangle\cap\mathcal{R})$ , where $\mathcal{R}=\mathcal{H}[V\smallsetminus F]\smallsetminus\mathcal{D}$ (tie-breaking done in some canonical way, e.g. by agreeing on the ordering of $V$ ). Add $v$ to $F$ , set $\mathcal{H}^{\prime}=\mathcal{H}^{\prime}\cup(\langle v\rangle\cap\mathcal{R})$ , and for each $X\in 2^{V}\smallsetminus\mathcal{L}$ of size $|X|\leq\ell-1$ such that

\nu(\langle X\rangle\cap\mathcal{H}^{\prime})>Kp^{|X|}/N,

(1)

add $X$ to $\mathcal{L}$ and set $\mathcal{D}=\mathcal{D}\cup(\langle X\rangle\cap\mathcal{R})$ .

A few observations about the process. First, as $\nu$ is $(p,K)$ -uniformly-spread the value $\nu(\langle X\rangle\cap\mathcal{H}^{\prime})$ increases by at most $\nu(\langle X\cup\{v\}\rangle)\leq Kp^{|X|}/N$ after adding a vertex $v$ to $F$ . Once a subset $X$ satisfies (1) no more hyperedges which contain $X$ are added to $\mathcal{H}^{\prime}$ , thus at the end of the process we have

\nu(\langle X\rangle\cap\mathcal{H}^{\prime})\leq 2Kp^{|X|}/N

(2)

for every $X\subseteq V$ of size $|X|\leq\ell-1$ . Second, given $F\subseteq\hat{F}\subseteq I$ , we can reconstruct $F$ from $\hat{F}$ together with the order in which the vertices were added, thus we can also reconstruct $\mathcal{H^{\prime}}$ and $\mathcal{R}$ .

We next derive several useful lower bounds on $\nu(\mathcal{H}^{\prime})$ . First we show that if $\nu(\mathcal{D})$ is large, then $\nu(\mathcal{H}^{\prime})$ is also large. In particular, the following holds:

\displaystyle\nu(\mathcal{H}^{\prime})\geq 2^{-\ell}p\nu(\mathcal{D}).

(3)

Indeed, for each $e\in\mathcal{D}$ there exists $X\in\mathcal{L}$ such that $e\in\langle X\rangle$ . Thus, $\sum_{X\in\mathcal{L}}\nu(\langle X\rangle)\geq\nu(\mathcal{D})$ . On the other hand, we have by (1) that

\sum_{X\in\mathcal{L}}\nu(\langle X\rangle\cap\mathcal{H}^{\prime})>\sum_{X\in\mathcal{L}}Kp^{|X|}/N\geq p\sum_{X\in\mathcal{L}}\nu(\langle X\rangle).

Here in the last inequality we use that $\nu$ is $(p,K)$ -uniformly spread. Furthermore, each edge $e$ in $\mathcal{H}^{\prime}$ may contribute to at most $2^{\ell}$ terms $\nu(\langle X\rangle\cap\mathcal{H}^{\prime})$ . Hence,

\displaystyle\nu(\mathcal{H}^{\prime})\geq 2^{-\ell}\sum_{X\in\mathcal{L}}\nu(\langle X\rangle\cap\mathcal{H}^{\prime})>2^{-\ell}p\nu(\mathcal{D}),

as claimed in (3).

Next, we show that

\displaystyle\nu(\mathcal{H}^{\prime})\geq(Np)\max_{v\in I\smallsetminus F}\nu(\langle v\rangle\cap\mathcal{R}).

(4)

Let $\mathcal{R}_{i}$ denote the hypergraph $\mathcal{R}$ at the moment when the $i$ -th vertex $v_{i}$ was added to $F$ (thus $\mathcal{R}=\mathcal{R}_{|F|}$ ). We observe that, since $\mathcal{R}$ is non-increasing and by our choice of $v$ in each step,

\displaystyle\nu(\mathcal{H}^{\prime})\geq\sum_{i=1}^{|F|}\nu(\langle v_{i}\rangle\cap\mathcal{R}_{i})\geq\sum_{i=1}^{|F|}\max_{v\in I\smallsetminus F}\nu(\langle v\rangle\cap\mathcal{R}_{|F|}),

yielding (4).

Let $\alpha=2^{-\ell-2}$ . We now distinguish two cases, where if $\nu(\mathcal{H}^{\prime})$ is large, then we can apply the inductive hypothesis to an appropriate $(\leq\ell-1)$ -graph, and otherwise we can immediately find a small container $C$ for which $I\smallsetminus F\subseteq C$ .

Case 1: $\nu(\mathcal{H}^{\prime})\geq\alpha p$ . Let $\mathcal{H}^{\prime\prime}$ denote the $(\leq\ell-1)$ -graph consisting of sets $X$ such that $X=H^{\prime}\smallsetminus F$ for some $H^{\prime}\in\mathcal{H}^{\prime}$ . Set $\nu^{\prime}$ to be the probability measure over $2^{V\smallsetminus F}$ given by

\nu^{\prime}(X)\,\propto\,\begin{cases}\nu((X\cup 2^{F})\cap\mathcal{H}^{\prime}),&\text{if }X\in\mathcal{H}^{\prime\prime},\\ 0,&\text{otherwise.}\end{cases}

From (2) and $\nu(\mathcal{H}^{\prime})\geq\alpha p$ we conclude that $\nu^{\prime}$ is $(2K\alpha^{-1},p)$ -uniformly-spread. Also observe that $I$ is an independent set in $\mathcal{H}^{\prime\prime}$ , thus by the induction hypothesis there exists $F^{\prime}\subseteq V$ of size $|F^{\prime}|\leq(\ell-1)Np$ and $C=C(F^{\prime})$ such that $|C|\leq(1-\delta)N$ and $I\subseteq C\cup F^{\prime}$ . Note that we can reconstruct $C$ from $F:=F\cup F^{\prime}$ .

Case 2: $\nu(\mathcal{H}^{\prime})<\alpha p$ . By (3), we have $\nu(\mathcal{D})<1/4$ and hence $\nu(\mathcal{R})\geq\nu(\mathcal{H})-\nu(\mathcal{H}^{\prime})-\nu(\mathcal{D})>1/2$ . By (4), for every $v\in I\smallsetminus F$ we have

\nu(\langle v\rangle\cap\mathcal{R})\leq\alpha/N.

(5)

Let now $C\subseteq V\smallsetminus F$ denote the set of all $v\in V\smallsetminus F$ such that $\nu(\langle v\rangle\cap\mathcal{R})\leq\alpha/N$ . By (5) we have $I\smallsetminus F\subseteq C$ . Furthermore,

\nu(\mathcal{R})\leq\sum_{v\in C}\nu(\langle v\rangle\cap\mathcal{R})+\sum_{w\in V\smallsetminus(F\cup C)}\nu(\langle w\rangle\cap\mathcal{R})<\alpha+(N-|C|)\cdot K/N.

Hence, $|C|<N-(\nu(\mathcal{R})-\alpha)N/K<(1-\delta)N$ for $\delta=1/(4K)$ . This concludes the construction of desired $F$ and $C$ . ∎

For the sake of completeness, we derive Theorem 1.1 from Lemma 2.1.

Proof of Theorem 1.1.

Let $\delta>0$ be as given by Lemma 2.1 for $\ell$ and $K/\varepsilon$ (as $K$ ). We prove the theorem for $T=\ell\log(K\varepsilon^{-1})/\log(1+\delta)$ .

We find a fingerprint $F$ and a container $C$ as follows. Set $F=\varnothing$ and $C=V$ , and as long as $\nu(\mathcal{H}[C])\geq\varepsilon$ do the following: Let $F^{\prime}$ and $C^{\prime}$ be as given by Lemma 2.1 applied with $\nu^{\prime}$ being a probability measure over $2^{C}$ given by $\nu^{\prime}(X)\,\propto\,\nu(X)$ if $X\in\mathcal{H}[C]$ , and $\nu^{\prime}(X)=0$ otherwise. Set $F:=F\cup F^{\prime}$ and $C:=C^{\prime}$ , and proceed to the next iteration.

If $\nu(\mathcal{H}[C])\geq\varepsilon$ , then for nonempty $X\subseteq C$ ,

\nu^{\prime}(\langle X\rangle)\leq\frac{\nu(\langle X\rangle)}{\nu(\mathcal{H}[C])}\leq\frac{Kp^{|X|-1}/N}{\varepsilon}\leq\frac{K}{\varepsilon}p^{|X|-1}/|C|,

and hence $\nu^{\prime}$ is $(p,K/\varepsilon)$ -uniformly-spread each time we apply Lemma 2.1. Furthermore, if $\nu(\mathcal{H}[C])\geq\varepsilon$ , then $|C|\geq\varepsilon N/K$ . In each iteration the set $C$ shrinks by a factor of $1-\delta$ , thus we are done after at most $\log(K\varepsilon^{-1})/\log(1+\delta)$ iterations. The set $F$ grows by at most $\ell Np$ in each iteration, which gives an upper bound of $TNp$ on its final size for the above choice of $T=T(K,\varepsilon)$ . Due to the last property in Lemma 2.1, the final set $C$ can be unambiguously constructed from $F$ . ∎

Acknowledgment.

Ideas used in this paper were developed while the first author was visiting Stanford University in November 2023. The first author thanks Jacob Fox for hospitality. We thank Jacob Fox for helpful comments and Wojciech Samotij for pointing out a subtle issue in an earlier version.

References

[1] J. Balogh, R. Morris, and W. Samotij. Independent sets in hypergraphs. J. Am. Math. Soc., 28(3):669–709, 2015.
[2] J. Balogh, R. Morris, and W. Samotij. The method of hypergraph containers. In Proceedings of the international congress of mathematicians 2018, ICM 2018, Rio de Janeiro, Brazil, August 1–9, 2018. Volume IV. Invited lectures, pages 3059–3092. Hackensack, NJ: World Scientific; Rio de Janeiro: Sociedade Brasileira de Matemática (SBM), 2018.
[3] J. Balogh and W. Samotij. An efficient container lemma. Discrete Anal., 2020:56, 2020. Id/No 17.
[4] A. Bernshteyn, M. Delcourt, H. Towsner, and A. Tserunyan. A short nonalgorithmic proof of the containers theorem for hypergraphs. Proc. Am. Math. Soc., 147(4):1739–1749, 2019.
[5] M. Bucić, J. Fox, and H. T. Pham. Equivalence between Erdős-Hajnal and polynomial Rödl and Nikiforov conjectures, 2024. arXiv:2403.08303.
[6] M. Campos and W. Samotij. Towards an optimal hypergraph container lemma, 2024. arXiv:2408.06617.
[7] R. Morris, W. Samotij, and D. Saxton. An asymmetric container lemma and the structure of graphs with no induced 4-cycle. J. Eur. Math. Soc., 26(5):1655–1711, 2024.
[8] R. Nenadov. Probabilistic hypergraph containers. Israel Journal of Mathematics, 261:879–897, 2024.
[9] D. Saxton and A. Thomason. Hypergraph containers. Invent. Math., 201(3):925–992, 2015.
[10] D. Saxton and A. Thomason. Online containers for hypergraphs, with applications to linear equations. J. Comb. Theory, Ser. B, 121:248–283, 2016.
[11] D. Saxton and A. Thomason. Simple containers for simple hypergraphs. Comb. Probab. Comput., 25(3):448–459, 2016.