Hypergraph containers

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)){\log }_{r}d$. For $r=2$ this improves a bound due to Alon and is tight. For $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$ of order $k$, there is a collection $C$ of $\ell$-uniform hypergraphs of order $n$ each with $o(n^k)$ copies of $H$, such that every $H$-free $\ell$-uniform hypergraph of order $n$ is a subgraph of a hypergraph in $C$, and $\log |C|\le c{n}^{\ell -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.

References in corpus (5)

• Hypergraph containers
• A Szemeredi-type regularity lemma in abelian groups, with applications
• The Number of Independent Sets in a Regular Graph
• On the KŁR conjecture in random graphs
• A Proof of Green's Conjecture Regarding the Removal Properties of Sets of Linear Equations

Cited by in corpus (48)

• Hypergraph containers
• Further applications of the Container Method
• On the KŁR conjecture in random graphs
• A relative Szemerédi theorem
• Extremal results in random graphs
• A random version of Sperner's theorem
• The number of the maximal triangle-free graphs
• Independent sets in the hypercube revisited
• Ramsey properties of randomly perturbed graphs: cliques and cycles
• Separation choosability and dense bipartite induced subgraphs
• The number of independent sets in an irregular graph
• On the number of graphs without large cliques
• On the structure of large sum-free sets of integers
• Online containers for hypergraphs, with applications to linear equations
• The number of triple systems without even cycles
• The number of hypergraphs without linear cycles
• Turán's Theorem for random graphs
• The number of $C_{2l}$-free graphs
• Sharp thresholds for Ramsey properties of strictly balanced nearly bipartite graphs
• An extremal graph problem with a transcendental solution
• Integer colorings with no rainbow 3-term arithmetic progression
• An exponential-type upper bound for Folkman numbers
• Intersecting families of discrete structures are typically trivial
• Colouring set families without monochromatic k-chains
• Weakly saturated random graphs
• The typical structure of graphs with no large cliques
• List colouring with a bounded palette
• Balanced supersaturation for some degenerate hypergraphs
• A note on induced Ramsey numbers
• On the number of monotone sequences
• On the number of high-dimensional partitions
• Blowup Ramsey numbers
• Asymmetric list sizes in bipartite graphs
• On the number of H-free hypergraphs
• On a topological version of Pach's overlap theorem
• Sharp thresholds for Ramsey properties
• Counting independent sets in structured graphs
• The number of maximal sum-free subsets of integers
• A refined graph container lemma and applications to the hard-core model on bipartite expanders
• Counting independent sets in percolated graphs via the Ising model
• On linear configurations in subsets of compact abelian groups, and invariant measurable hypergraphs
• Normal limiting distributions for systems of linear equations in random sets
• Ramsey properties of random graphs and Folkman numbers
• On higher dimensional point sets in general position
• The counting version of a problem of Erdős
• List colourings of multipartite hypergraphs
• On the threshold for the Maker-Breaker $H$-game
• Mantel's Theorem for Random Hypergraphs