Repository logo

Hypergraph containers



Change log


Saxton, David 
Thomason, Andrew 


We develop a notion of containment for independent sets in hypergraphs. For every r-uniform hypergraph G, we find a relatively small collection C of vertex subsets, such that every independent set of G is contained within a member of C, and no member of 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-uniform hypergraphs of average degree d have list chromatic number at least (1/(r−1)2+o(1))logrd. For r=2 this improves a bound due to Alon and is tight. For r≥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 -uniform hypergraph H of order k, there is a collection C of -uniform hypergraphs of order n each with o(nk) copies of H, such that every H-free -uniform hypergraph of order n is a subgraph of a hypergraph in C, and log⁡|C|≤cn−1/m(H)logn where 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-free hypergraphs, and for the sparsity theorems of Conlon-Gowers and Schacht. A slight variant yields a counting version of the K{\L}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.



math.CO, math.CO

Journal Title


Conference Name

Journal ISSN


Volume Title



Springer Science and Business Media LLC
The first author was supported by a grant from the EPSRC.