Container method

Last updated

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.

Contents

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 () 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 that lack a k-term arithmetic progression. These sets are exactly the independent sets in the k-uniform hypergraph , where E is the collection of all k-term arithmetic progressions in .

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

These problems are connected by a simple observation. Let be the size of a largest independent set of H 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 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:

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 , 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 [8] about the graph container method, originally employed by Kleitman-Winston and Sapozhenko.

Notation

We use the following notation in the below section.

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 and positive integer .

  1. Initialize: let .
  2. Iterate for :
    • Construct the max-degree ordering of
    • Find the minimal index such that (i.e. the vertex in A of largest degree in induced subgraph G[A])
    • Let , where is the neighborhood of vertex .
  3. 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 .

Statement

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

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

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 -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, d-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 S 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. [10]

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 3-uniform hypergraph H 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 n, there exists a collection of graphs on n 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

Related Research Articles

In combinatorics, Ramsey's theorem, in one of its graph-theoretic forms, states that one will find monochromatic cliques in any edge labelling (with colours) of a sufficiently large complete graph. To demonstrate the theorem for two colours (say, blue and red), let r and s be any two positive integers. Ramsey's theorem states that there exists a least positive integer R(r, s) for which every blue-red edge colouring of the complete graph on R(r, s) vertices contains a blue clique on r vertices or a red clique on s vertices. (Here R(r, s) signifies an integer that depends on both r and s.)

In mathematics, Hall's marriage theorem, proved by Philip Hall (1935), is a theorem with two equivalent formulations. In each case, the theorem gives a necessary and sufficient condition for an object to exist:

<span class="mw-page-title-main">Hypergraph</span> Generalization of graph theory

In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices.

Vapnik–Chervonenkis theory was developed during 1960–1990 by Vladimir Vapnik and Alexey Chervonenkis. The theory is a form of computational learning theory, which attempts to explain the learning process from a statistical point of view.

<span class="mw-page-title-main">Random graph</span> Graph generated by a random process

In mathematics, random graph is the general term to refer to probability distributions over graphs. Random graphs may be described simply by a probability distribution, or by a random process which generates them. The theory of random graphs lies at the intersection between graph theory and probability theory. From a mathematical perspective, random graphs are used to answer questions about the properties of typical graphs. Its practical applications are found in all areas in which complex networks need to be modeled – many random graph models are thus known, mirroring the diverse types of complex networks encountered in different areas. In a mathematical context, random graph refers almost exclusively to the Erdős–Rényi random graph model. In other contexts, any graph model may be referred to as a random graph.

<span class="mw-page-title-main">Szemerédi regularity lemma</span>

Szemerédi's regularity lemma is one of the most powerful tools in extremal graph theory, particularly in the study of large dense graphs. It states that the vertices of every large enough graph can be partitioned into a bounded number of parts so that the edges between different parts behave almost randomly.

In probability theory, if a large number of events are all independent of one another and each has probability less than 1, then there is a positive probability that none of the events will occur. The Lovász local lemma allows one to relax the independence condition slightly: As long as the events are "mostly" independent from one another and aren't individually too likely, then there will still be a positive probability that none of them occurs. It is most commonly used in the probabilistic method, in particular to give existence proofs.

In mathematics, the Schwartz–Zippel lemma is a tool commonly used in probabilistic polynomial identity testing, i.e. in the problem of determining whether a given multivariate polynomial is the 0-polynomial. It was discovered independently by Jack Schwartz, Richard Zippel, and Richard DeMillo and Richard J. Lipton, although DeMillo and Lipton's version was shown a year prior to Schwartz and Zippel's result. The finite field version of this bound was proved by Øystein Ore in 1922.

The expander mixing lemma intuitively states that the edges of certain -regular graphs are evenly distributed throughout the graph. In particular, the number of edges between two vertex subsets and is always close to the expected number of edges between them in a random -regular graph, namely .

In mathematics, the Grothendieck inequality states that there is a universal constant with the following property. If Mij is an n × n matrix with

In extremal graph theory, the forbidden subgraph problem is the following problem: given a graph , find the maximal number of edges an -vertex graph can have such that it does not have a subgraph isomorphic to . In this context, is called a forbidden subgraph.

<span class="mw-page-title-main">Graphon</span>

In graph theory and statistics, a graphon is a symmetric measurable function , that is important in the study of dense graphs. Graphons arise both as a natural notion for the limit of a sequence of dense graphs, and as the fundamental defining objects of exchangeable random graph models. Graphons are tied to dense graphs by the following pair of observations: the random graph models defined by graphons give rise to dense graphs almost surely, and, by the regularity lemma, graphons capture the structure of arbitrary large dense graphs.

In arithmetic combinatorics, the corners theorem states that for every , for large enough , any set of at least points in the grid contains a corner, i.e., a triple of points of the form with . It was first proved by Miklós Ajtai and Endre Szemerédi in 1974 using Szemerédi's theorem. In 2003, József Solymosi gave a short proof using the triangle removal lemma.

In graph theory, the graph removal lemma states that when a graph contains few copies of a given subgraph, then all of the copies can be eliminated by removing a small number of edges. The special case in which the subgraph is a triangle is known as the triangle removal lemma.

In graph theory, the hypergraph removal lemma states that when a hypergraph contains few copies of a given sub-hypergraph, then all of the copies can be eliminated by removing a small number of hyperedges. It is a generalization of the graph removal lemma. The special case in which the graph is a tetrahedron is known as the tetrahedron removal lemma. It was first proved by Nagle, Rödl, Schacht and Skokan and, independently, by Gowers.

The counting lemmas this article discusses are statements in combinatorics and graph theory. The first one extracts information from -regular pairs of subsets of vertices in a graph , in order to guarantee patterns in the entire graph; more explicitly, these patterns correspond to the count of copies of a certain graph in . The second counting lemma provides a similar yet more general notion on the space of graphons, in which a scalar of the cut distance between two graphs is correlated to the homomorphism density between them and .

In the mathematical field of graph theory, Hall-type theorems for hypergraphs are several generalizations of Hall's marriage theorem from graphs to hypergraphs. Such theorems were proved by Ofra Kessler, Ron Aharoni, Penny Haxell, Roy Meshulam, and others.

Flag algebras are an important computational tool in the field of graph theory which have a wide range of applications in homomorphism density and related topics. Roughly, they formalize the notion of adding and multiplying homomorphism densities and set up a framework to solve graph homomorphism inequalities with computers by reducing them to semidefinite programming problems. Originally introduced by Alexander Razborov in a 2007 paper, the method has since come to solve numerous difficult, previously unresolved graph theoretic questions. These include the question regarding the region of feasible edge density, triangle density pairs and the maximum number of pentagons in triangle free graphs.

In mathematics, the hypergraph regularity method is a powerful tool in extremal graph theory that refers to the combined application of the hypergraph regularity lemma and the associated counting lemma. It is a generalization of the graph regularity method, which refers to the use of Szemerédi's regularity and counting lemmas.

The blow-up lemma, proved by János Komlós, Gábor N. Sárközy, and Endre Szemerédi in 1997, is an important result in extremal graph theory, particularly within the context of the regularity method. It states that the regular pairs in the statement of Szemerédi's regularity lemma behave like complete bipartite graphs in the context of embedding spanning graphs of bounded degree.

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 .