Container method
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. Such questions arise naturally in extremal graph theory, additive combinatorics, discrete geometry, coding theory, and Ramsey theory; they include some of the most classical problems in the associated fields. These problems can be expressed as questions of the following form: given a hypergraph  on finite vertex set  with edge set  (i.e. a collection of subsets of  with some size constraints), what can we say about the independent sets of  (i.e. those subsets of  that contain no element of )? The hypergraph container lemma provides a method for tackling such questions. History

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  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 -term arithmetic progression, with upper bounds on this size given by Roth () and Szemerédi (general ). The method of containers (in graphs) was initially pioneered by Kleitman and Winston in 1980, who bounded the number of lattices and graphs without 4-cycles. 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, sum-free sets in abelian groups, and study a variety of other enumeration problems

A generalization of these ideas to a hypergraph container lemma was devised independently by Saxton and Thomason and Balogh, Morris, and Samotij in 2015, inspired by a variety of previous related work. Main idea and informal statement
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  to , which we denote by  that lack a -term arithmetic progression. These sets are exactly the independent sets in the -uniform hypergraph , where  is the collection of all -term arithmetic progressions in . In the above (and many other) instances, there are usually two natural classes of problems posed about a hypergraph :
 What is the size of a maximum independent set in ? What does the collection of maximum-sized independent sets in  look like? How may independent sets does  have? What does a "typical" independent set in  look like? These problems are connected by a simple observation. Let  be the size of a largest independent set of  and suppose  has  independent sets. Then,

where the lower bound follows by taking all subsets of a maximum independent set. These bounds are relatively far away from each other unless  is very large, close to the number of vertices of the hypergraph. 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 . The hypergraph container lemma provides a powerful approach to understanding the structure and size of the family of independent sets in a hypergraph. At its core, the hypergraph container method enables us to extract from a hypergraph, a collection of containers, subsets of vertices that satisfy the following properties:
 There are not too many containers. Each container is not much larger than the largest independent set. Each container has few edges. Every independent set in the hypergraph is fully included in some container. The name container alludes to this last condition. Such containers often provide an effective approach to characterizing the family of independent sets (subsets of the containers) and to enumerating the independent sets of a hypergraph (by simply considering all possible subsets of a container). The hypergraph container lemma achieves the above container decomposition in two pieces. It constructs a deterministic function . Then, it provides an algorithm that extracts from each independent set  in hypergraph , a relatively small collection of vertices , called a fingerprint, with the property that . Then, the containers are the collection of sets  that arise in the above process, and the small size of the fingerprints provides good control on the number of such container sets. Graph container algorithm
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 about the graph container method, originally employed by Kleitman-Winston and Sapozhenko. Notation
We use the following notation in the below section. is a graph on  vertices, where the vertex set is equipped with (arbitrary) ordering . Let  be the collection of independent sets of  with size  . Let  be the number of independent sets of size . The max-degree ordering of a vertex subset  is the ordering of the vertices in  by their degree in the induced subgraph . Kleitman-Winston algorithm
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 , independent set  and positive integer . Initialize: let . Iterate for :
 Construct the max-degree ordering of 
 Find the minimal index  such that  (i.e. the vertex in  of largest degree in induced subgraph )
 Let , where  is the neighborhood of vertex . Output the vector  and the vertex set . Analysis
By construction, the output of the above algorithm has property that , noting that  is a vertex subset that is completely determined by  and not otherwise a function of . To emphasize this we will write . We also observe that we can reconstruct the set  in the above algorithm just from the vector . This suggests that  might be a good choice of a fingerprint and  a good choice for a container. More precisely, we can bound the number of independent sets of  of some size  as a sum over output sequences 
,
where we can sum across  to get a bound on the total number of independent sets of the graph:
. When trying to minimize this upper bound, we want to pick  that balances/minimizes these two terms. This result illustrates the value of ordering vertices by maximum degree (to minimize ). Lemmas
The above inequalities and observations can be stated in a more general setting, divorced from an explicit sum over vectors . Lemma 1: Given a graph  with  and assume that integer  and real numbers  satisfy . Suppose that every induced subgraph on at least  vertices has edge density at least . Then for every integer ,

