2012/04/30 by David Saxton, Andrew Thomason · 1 citation
Mathematics · #math.CO
paper · pdf · doi:10.1007/s00222-014-0562-8
arxiv created 2014/11/28 · arxiv updated 2014/12/01
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)) logr d. 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| ≤ c nℓ-1/m(H) log n 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Ł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.