Hypergraph containers

Abstract

We develop a notion of containment for independent sets in hypergraphs. For every r$$r$$-uniform hypergraph G$$G$$, we find a relatively small collection C$${\mathcal C}$$ of vertex subsets, such that every independent set of G$$G$$ is contained within a member of C$${\mathcal C}$$, and no member of C$${\mathcal C}$$ is large; the collection, which is in various respects optimal, reveals an underlying structure to the independent sets. The containers offer a straightforward and unified approach to many combinatorial questions concerned (usually implicitly) with independence. With regard to colouring, it follows that simple r$$r$$-uniform hypergraphs of average degree d$$d$$ have list chromatic number at least (1/(r-1)2+o(1))logrd$$(1/(r-1)^2+o(1))\log _r d$$. For r=2$$r=2$$ this improves a bound due to Alon and is tight. For r≥3$$r\ge 3$$, previous bounds were weak but the present inequality is close to optimal. In the context of extremal graph theory, it follows that, for each ℓ$$\ell $$-uniform hypergraph H$$H$$ of order k$$k$$, there is a collection C$${\mathcal C}$$ of ℓ$$\ell $$-uniform hypergraphs of order n$$n$$ each with o(nk)$$o(n^k)$$ copies of H$$H$$, such that every H$$H$$-free ℓ$$\ell $$-uniform hypergraph of order n$$n$$ is a subgraph of a hypergraph in C$${\mathcal C}$$, and log|C|≤cnℓ-1/m(H)logn$$\log |{\mathcal C}|\le c n^{\ell -1/m(H)}\log n$$ where m(H)$$m(H)$$ is a standard parameter (there is a similar statement for induced subgraphs). This yields simple proofs, for example, for the number of H$$H$$-free hypergraphs, and for the sparsity theorems of Conlon–Gowers and Schacht. A slight variant yields a counting version of the KŁR conjecture. Likewise, for systems of linear equations the containers supply, for example, bounds on the number of solution-free sets, and the existence of solutions in sparse random subsets. Balogh, Morris and Samotij have independently obtained related results.