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  (formula_1) 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 formula_2 that lack a -term arithmetic progression. These sets are exactly the independent sets in the -uniform hypergraph formula_3, where is the collection of all -term arithmetic progressions in formula_4. In the above (and many other) instances, there are usually two natural classes of problems posed about hypergraph : These problems are connected by a simple observation. Let formula_5  be the size of a largest independent set of and suppose formula_6 has formula_7 independent sets. Then, Example applications. Regular graphs. Upper bound on the number of independent sets. We will show that there is an absolute constant such that every formula_2-vertex formula_19-regular graph formula_20 satisfies formula_21. We can bound the number of independent sets of each size formula_22 by using the trivial bound formula_23 for formula_24. For larger formula_22, take formula_26 With these parameters, -regular graph formula_20 satisfies the conditions of Lemma 1 and thus, Summing over all formula_29 gives which yields the desired result when we  plug in formula_31 Sum-free sets. A set formula_32 of elements of an abelian group is called "sum-free" if there are no formula_33 satisfying formula_34. We will show that there are at most formula_35 sum-free subsets of formula_36. 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 formula_37 elements smaller than formula_38 (since the number of subsets in  the complement of this is at most formula_39). Given some subset formula_40, we define an auxiliary graph formula_41 with vertex set formula_42 and edge set formula_43, and observe that our auxiliary graph is formula_44 regular since each element of is smaller than formula_38. Then if formula_46 are the smallest formula_37 elements of subset formula_48, the set formula_49 is an independent set in the graph formula_50. Then, by our previous bound, we see that the number of sum-free subsets of formula_42 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 formula_2 vertices. Informal statement. Since bipartite graphs are triangle-free, the number of triangle free graphs with formula_2 vertices is at least formula_55, obtained by enumerating all possible subgraphs of the balanced complete bipartite graph formula_56. We can construct an auxiliary -uniform hypergraph with vertex set formula_57 and edge set formula_58. This hypergraph "encodes" triangles in the sense that the family of triangle-free graphs on formula_2 vertices is exactly the collection of independent sets of this hypergraph, formula_60. The above hypergraph has  a nice degree distribution: each edge of formula_61, and thus vertex in formula_62 is contained in exactly formula_63 triangles and each pair of elements in formula_62 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 formula_65 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 formula_66, there exists formula_67 such  that the following holds. Let formula_6 be a 3-uniform hypergraph with average degree formula_69 and suppose that formula_70. Then there exists a collection formula_9 of at most formula_72 containers such that Applying this lemma iteratively will give the following theorem (as proved below): Theorem: For all formula_77, there exists formula_78 such that the following holds. For each positive integer , there exists a collection formula_79 of graphs on vertices with formula_80 such that Proof: Consider the hypergraph formula_6 defined above. As observed informally earlier, the hypergraph satisfies formula_86 for every formula_87. Therefore, we can apply the above Lemma to formula_6  with formula_89 to find some collection formula_90 of formula_65 subsets of formula_92 (i.e. graphs on formula_2 vertices) such that 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 formula_16 with at least formula_82 triangles. We can apply the container lemma to the induced sub-hypergraph formula_99. The average degree of formula_99 is at least formula_101, since every triangle in formula_102 is an edge in formula_99, and this induced subgraph has at most formula_104 vertices. Thus, we can apply Lemma with parameter formula_105, remove  formula_102 from our set of containers, replacing it by this set of containers, the containers covering formula_107. We can keep iterating until we have a final collection of containers formula_90 that each contain fewer than formula_82 triangles. We observe that this collection cannot be too big; all of our induced subgraphs have at most formula_104 vertices and average degree at least formula_101, meaning that each iteration results in at most formula_65 new containers. Further, the container size shrinks by a factor of formula_113 each time, so after a bounded (depending on formula_114) number of iterations, the iterative process will  terminate. See also. Independent set (graph theory) Szemerédi's theorem Szemerédi regularity lemma