The method of (hypergraph) containers is a powerful tool that can help characterize the typical structure and/or answer extremal questions about families of discrete objects with a prescribed set of local constraints.
These problems can be expressed as questions of the following form: given a hypergraph H on finite vertex set V with edge set E (i.e. a collection of subsets of V with some size constraints), what can we say about the independent sets of H (i.e. those subsets of V that contain no element of E)?
The hypergraph container lemma provides a method for tackling such questions.
One of the foundational problems of extremal graph theory, dating to work of Mantel in 1907 and Turán from the 1940s, asks to characterize those graphs that do not contain a copy of some fixed forbidden H as a subgraph.
In a different domain, one of the motivating questions in additive combinatorics is understanding how large a set of integers can be without containing a k-term arithmetic progression, with upper bounds on this size given by Roth (
[2] Container-style lemmas were independently developed by multiple mathematicians in different contexts, notably including Sapozhenko, who initially used this approach in 2002-2003 to enumerate independent sets in regular graphs,[3] sum-free sets in abelian groups,[4] and study a variety of other enumeration problems[5] A generalization of these ideas to a hypergraph container lemma was devised independently by Saxton and Thomason[6] and Balogh, Morris, and Samotij[7] in 2015, inspired by a variety of previous related work.
Many problems in combinatorics can be recast as questions about independent sets in graphs and hypergraphs.
For example, suppose we wish to understand subsets of integers 1 to n, which we denote by
Then, where the lower bound follows by taking all subsets of a maximum independent set.
However, in many hypergraphs that naturally arise in combinatorial problems, we have reason to believe that the lower bound is closer to the true value; thus the primary goal is to improve the upper bounds on i(H).
The hypergraph container lemma provides a powerful approach to understanding the structure and size of the family of independent sets in a hypergraph.
It constructs a deterministic function f. Then, it provides an algorithm that extracts from each independent set I in hypergraph H, a relatively small collection of vertices
that arise in the above process, and the small size of the fingerprints provides good control on the number of such container sets.
We first describe a method for showing strong upper bounds on the number of independent sets in a graph; this exposition is adapted from a survey of Samotij[8] about the graph container method, originally employed by Kleitman-Winston and Sapozhenko.
The following algorithm gives a small "fingerprint" for every independent set in a graph and a deterministic function of the fingerprint to construct a not-too-large subset that contains the entire independent set Fix graph G, independent set
This result illustrates the value of ordering vertices by maximum degree (to minimize
The above inequalities and observations can be stated in a more general setting, divorced from an explicit sum over vectors
Informally, the hypergraph container lemma tells us that we can assign a small fingerprint
, the associated container, that has size bounded away from the number of vertices of the hypergraph.
Further, these fingerprints are small (and thus there are few containers), and we can upper bound their size in an essentially optimal way using some simple properties of the hypergraph.
We state the version of this lemma found in a work of Balogh, Morris, Samotij, and Saxton.
We can bound the number of independent sets of each size
This will follow from our above bounds on the number of independent sets in a regular graph.
We first observe that up to lower order terms, we can restrict our focus to sum-free sets with at least
is at most We give an illustration of using the hypergraph container lemma to answer an enumerative question by giving an asymptotically tight upper bound on the number of triangle-free graphs with
, obtained by enumerating all possible subgraphs of the balanced complete bipartite graph
This hypergraph "encodes" triangles in the sense that the family of triangle-free graphs on
Therefore, applying the hypergraph container lemma (iteratively), we are able to show that there is a family of
vertices) such that This is not quite as strong as the result we want to show, so we will iteratively apply the container lemma.
We can apply the container lemma to the induced sub-hypergraph