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 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.

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 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 (${\displaystyle k=3}$) and Szemerédi (general k).

The method of containers (in graphs) was initially pioneered by Kleitman and Winston in 1980, who bounded the number of lattices ^[1] and graphs without 4-cycles. ^[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.

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 1 to n, which we denote by ${\displaystyle [n]}$ that lack a k-term arithmetic progression. These sets are exactly the independent sets in the k-uniform hypergraph ${\displaystyle H=(\{1,2,\ldots ,n\},E)}$, where E is the collection of all k-term arithmetic progressions in ${\displaystyle \{1,2,\ldots ,n\}}$.

In the above (and many other) instances, there are usually two natural classes of problems posed about a hypergraph H:

• What is the size of a maximum independent set in H? What does the collection of maximum-sized independent sets in H look like?
• How many independent sets does H have? What does a "typical" independent set in H look like?

These problems are connected by a simple observation. Let ${\displaystyle \alpha (H)}$ be the size of a largest independent set of H and suppose ${\displaystyle H}$ has ${\displaystyle i(H)}$ independent sets. Then,

${\displaystyle 2^{\alpha (H)}\leq i(H)\leq \sum _{r=0}^{\alpha (H)}{|V(H)| \choose r},}$

where the lower bound follows by taking all subsets of a maximum independent set. These bounds are relatively far away from each other unless ${\displaystyle \alpha (H)}$ 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 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. 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 f. Then, it provides an algorithm that extracts from each independent set I in hypergraph H, a relatively small collection of vertices ${\displaystyle S\subset I}$, called a fingerprint, with the property that ${\displaystyle S\subset I\subset S\cup f(S)}$. Then, the containers are the collection of sets ${\displaystyle S\cup f(S)}$ 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 ^[8] about the graph container method, originally employed by Kleitman-Winston and Sapozhenko.

Notation

We use the following notation in the below section.

• ${\displaystyle G=(V,E)}$ is a graph on ${\displaystyle |V|=n}$ vertices, where the vertex set is equipped with (arbitrary) ordering ${\displaystyle \{v_{1},\ldots ,v_{n}\}}$.
• Let ${\displaystyle \ell (G)}$ be the collection of independent sets of G with size ${\displaystyle i(G):=|\ell (G)|}$. Let ${\displaystyle i(G,r)}$ be the number of independent sets of size r.
• The max-degree ordering of a vertex subset ${\displaystyle A\subset V}$ is the ordering of the vertices in A by their degree in the induced subgraph ${\displaystyle G[A]}$.

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 G, independent set ${\displaystyle I\in \ell (G)}$ and positive integer ${\displaystyle q\leq |I|}$.

1. Initialize: let ${\displaystyle A=V(G),S=\emptyset }$.
2. Iterate for ${\displaystyle s=1,2,\ldots ,q}$:
   • Construct the max-degree ordering of ${\displaystyle A,\,(v_{1},\ldots v_{|A|})}$
   • Find the minimal index ${\displaystyle j_{s}}$ such that ${\displaystyle v_{j_{s}}\in I}$ (i.e. the vertex in A of largest degree in induced subgraph G[A])
   • Let ${\displaystyle S\leftarrow S\cup \{v_{j_{s}}\},\,A\leftarrow A\backslash (\{v_{1},\ldots ,v_{j_{s}}\}\cup N(v_{j_{s}}))}$, where ${\displaystyle N(v)}$ is the neighborhood of vertex ${\displaystyle v}$.
3. Output the vector ${\displaystyle (j_{1},\ldots ,j_{q})}$ and the vertex set ${\displaystyle A\cap I}$.

Analysis

By construction, the output of the above algorithm has property that ${\displaystyle \{v_{j_{1}},\ldots ,v_{j_{q}}\}\subset I\subset \{v_{j_{1}},\ldots ,v_{j_{q}}\}\cup (A\cap I)}$, noting that ${\displaystyle A\cap I}$ is a vertex subset that is completely determined by ${\displaystyle \{j_{1},\ldots ,j_{q}\}}$ and not otherwise a function of ${\displaystyle I}$. To emphasize this we will write ${\displaystyle A=A(j_{1},\ldots ,j_{q})}$. We also observe that we can reconstruct the set ${\displaystyle S=\{v_{j_{1}},\ldots ,v_{j_{q}}\}=S(j_{1},\ldots j_{q})}$ in the above algorithm just from the vector ${\displaystyle (j_{1},\ldots ,j_{q})}$.

This suggests that ${\displaystyle S}$ might be a good choice of a fingerprint and ${\displaystyle S(j_{1},\ldots j_{q})\cup A(j_{1},\ldots ,j_{q})}$ a good choice for a container. More precisely, we can bound the number of independent sets of ${\displaystyle G}$ of some size ${\displaystyle r\geq q}$ as a sum over output sequences ${\displaystyle (j_{1},\ldots j_{q})}$

${\displaystyle i(G,r)=\sum _{(j_{s})_{s=1}^{q}}i(G[A(j_{1},\ldots j_{q})],r-q)\leq \sum _{(j_{s})}{A(j_{1},\ldots j_{q}) \choose r-q}}$,

where we can sum across ${\displaystyle r}$ to get a bound on the total number of independent sets of the graph:

${\displaystyle i(G)=\sum _{r=0}^{q-1}{n \choose r}+\sum _{(j_{s})_{s=1}^{q}}i(G[A(j_{1},\ldots j_{q})])\leq \sum _{r=0}^{q-1}{n \choose r}+\sum _{(j_{s})}2^{|A(j_{1},\ldots j_{q})|}}$.

When trying to minimize this upper bound, we want to pick ${\displaystyle q}$ that balances/minimizes these two terms. This result illustrates the value of ordering vertices by maximum degree (to minimize ${\displaystyle |A(j_{1},\ldots j_{q})|}$).

Lemmas

The above inequalities and observations can be stated in a more general setting, divorced from an explicit sum over vectors ${\displaystyle (j_{s})}$.

Lemma 1: Given a graph ${\displaystyle G}$ with ${\displaystyle n}$ and assume that integer ${\displaystyle q}$ and real numbers ${\displaystyle R,\beta \in [0,1]}$ satisfy ${\displaystyle R\geq e^{-\beta q}n}$. Suppose that every induced subgraph on at least ${\displaystyle R}$ vertices has edge density at least ${\displaystyle \beta }$. Then for every integer ${\displaystyle r\geq q}$,

${\displaystyle i(G,r)\leq {n \choose q}{R \choose r-q}.}$

Lemma 2: Let ${\displaystyle G}$ be a graph on ${\displaystyle n}$ vertices and assume that an integer ${\displaystyle q}$ and reals ${\displaystyle R,D}$ are chosen such that ${\displaystyle n\leq R+qD}$. If all subsets ${\displaystyle U}$ of at least ${\displaystyle R}$ vertices have at least ${\displaystyle D|U|/2}$ edges, then there is a collection ${\displaystyle {\mathcal {F}}}$ of subsets of ${\displaystyle q}$ vertices ("fingerprints") and a deterministic function ${\displaystyle f\colon {\mathcal {C}}\rightarrow {\mathcal {P}}(V(G))}$, so that for every independent set ${\displaystyle I\subset V(G)}$, there is ${\displaystyle S\in {\mathcal {F}}}$ such that ${\displaystyle S\subset I\subset f(S)\cup S}$.

Hypergraph container lemma

Informally, the hypergraph container lemma tells us that we can assign a small fingerprint${\displaystyle S\subset I}$ to each independent set, so that all independent sets with the same fingerprint belong to the same larger set, ${\displaystyle C=f(S)}$, 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 ${\displaystyle k}$ uniform hypergraph ${\displaystyle {\mathcal {H}}}$.

• Define ${\displaystyle \Delta _{l}({\mathcal {H}}):=\max\{d_{H}(A)\mid A\subset V({\mathcal {H}}),|A|=l\}}$ for positive integers ${\displaystyle 1\leq l\leq k}$, where ${\displaystyle d_{\mathcal {H}}(A)=|\{e\in E({\mathcal {H}})\mid A\subset e\}|}$.
• Let ${\displaystyle {\mathcal {I}}({\mathcal {H}})}$ be the collection of independent sets of ${\displaystyle {\mathcal {H}}}$. ${\displaystyle I}$ will denote some such independent set.

Statement

We state the version of this lemma found in a work of Balogh, Morris, Samotij, and Saxton. ^[9]

Let ${\displaystyle {\mathcal {H}}}$ be a ${\displaystyle k}$-uniform hypergraph and suppose that for every ${\displaystyle l\in \{1,2,\ldots ,k\}}$ and some ${\displaystyle b,r\in \mathbb {N} }$, we have that ${\displaystyle \Delta _{l}(H)\leq \left({\frac {b}{|V(H)|}}\right)^{l-1}{\frac {|E(H)|}{r}}}$. Then, there is a collection ${\displaystyle {\mathcal {C}}\subset {\mathcal {P}}(V(H))}$ and a function ${\displaystyle f\colon {\mathcal {P}}(V(H))\rightarrow {\mathcal {C}}}$ such that

• for every ${\displaystyle I\in {\mathcal {I}}(H)}$ there exists ${\displaystyle S\subset I}$ with ${\displaystyle |S|\leq (k-1)b}$ and ${\displaystyle I\subset f(S)}$.
• ${\displaystyle |C|\leq |V(H)|-\delta r}$ for every ${\displaystyle C\in {\mathcal {C}}}$ and ${\displaystyle \delta =2^{-k(k+1)}}$.

Example applications

Regular graphs

Upper bound on the number of independent sets

We will show that there is an absolute constant C such that every ${\displaystyle n}$-vertex ${\displaystyle d}$-regular graph ${\displaystyle G}$ satisfies ${\displaystyle i(G)\leq 2^{\left(1+C{\sqrt {\frac {\log d}{d}}}\right){\frac {n}{2}}}}$.

We can bound the number of independent sets of each size ${\displaystyle r}$ by using the trivial bound ${\displaystyle i(G,r)\leq {n \choose r}\leq {n \choose n/10}\leq 2^{0.48n}}$ for ${\displaystyle r\leq n/10}$. For larger ${\displaystyle r}$, take ${\displaystyle \beta >10/n,q=\lfloor 1/\beta \rfloor ,R={\frac {n}{2}}+{\frac {\beta n^{2}}{2d}}.}$ With these parameters, d-regular graph ${\displaystyle G}$ satisfies the conditions of Lemma 1 and thus,

${\displaystyle i(G,r)\leq {n \choose q}{R \choose r-q}\leq {n \choose q}{{\frac {n}{2}}+{\frac {\beta n^{2}}{2d}} \choose r-q}\leq \left({\frac {en}{q}}\right)^{q}{{\frac {n}{2}}+{\frac {\beta n^{2}}{2d}} \choose r-q}\leq (e\beta n)^{\lfloor 1/\beta \rfloor }{{\frac {n}{2}}+{\frac {\beta n^{2}}{2d}} \choose r-q}.}$

Summing over all ${\displaystyle 0\leq r\leq n}$ gives

${\displaystyle i(G)\leq 2^{0.49n}+2^{{\frac {n}{2}}+{\frac {\beta n^{2}}{2d}}+\lfloor 1/\beta \rfloor \log _{2}(e\beta n)}}$,

which yields the desired result when we plug in ${\displaystyle \beta ={\sqrt {d\log d}}/n.}$

Sum-free sets

A set ${\displaystyle A}$ of elements of an abelian group is called sum-free if there are no ${\displaystyle x,y,z\in A}$ satisfying ${\displaystyle x+y=z}$. We will show that there are at most ${\displaystyle 2^{(1/2+o(1))n}}$ sum-free subsets of ${\displaystyle [n]:=\{1,2,\ldots ,n\}}$.

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 ${\displaystyle n^{2/3}}$ elements smaller than ${\displaystyle n/2}$ (since the number of subsets in the complement of this is at most ${\displaystyle (n/2)^{n^{2/3}}2^{n/2+1}}$).

Given some subset ${\displaystyle S\subset \{1,2,\ldots ,\lceil n/2\rceil -1\}}$, we define an auxiliary graph ${\displaystyle G_{S}}$ with vertex set ${\displaystyle [n]}$ and edge set ${\displaystyle \{\{x,y\}\mid x+s\equiv y{\pmod {n}}{\text{ for some }}s\in S\cup (-S)\}}$, and observe that our auxiliary graph is ${\displaystyle 2|S|}$ regular since each element of S is smaller than ${\displaystyle n/2}$. Then if ${\displaystyle S_{A}}$ are the smallest ${\displaystyle n^{2/3}}$ elements of subset ${\displaystyle A\subset [n]}$, the set ${\displaystyle A\backslash S_{A}}$ is an independent set in the graph ${\displaystyle G_{S_{A}}}$. Then, by our previous bound, we see that the number of sum-free subsets of ${\displaystyle [n]}$ is at most

${\displaystyle (n/2)^{n^{2/3}}2^{n/2+}+{n/2 \choose n^{2/3}}2^{(1+O(n^{-1/3}{\sqrt {\log n}})){\frac {n}{2}}}\leq 2^{(1/2+O(n^{-1/3}\log n))n}.}$

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 ${\displaystyle n}$ vertices. ^[10]

Informal statement

Since bipartite graphs are triangle-free, the number of triangle free graphs with ${\displaystyle n}$ vertices is at least ${\displaystyle 2^{\lfloor n^{2}/4\rfloor }}$, obtained by enumerating all possible subgraphs of the balanced complete bipartite graph ${\displaystyle K_{\lfloor n/2\rfloor ,\lceil n/2\rceil }}$.

We can construct an auxiliary 3-uniform hypergraph H with vertex set ${\displaystyle V(H)=E(K_{n})}$ and edge set ${\displaystyle E(H)=\{\{e_{1},e_{2},e_{3}\}\subset E(K_{n})=V(H)\mid e_{1},e_{2},e_{3}{\text{ form a triangle}}\}}$. This hypergraph "encodes" triangles in the sense that the family of triangle-free graphs on ${\displaystyle n}$ vertices is exactly the collection of independent sets of this hypergraph, ${\displaystyle {\mathcal {I}}(H)}$.

The above hypergraph has a nice degree distribution: each edge of ${\displaystyle K_{n}}$, and thus vertex in ${\displaystyle V(H)}$ is contained in exactly ${\displaystyle n-2}$ triangles and each pair of elements in ${\displaystyle V(H)}$ 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 ${\displaystyle n^{O(n^{3/2})}}$ 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 ${\displaystyle c>0}$, there exists ${\displaystyle \delta >0}$ such that the following holds. Let ${\displaystyle H}$ be a 3-uniform hypergraph with average degree ${\displaystyle d\geq 1/\delta }$ and suppose that ${\displaystyle \Delta _{1}(H)\leq cd,\Delta _{2}(H)\leq c{\sqrt {d}}}$. Then there exists a collection ${\displaystyle {\mathcal {C}}\subset {\mathcal {P}}(V(H))}$ of at most ${\displaystyle |{\mathcal {C}}|\leq {|V(H)| \choose |V(H)|/{\sqrt {d}}}}$ containers such that

• for every ${\displaystyle I\in {\mathcal {I}}(H)}$, there exists ${\displaystyle I\subset C\in {\mathcal {C}}}$
• ${\displaystyle |C|\leq (1-\delta )|V(H)|}$ for all ${\displaystyle C\in {\mathcal {C}}}$

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

Theorem: For all ${\displaystyle \epsilon >0}$, there exists ${\displaystyle C>0}$ such that the following holds. For each positive integer n, there exists a collection ${\displaystyle {\mathcal {G}}}$ of graphs on n vertices with ${\displaystyle |{\mathcal {G}}|\leq n^{Cn^{3/2}}}$ such that

• each ${\displaystyle G\in {\mathcal {G}}}$ has fewer than ${\displaystyle \epsilon n^{3}}$ triangles,
• each triangle-free graph on ${\displaystyle n}$ vertices is contained in some ${\displaystyle G\in {\mathcal {G}}}$.

Proof: Consider the hypergraph ${\displaystyle H}$ defined above. As observed informally earlier, the hypergraph satisfies ${\displaystyle |V(H)|={n \choose 2},\Delta _{2}(H)=1,d(v)=n-2}$ for every ${\displaystyle v\in V(H)}$. Therefore, we can apply the above Lemma to ${\displaystyle H}$ with ${\displaystyle c=1}$ to find some collection ${\displaystyle {\mathcal {C}}}$ of ${\displaystyle n^{O(n^{3/2})}}$ subsets of ${\displaystyle E(K_{n})}$ (i.e. graphs on ${\displaystyle n}$ vertices) such that

• every triangle free graph is a subgraph of some ${\displaystyle C\in {\mathcal {C}}}$,
• every ${\displaystyle C\in {\mathcal {C}}}$ has at most ${\displaystyle (1-\delta ){n \choose 2}}$ 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 ${\displaystyle C\in {\mathcal {C}}}$ with at least ${\displaystyle \epsilon n^{3}}$ triangles. We can apply the container lemma to the induced sub-hypergraph ${\displaystyle H[C]}$. The average degree of ${\displaystyle H[C]}$ is at least ${\displaystyle 6\epsilon n}$, since every triangle in ${\displaystyle C}$ is an edge in ${\displaystyle H[C]}$, and this induced subgraph has at most ${\displaystyle {n \choose 2}}$ vertices. Thus, we can apply Lemma with parameter ${\displaystyle c=1/\epsilon }$, remove ${\displaystyle C}$ from our set of containers, replacing it by this set of containers, the containers covering ${\displaystyle {\mathcal {I}}(H[C])}$.

We can keep iterating until we have a final collection of containers ${\displaystyle {\mathcal {C}}}$ that each contain fewer than ${\displaystyle \epsilon n^{3}}$ triangles. We observe that this collection cannot be too big; all of our induced subgraphs have at most ${\displaystyle {n \choose 2}}$ vertices and average degree at least ${\displaystyle 6\epsilon n}$, meaning that each iteration results in at most ${\displaystyle n^{O(n^{3/2})}}$ new containers. Further, the container size shrinks by a factor of ${\displaystyle 1-\delta }$ each time, so after a bounded (depending on ${\displaystyle \epsilon }$) number of iterations, the iterative process will terminate.

See also

Independent set (graph theory)
Szemerédi's theorem
Szemerédi regularity lemma

References

1. Kleitman, Daniel; Winston, Kenneth (1980). "The asymptotic number of lattices". Annals of Discrete Mathematics. 6: 243–249. doi:10.1016/S0167-5060(08)70708-8. ISBN   9780444860484.
2. Kleitman, Daniel; Winston, Kenneth (1982). "On the number of graphs without 4-cycles". Discrete Mathematics. 31 (2): 167–172. doi: 10.1016/0012-365X(82)90204-7 .
3. Sapozhenko, Alexander (2003). "The Cameron-Erdos conjecture". Doklady Akademii Nauk. 393: 749–752.
4. Sapozhenko, Alexander (2002). "Asymptotics for the number of sum-free sets in Abelian groups". Doklady Akademii Nauk. 383: 454–458.
5. Sapozhenko, Alexander (2005), "Systems of Containers and Enumeration Problems", Stochastic Algorithms: Foundations and Applications, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 1–13, ISBN   978-3-540-29498-6 , retrieved 2022-02-13
6. Saxton, David; Thomason, Andrew (2015). "Hypergraph containers". Inventiones Mathematicae. 201 (3): 925–992. arXiv: 1204.6595 . Bibcode:2015InMat.201..925S. doi:10.1007/s00222-014-0562-8. S2CID   119253715.
7. Balogh, József; Morris, Robert; Samotij, Wojciech (2015). "Independent sets in hypergraphs". Journal of the American Mathematical Society. 28 (3): 669–709. arXiv: 1204.6530 . doi: 10.1090/S0894-0347-2014-00816-X . S2CID   15244650.
8. Samotij, Wojciech (2015). "Counting independent sets in graphs". European Journal of Combinatorics. 48: 5–18. arXiv: 1412.0940 . doi:10.1016/j.ejc.2015.02.005. S2CID   15850625.
9. Balogh, József; Morris, Robert; Samotij, Wojciech (2015). "Independent sets in hypergraphs". Journal of the American Mathematical Society. 28 (3): 669–709. arXiv: 1204.6530 . doi: 10.1090/S0894-0347-2014-00816-X . S2CID   15244650.
10. Balogh, József; Morris, Robert; Samotij, Wojciech (2018). "The method of hypergraph containers". Proceedings of the International Congress of Mathematicians: Rio de Janeiro. arXiv: 1801.04584 .