Hypergraph containers

By David Saxton, Andrew G. Thomason. 2012

395 citations recorded by the source corpus.

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 $${\mathcal C}$$C of vertex subsets, such that every independent set of $$G$$G is contained within a member of $${\mathcal C}$$C, and no member of $${\mathcal C}$$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))\log _r d$$(1/(r-1)2+o(1))logrd. For $$r=2$$r=2 this improves a bound due to Alon and is tight. For $$r\ge 3$$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 $$\ell $$ℓ-uniform hypergraph $$H$$H of order $$k$$k, there is a collection $${\mathcal C}$$C of $$\ell $$ℓ-uniform hypergraphs of order $$n$$n each with $$o(n^k)$$o(nk) copies of $$H$$H, such that every $$H$$H-free $$\ell $$ℓ-uniform hypergraph of order $$n$$n is a subgraph of a hypergraph in $${\mathcal C}$$C, and $$\log |{\mathcal C}|\le c n^{\ell -1/m(H)}\log n$$log|C|≤cnℓ-1/m(H)logn 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.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/bbe14bb64ca135169aa0a3187c2d7e1cf0d7a3e8

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Discrete Mathematics and Combinatorics

In Geometry and Topology

Citations in the corpus

The asymptotics of r(4,t) (2023, methodology): “…Lee, R¨odl and Samotij [35], and is a special case of the method of containers due to Balogh, Morris and Samotij [5] and Saxton and Thomason [48]: Proposition 4 Let G be a graph on n vertices, and let r, R ∈ N , and α ∈ [0 , 1] satisfy: and, for every subset Then the number of independent…”
THE METHOD OF HYPERGRAPH CONTAINERS (2018, methodology): “(cid:0) (cid:1) The following generalisation of this result, which also improves the constant 1 / 2, was proved by Saxton and Thomason [81], see also [80, 82].”
Independent sets in hypergraphs (2012, result): “iform hypergraphs) and subsequently used it to bound the number of n-vertex graphs without a 4-cycle. We also note that a result similar to Theorem 2.2 was independently proved by Saxton and Thomason [57], who also use it to derive many of the statements that we present in Sections 1.1–1.3. 1.1. The”
Combinatorial theorems in sparse random sets (2010, background): “[54] D. Saxton and A. Thomason, Hypergraph containers, Invent.”
On the KŁR conjecture in random graphs (2013, methodology): “oved in a diﬀerent way by Conlon and Gowers [17] (for strictly balanced graphs, i.e., those for which m2(H) > m2(H′) for every proper subgraph H′ of H) and, independently, Schacht [79] (see 4 also [10, 78]). We remark that this theorem was the original motivation behind Conjecture 1.4 – see Secti”
Many T copies in H-free graphs (2015, background): “See also [6] and [43] for a more recent effective approach for investigating these problems.”
The number of $C_{2l}$-free graphs (2013, methodology): “mma. The corresponding result for k-uniform hypergraphs was proved by Nagle, Ro¨dl and Schacht [44] using hypergraph regularity, and reproved by Balogh, Morris and Samotij [5] and Saxton and Thomason [49] using the hypergraph container method (see below). Much more precise results for graphs were ob”