Lemma 2: Let  be a graph on  vertices and assume that an integer  and reals  are chosen such that . If all subsets  of at least  vertices have at least  edges, then there is a collection  of subsets of  vertices ("fingerprints") and a deterministic function , so that for every independent set , there is  such that . Hypergraph container lemma
Informally, the hypergraph container lemma tells us that we can assign a small fingerprint  to each independent set, so that all independent sets with the same fingerprint belong to the same larger set, , 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 recall the following notation associated to  uniform hypergraph . Define  for positive integers , where . Let  be the collection of independent sets of . will denote some such independent set. Statement
We state the version of this lemma found in a work of Balogh, Morris, Samotij, and Saxton

Let  be a -uniform hypergraph and suppose that for every  and some , we have that . Then, there is a collection  and a function  such that 
 for every  there exists  with  and . for every  and . Example applications

Regular graphs

Upper bound on the number of independent sets
We will show that there is an absolute constant  such that every -vertex -regular graph  satisfies . We can bound the number of independent sets of each size  by using the trivial bound  for . For larger , take  With these parameters, -regular graph  satisfies the conditions of Lemma 1 and thus,

Summing over all  gives 
,
which yields the desired result when we plug in

Sum-free sets
A set  of elements of an abelian group is called sum-free if there are no  satisfying . We will show that there are at most  sum-free subsets of . This will follow from our above bounds on the number of independent sets in a regular graph. To see this, we will need to construct an auxiliary graph. We first observe that up to lower order terms, we can restrict our focus to sum-free sets with at least  elements smaller than  (since the number of subsets in the complement of this is at most ). Given some subset , we define an auxiliary graph  with vertex set  and edge set , and observe that our auxiliary graph is  regular since each element of  is smaller than . Then if  are the smallest  elements of subset , the set  is an independent set in the graph . Then, by our previous bound, we see that the number of sum-free subsets of  is at most

Triangle-free graphs

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  vertices. Informal statement
Since bipartite graphs are triangle-free, the number of triangle free graphs with  vertices is at least , obtained by enumerating all possible subgraphs of the balanced complete bipartite graph . We can construct an auxiliary -uniform hypergraph  with vertex set  and edge set . This hypergraph "encodes" triangles in the sense that the family of triangle-free graphs on  vertices is exactly the collection of independent sets of this hypergraph, . The above hypergraph has a nice degree distribution: each edge of , and thus vertex in  is contained in exactly  triangles and each pair of elements in  is contained in at most 1 triangle. Therefore, applying the hypergraph container lemma (iteratively), we are able to show that there is a family of  containers that each contain few triangles that contain every triangle-free graph/independent set of the hypergraph. Upper bound on the number of triangle-free graphs
We first specialize the generic hypergraph container lemma to 3-uniform hypergraphs as follows:

Lemma: For every , there exists  such that the following holds. Let  be a 3-uniform hypergraph with average degree  and suppose that . Then there exists a collection  of at most  containers such that 
 for every , there exists 
  for all 

Applying this lemma iteratively will give the following theorem (as proved below):

Theorem: For all , there exists  such that the following holds. For each positive integer , there exists a collection  of graphs on  vertices with  such that 
 each  has fewer than  triangles,
 each triangle-free graph on  vertices is contained in some . Proof: Consider the hypergraph  defined above. As observed informally earlier, the hypergraph satisfies  for every . Therefore, we can apply the above Lemma to  with  to find some collection  of  subsets of  (i.e. graphs on  vertices) such that
 every triangle free graph is a subgraph of some ,
 every  has at most  edges. This is not quite as strong as the result we want to show, so we will iteratively apply the container lemma. Suppose we have some container  with at least  triangles. We can apply the container lemma to the induced sub-hypergraph . The average degree of  is at least , since every triangle in  is an edge in , and this induced subgraph has at most  vertices. Thus, we can apply Lemma with parameter , remove  from our set of containers, replacing it by this set of containers, the containers covering . We can keep iterating until we have a final collection of containers  that each contain fewer than  triangles. We observe that this collection cannot be too big; all of our induced subgraphs have at most  vertices and average degree at least , meaning that each iteration results in at most  new containers. Further, the container size shrinks by a factor of  each time, so after a bounded (depending on ) number of iterations, the iterative process will terminate. See also
Independent set (graph theory) 
Szemerédi's theorem 
Szemerédi regularity lemma

References 

Extremal graph theory
Hypergraphs
Additive combinatorics