Repository logo
 

Hypergraph containers


Type

Article

Change log

Authors

Saxton, David 
Thomason, Andrew 

Abstract

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.

Description

Keywords

math.CO, math.CO

Journal Title

INVENTIONES MATHEMATICAE

Conference Name

Journal ISSN

0020-9910
1432-1297

Volume Title

201

Publisher

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