Containers, containers, containers

It’s been a while since I managed to wrap up some projects (moving continents and getting more kids sure does take some time!), but the last few weeks I managed to get some work done. First, the paper with Ishay Haviv, Aleksa Milojević and Yuval Wigderson appeared, and today one with Geertrui Van de Voorde did.

Both of them are essentially applications of the container method to combinatorial problems. I first learned about this method while at UCSD, and indeed, it has been instrumental in the Ramsey result with Jacques (whose published version is now available). Admittedly, my understanding was still rather poor, so I decided to study a bit more last winter. I’ll share some of my newly-gained understanding in the course of summarizing both of these two results.

The container method

Here’s a beautiful summary of the principle of containers from a paper by Gwen McKinley (formerly at USCD while I was there), Asaf Ferber (UC Irvine, just one hour north of UCSD) and Wojciech Samotij (who we’ll meet later):

Roughly speaking, the lemma states that if the edges of a uniform hypergraph are ‘well-distributed’, then the following holds. There is a ‘relatively small’ collection of subsets of (referred to as containers), each of which induces ‘not too many’ hyperedges, such that every independent set of is a subset of at least one container.

In other words, the container method aims to construct subsets of the vertex set of a (hyper)graph which
(1) are few,
(2) induce few (hyper)edges, and,
(3) every independent set of is contained in one of these subsets.

Each subset of conditions is easily satisfied on its own, and the real strength of the container method is to combine all three. So while the idea is rather simple, the machinery behind it is quite involved and it took some time before its significance was realized. Indeed, the idea goes all the way back to 1980 when Kleitman and Winston used it for graphs to count graphs without 4-cycles. Then rather recently (not even 10 years ago!), it was generalized to hypergraphs by József Balogh, Rob Morris and Wojciech Samotij, and David Saxton and Andrew Thomason independently. I’ll refer you to the Wikipedia page for more history and references, but I would argue that the impact of these works can hardly be understated. For an extensive list of applications and further developments since these seminal results, I’ll refer you to the same Wikipedia page as before or the ICM survey by the first set of authors.

Just to give you a flavor, and so you understand why it takes some time to digest and understand the method, here’s a sample theorem.

Notation. Let be a -uniform hypergraph, then we use the notation and for the vertex set and hyperedge set of respectively. Their sizes are denoted by and respectively. The power set of the vertex set is denoted by and if then the induced hypergraph is denoted by . For a vertex subset denote by the number of edges that contain . Then define

Finally, denotes the family of independent sets of . We can now state a version of the container theorem.

Theorem. For all and there exists a constant such that the following holds. Suppose that is a -uniform hypergraph that satisfies

for all

and for some . Then there is a family and functions and such that

(A) ,
(B) .

To fully understand this theorem, I will refer you to the excellent lectures by Wojciech Samotij at IBS last winter, but let’s see why it implies the three conditions mentioned before. Given a hypergraph satisfying all assumptions, the theorem provides us with a set of containers . Conclusions (A) and (B) immediately imply (2) and (3) so we only need to see why there are few containers. The reason that is small, is because each container is determined as the image under of a small set in . Since there are few small sets there are also few containers, et voilà.

There are many versions and pre-packaged theorems which one can apply to the problem at hand, but it’s hard to see the forest for the trees in the beginning. I can highly recommend the aforementioned video lectures if you want to get into more details, along with Rob Morris’ lecture notes.

Applications

A first immediate application of these theorems is that one can upper bound the number of independent sets of a given size, once we can bound the size of the containers. This is useful in itself as Geertrui and I tried to convey in our paper. I suppose mostly finite geometers need to be convinced that this is interesting, since combinatorialists have used this to count Sidon sets, -free graphs, and many more objects.
We find plenty of instances in finite geometry where the upper bound provided by the container theorem is asymptotically sharp. In particular, given a (hyper)graph coming from finite geometry, with independence number (i.e. the size of the largest independent set), we can show that for not too small, the number of independent sets of size satisfies

,

where the term goes to as the underlying prime power tends to infinity. Since partial spreads, partial ovoids, caps, EKR-sets, and many more can be rephrased as independent sets in appropriate graphs, we hence find bounds of this shape for all of these instances.

A second application is that we can feed the upper bound on the number of independent sets of given size into the union bound. In this setting, we sample each vertex of the hypergraph independently at random with probability and investigate what happens to the independent sets. This is often referred to as taking -random subsets of the vertex set. For instance, together with Geertrui, we can investigate the largest cap in a -random subset of . We focus on three dimensions since the plane case was already done by work of Bhowmick and Roche-Newton and Roche-Newton and Warren, and is the only other case where we have caps of size in .

The main difference with the papers referenced above is that we use a different packaged statement of the container method, found in a paper due to Saxton and Thomason. The statement of this theorem is even more involved (see Theorem 5.1 in this paper), so I will not replicate it here. The essence is that after applying the container theorem once, one can iterate it for every container on the induced hypergraph to obtain even smaller containers. Observe that this comes at a price of increasing the number of containers, but this increase is often negligible. The complexity of the theorem is due to the fact that the behavior of the parameters might change as the containers get smaller and smaller and this needs to be accounted for. While the theorem was definitely something I quickly glossed over in a first reading (this is gibberish!), it is not too bad once you have seen and got comfortable with different versions of the container lemmas and their applications. In our application, we need to invoke the iteration since we want our containers to have size , but is typically of order whenever is a (hyper)graph coming from finite geometry.

A variation on the same theme is to construct structures with `low independence number’, i.e. the induced hypergraph under consideration has low independence number, by sampling vertices uniformly at random. The idea being that we set the sample probability small enough so that ‘large’ independent sets are destroyed with positive probability. Indeed, this was a crucial step in our proof of the lower bound on , and was used throughout in the literature before that. This idea was for example used by Alon and Szegedy, in combination with a clever tensor product construction, to construct large sets of nearly orthogonal vectors in , that is, sets in which every members have an orthogonal pair.

Ishay Haviv and Dror Chawin managed to adapt the argument to prove a similar argument over finite fields. However, they did not use containers and instead devised an ingenious method to count independent sets in the relevant graph. Since this graph was the polarity graph over a finite field, which has featured several times on the blog before, I was curious to see if the container method could be applicable in this case. Indeed, together with Ishay, Aleksa, and Yuval, we managed to extend their results to sets of nearly orthogonal vectors in , where every members have orthogonal pairs. There’s also a bipartite version where you are allowed to select two subsets of size and find an orthogonal ‘cross-pair’. The proof is a straightforward extension of Alon and Szegedy’s, as shown to be possible by Ishay and Dror, by implementing the full strength of the container method.

So even though a few gaps in my understanding of containers remain, I’d say that I have gained a pretty functional knowledge over the last few months. It’s a beautiful piece of combinatorics with far-reaching implications and if I can learn how to use it, so can you!