The method of Hypergraph Containers - Probabilistic Combinatorics

12 The method of Hypergraph Containers

Definition 12.1. For graphs $G$ , $H$ ,

ex (G, H) = \max {e (K) : K \subset G and K ⁄ \supset H} .

Example. $ex (n, H) = ex (K_{n}, H)$ .

We are interested in $ex (G, K_{3})$ when $G \sim G (n, p)$ .

Theorem 12.2 (Frankl, Rödl). For $p ≫ \frac{1}{\sqrt{n}}$ and $G \sim G (n, p)$ ,

ex (G, K_{3}) = (1 + o (1)) \frac{p n^{2}}{4}

with high probability.

Remark.

Easy to see “ $\geq$ ”: consider a bipartition
If $p \leq \frac{𝜀}{\sqrt{n}}$ , then recall from earlier in the course our work on $R (3, k)$ : in this regime for $p$ , we have few triangles compared to number of edges, so we can get a triangle-free subgraph by just deleting an edge from every triangle.

Let $m = (1 + δ) \frac{p n^{2}}{4}$ . Let

X_{m} = | {H \subset G : H ⁄ \supset K_{3} and e (H) = m} | .

If $𝔼 X_{m} \to 0$ , then by Markov done. But:

\begin{array}{l} 𝔼 X_{m} & = | {H \subset K_{n} : H ⁄ \supset K_{3}, e (H) = m} | \cdot p^{m} \\ \geq (\binom{\frac{n^{2}}{4}}{m}) \cdot p^{m} \\ \geq {(\frac{p n^{2}}{m})}^{m} \\ \geq {(\frac{4}{(1 + δ)})}^{n^{3 ∕ 2}} \\ \to \infty \end{array}

So first moment method fails horribly here.

Remark. This quantity is useluss because these triangle free graphs are very correlated.

Idea: What if every $K_{3}$ -free graph was bipartite? (This is a massive lie, but we discuss it anyway to motivate the proof of Frankl, Rödl).

\begin{array}{l} ℙ (\exists H, H \subset G, e (H) = m, H ⁄ \supset K_{3}) \\ \overset{!}{\leq} \sum_{(A, A^{c}) bipartite on V (G)} ℙ (| G \cap (A \times A^{c}) | \geq m) \\ \leq 2^{n} \exp {(- \frac{(δ p n^{2})}{3 \frac{p n^{2}}{4}})}^{2} \\ \to 0 \end{array}

(the $!$ is to emphasise that here we use the false statement that “every triangle-free graph is bipartite”). On the penultimate step, we used that

𝔼 | G \cap (A \times A^{c}) | \leq \frac{n^{2}}{4} \cdot p \leq 2^{n} \exp (- δ^{2} p n^{2}) .

But $m \geq (1 + δ) \frac{p n^{2}}{4}$ .

Note that there exist triangle-free graphs that are far from being bipartite:

So we need something a little different:

Theorem 12.3 (Containers for triangle-free graphs). For all $n$ , there exists a collection of graphs $C_{n}$ with the following properties:

(1) $| C | \leq n^{O (n^{3 ∕ 2})}$ .
(2) every $G \in C$ contains at most $o (n^{3})$ triangles.
(3) every triangle-free graph on $n$ vertices is contained in some $G \in C$ .

Remark. This result is essentially sharp. Before we constructed very “random like” graphs with density $p = \frac{γ}{\sqrt{n}}$ . So we expect $(\binom{\frac{n^{2}}{2}}{\frac{p n^{2}}{2}}) = n^{O (n^{3 ∕ 2}}$ such graphs. Intuitively, these should be in different containers.

Lemma 12.4 (Supersaturation). For all $𝜀 > 0$ , there exists $δ$ such that: If $G$ is an $n$ vertex graph with

e (G) \geq (1 + 𝜀) \frac{n^{2}}{4},

then $G$ contains $δ n^{3}$ triangles.

Proof. Let $k$ be a large constant. Note $(\binom{n}{2}) (\binom{n - 02}{k - 2}) = (\binom{n}{k}) (\binom{k}{2})$ Consider

\begin{array}{l} (*) & = \frac{1}{(\binom{n}{k})} \sum_{S \in {[n]}^{(k)}} \frac{e (G [S])}{(\binom{k}{2})} \\ = \frac{e (G)}{(\binom{n}{k}) (\binom{k}{2})} \cdot (\binom{n - 2}{k - 2}) \\ = \frac{e (G)}{(\binom{n}{2})} \\ \geq \frac{1}{2} (1 + 𝜀) \end{array}

If the number of $k$ subsets with $> \frac{1}{2} (\binom{k}{2})$ edges is $η (\binom{n}{k})$ , then

(*) \leq η \cdot 1 + \frac{1}{2} (1 - η) \leq \frac{1}{2} (1 + η) .

So $η \geq 𝜀$ . Apply Turán to this $𝜀$ proportion of subsets. This gives us $𝜀 (\binom{n}{k})$ pairs of $(k -subsets, triangles)$ . But each triangle is counted at most $(\binom{n - 3}{k - 3})$ . So there must exist

\geq \frac{𝜀 (\binom{n}{k})}{(\binom{n - 3}{k - 3})} \geq c 𝜀 n^{3}

triangles, for some $c > 0$ . □

Proof of Frankl, Rödl for $p ≫ \frac{\log n}{\sqrt{n}}$ . Let $p ≫ \frac{\log n}{\sqrt{n}}$ , $G \sim G (n, p)$ , $m = (1 + δ) \frac{p n^{2}}{4}$ .

\begin{array}{l} ℙ (\exists H, H ⁄ \supset K_{3}, H \subset G, e (H) = m) & \leq ℙ (\exists K \in C_{n}, | H \cap G | \geq (1 + δ) \frac{p n^{2}}{2}) \\ \leq \sum_{K \in C_{n}} ℙ (| K \cap G | \geq (1 + δ) \frac{p n^{2}}{2}) \end{array}

Note that by Supersaturation,

𝔼 | K \cap G | = p \cdot e (K) \leq p (1 + o (1)) \frac{n^{2}}{4} .

So we can continue the earlier calculation to get

\begin{array}{l} \leq | C_{n} | \exp (- \frac{{(δ \frac{p n^{2}}{2})}^{2}}{3 \frac{p n^{2}}{4}}) \\ = n^{C n^{3 ∕ 2}} \exp (c δ^{2} p n^{2}) \\ = n^{C n^{3 ∕ 2}} \exp (- C_{2} (\log n) n^{3 ∕ 2}) \\ \to 0 \end{array}

if $C_{2} > C$ . □

Theorem 12.5. If $p ≫ \frac{1}{\sqrt{n}}$ and $G \sim G (n, p)$ then $G \to K_{3}$ with high probability.

Remark. If $p < \frac{γ}{\sqrt{n}}$ then $G ⁄ \to K_{3}$ with high probability for $γ$ small.

Sketch proof: pick an edge from each triangle and colour it blue. Since the number of triangles is small compared to the number of edges, we don’t colour too many blue. Colour the rest red. Now as long as we didn’t create any blue triangles, this works.

Lemma 12.6 (“Supersaturation” Lemma). Let $𝜀 > 0$ be sufficiently small. Let $K_{n}$ be coloured with red / blue / grey with the property that $\leq 𝜀 n^{2}$ are grey. Then there are $c n^{3}$ monochromatic triangles in red or blue.

Proof. There are at most $𝜀 n^{6}$ $K_{6}$ ’s that contain a grey edge. So there are $\geq (\binom{n}{6}) - 𝜀 n^{6} = (*)$ $K_{6}$ ’s that are only red / blue coloured. Each one of these contains a monochromatic triangle. So we have $\geq (*)$ many pairs ( $K_{6}$ , monochromatic $K_{3}$ ). So there exist $\geq \frac{(*)}{n^{3}} \geq c n^{3}$ monochromatic $K_{3}$ ’s in red or blue. □

Proof of Theorem 12.5 for $p \geq \frac{C^{'} \log n}{\sqrt{n}}$ . Let $p \geq \frac{C^{'} \log n}{\sqrt{n}}$ , $G \sim G (n, p)$ . Then

\begin{array}{l} ℙ (G ⁄ \to K_{3}) & \leq ℙ (\exists H_{1}, H_{2}, K_{3} -free with G \supset H_{1} \cup H_{2}) \\ \leq ℙ (\exists K_{1}, K_{2} \in C with G \supset K_{1} \cup K_{2}) \\ \leq \sum_{K_{1}, K_{2} \in C} ℙ (G \subset K_{1} \cup K_{2}) \\ \leq \sum {(1 - p)}^{| V (G) ∖ K_{1} \cup K_{2} |} \end{array}

By Lemma 12.6, $| V (G) ∖ K_{1} \cup K_{2} | \geq 𝜀 n^{2}$ , the above is

\leq | C | \cdot e^{- p \cdot 𝜀 n^{2}} \leq n^{C n^{3 ∕ 2}} e^{- C (\log n) n^{3 ∕ 2}}

for some large $C^{'}$ , so $\to 0$ as $n \to \infty$ . □

12.1 Proving the earlier container lemma

We will sketch the proof of Theorem 12.3.

Consider the $3$ -uniform hypergraph $H_{n}$ defined by

V (H_{n}) = E (K_{n}) H_{n} = {{e, f, g} : e, f, g form a triangle} .

Key observation is that $G \subset V (H_{n})$ is a graph on $[n]$ , and that $G$ is independent in $H_{n}$ if and only if $G$ is a triangle-free graph.

Here we say $G \subset V (H)$ is independent if it induces no edge of $H$ .

Notation. Given a hypergraph $H$ , define

Δ_{l} (H) = \max {d_{H} (A) : A \subset V (H), | A | = l},

where $d_{H} (A) = | {B \in E (H) : A \subset B} |$ .

We will write $Δ (H)$ to mean $Δ_{1} (H)$ .

Theorem 12.7 (Hypergraph Container Theorem for $3$ -uniform hypergraphs). For $C > 0$ , there exists $δ > 0$ so that the following holds. Let $H$ be a $3$ -uniform hypergraph with average degree $d$ and

Δ (H) \leq C d and Δ_{2} (H) \leq C \sqrt{d} .

Then there exists a collection $C \subset P (V (H))$ with the following properties:

(1) $| C | \leq (\binom{| V (H) |}{\frac{| V (H) |}{\sqrt{d}}})$ .
(2) $\forall C \in C$ , $| C | \leq (1 - δ) | V (H) |$ .
(3) For every independent set $I$ in $H$ , there exists $C \in C$ such that $I \subset C$ .

Due to Saxton, Thomason and Balogh, Morris, Samotij.

Sketch proof of container lemma for $K_{3}$ -free graphs (Theorem 12.3) using Hypergraph Container Theorem for $3$ -uniform hypergraphs:

We note that all degrees are $n - 2$

So average degree is $n - 2$ , and $Δ (H_{n}) = n - 2$ .

We have $Δ_{2} (H_{n}) = 1$ , since for a pair of edges $e$ , $f$ , we have $d_{H} ({e, f})$ is either $0$ or $1$ .

So we can apply Hypergraph Container Theorem for $3$ -uniform hypergraphs to $H_{n}$ with $d = n - 2$ and $C = 1$ . We obtain a collection $C$ of graphs

| C | \leq (\binom{\frac{n^{2}}{2}}{\frac{n^{2}}{2 \sqrt{n}}}) = n^{O (n^{3 ∕ 2}} .

Note that every triangle-free graph is contained in some $G \in C$ . We also have $e (G) \leq (1 - δ) (\binom{n}{2})$ .

We now repeat the following:

Suppose some $G \in C$ (current set of containers) has $\geq 𝜀 n^{3}$ triangles. Then consider $H_{n} [G]$ .

The average degree is $𝜀 n$ and $Δ (H_{n} [G]) \leq n$ , $Δ_{2} (H_{n} [G]) \leq 1$ . So apply Theorem 12.7 again to $H_{n} [G]$ with $d = 𝜀 n$ and $C = \frac{1}{𝜀}$ . Now put all of these containers into my collection.

We can imagine this process as creating a rooted tree, whose vertices are containers, and whose leaves are containers with $\leq 𝜀 n^{3}$ triangles.

Note we can only apply this at most $\leq \frac{2}{δ} \log \frac{1}{𝜀}$ times to a container (because after this many steps we have so few edges of $K_{n}$ left that we must have $\leq 𝜀 n^{3}$ triangles). Thus the total number of containers at the end is

\begin{array}{l} \leq (\binom{\frac{n^{2}}{2}}{\frac{n^{2}}{2 \sqrt{n}}}) {(\binom{\frac{n^{2}}{2}}{\frac{n^{2}}{2 \sqrt{𝜀 n}}})}^{\frac{2}{𝜀} \log \frac{1}{δ}} \\ \leq n^{O_{𝜀} (n^{3 ∕ 2})} \end{array}

as desired.

By construction each of the containers has at most $𝜀 n^{3}$ triangles. Note that every triangle-free graph $G$ on $n$ vertices is contained in some $C \in C$ for our initial application. This property is preserved when we replace a $C \in C$ with a collection of containers for $H [C]$ .

This lecture is non-examinable.

Theorem 12.8. For all $C > 0$ , there exists $δ > 0$ ( $δ = \frac{1}{4 C}$ ) such that the following holds. Let $G$ be a graph with average degree $d$ and $Δ (G) \leq C d$ . Then there exists $C \subset P (V (G))$ such that:

(1) $| C | \leq (\binom{n}{\leq \frac{2 δ n}{d}})$ .
(2) For $C \in C$ we have $| C | \leq (1 - δ) n$ .
(3) Every independent set in $G$ is contained in some $C \in C$ .

Due to Kleitman and Winston, 80s.

Notation. $(\binom{n}{\leq k}) = \sum_{i = 0}^{k} (\binom{n}{i})$ .

Given $G$ and $I$ , we run an algorithm that produces $F (I)$ , $A (I)$ satisfying

\underset{“the fingerprint”}{\underset{⏟}{F (I)}} \subset I \subset \underset{C (I) is the container}{\underset{⏟}{F (I) \cup A (I)}}

Graph Containers algorithm. We maintain, as the algorithm runs, a partition

V (G) = \underset{the vertices}{\underset{⏟}{A}} \cup \underset{bin}{\underset{⏟}{B}} \cup \underset{fingerprint so far}{\underset{⏟}{F}},

and we start with $A = V (G)$ , $B = \emptyset$ , $F = \emptyset$ . While $| B | < δ \cdot n$ , we loop the following:

Let $v \in A$ be a vertex of maximum degree in $G [A]$ (and tiebreak according to some fixed ordering of $G$ specified in advance, so that the algorithm is deterministic / reproducible: useful for observation later).

(1) If $v \notin I$ , then just move $v$ into $B$ .
(2) If $v \in I$ , then move $v$ into $F$ and move all of $N (v) \cap A$ into $B$ .

When algorithm stops, we define $A (I) = A$ and $F (I) = F$ .

Observation: $F (I) \subset I \subset F (I) \cup A (I)$ .

Proof. First inclusion holds by definition. For second one: I never move a vertex of $I$ into $B$ . □

Observation: $A (I)$ is determined by $F (I)$ .

Proof. We claim that if we run algorithm on input $F (I)$ then we would get same output (here we use the fact that we defined and used an ordering of $G$ to make the algorithm deterministic / reproducible). □

Observation: $| F (I) | \leq \frac{δ n}{d}$ .

Proof. We show that if we move a vertex into $F$ , we move $\geq \frac{d}{2}$ vertices in $A$ to $B$ . Note that at all times in the algorithm,

\begin{array}{l} e (G [A]) & \geq e (G) - | B | \cdot Δ (G) \\ \geq \frac{d n}{2} - δ n \cdot C d \\ \geq \frac{d n}{4} \end{array}

So $Δ (G [A]) \geq \frac{d}{2}$ for all steps.

If $| F (I) | > \frac{2 δ n}{2}$ , then $| B | > (\frac{2 δ n}{d}) \cdot \frac{d}{2} > δ n$ , contradiction. □

Proof of Theorem 12.8. We define

C = {A (I) \cup F (I) : I independent in G} .

Property (3) holds by the first observation.

For (2), note that $| A (I) \cup F (I) | = n - | B | \leq (1 - δ) n$ .

For property (1), note that the number of $F (I)$ ’s is at most $(\binom{n}{\frac{2 δ n}{d}})$ , and each $F (I)$ determines $F (I) \cup A (I)$ by the second observation. □

Informal explanation of the proof:

Suppose Alice and Bob both know the structure of a certain graph. Suppose Alice is given an independent set $I$ , and wants to communicate about its structure to Bob, by giving him a list of some vertices from $I$ . It makes sense for Alice to start by telling Bob which vertex has the highest degree in $I$ , since this then tells him a lot of vertices aren’t in $I$ :

For the next vertex, Alice shouldn’t just tell Bob the next highest degree vertex, because its neighbourhood might overlap a lot with the first vertex, in which case telling Bob about this vertex wouldn’t give him much new information. So instead, it makes more sense to pick the vertex with highest degree into the set of vertices which Bob hasn’t yet discarded; this gives us the algorithm described above.

If none of the vertices in $I$ have large degree, then Bob actually can still gain a lot of information from Alice, if Alice (implicitly) says “this vertex $v$ is in $I$ , and it is the most informative vertex I could have told you about”. Using this strategy, Bob can gain useful no matter what: if $I$ contains a large degree vertex, then Bob can immediately discard a lot of vertices. If it doesn’t, then when Alice tells Bob a vertex, Bob now knows $I$ doesn’t contain any high degree vertices, which in itself is very valuable information.

Generalising to hypergraphs:

We employ a similar strategy.

In this case, when Alice tells Bob about a vertex, he can’t immediately discard any vertices. Instead we have the following: ${u, v, w}$ is an edge, and Alice tells Bob that $v \in I$ , then Bob now knows that it can’t be the case that both of $u$ , $v$ are in $I$ . Bob can keep track of this information in a graph, where we can borrow ideas from the proof of graph containers. The proof will be more complex, and we will need to make use of the condition on $Δ_{2}$ .

Container algorithm for $3$ -uniform hypergraphs. We maintain

V (H) = A \cup B \cup F

a partition. We also have a graph $G$ , that we keep track of throughout the algorithm. We keep the following until $| A | < (1 - δ) N$ .

(1) If $Δ (G [A]) \geq c \sqrt{d}$ , then choose a vertex $x \in A$ with maximum degree (and break ties deterministically as before). If $x \notin I$ , then move it to $B$ . If $x \in I$ , then move into $F$ and move $N_{G} (x) \cap A$ to $B$ .
(2) If $Δ (G [A]) < c \sqrt{d}$ , then let $x \in H [A]$ with maximum degree. If $x \notin I$ , then move $x$ to $B$ . If $x \in I$ , move $x$ to $F$ , and add all the edges
${y z : {x, y, z} \in H [A]}$

into $G$ . Now remove from $H$ all edges that contain an edge of $G$ .

We then put $F (I) = F$ , $A (I) = A$ at the end of the loop.

The proof that this algorithm works is somewhat similar to the proof for graph containers, but more complicated.