Shearer’s lemma and applications - Entropy Methods in Combinatorics

4 Shearer’s lemma and applications

Notation. Given a random variable $X = (X_{1}, \dots, X_{n})$ and $A = {a_{1}, \dots, a_{k}} \subset [n]$ with $a_{1} < a_{2} < \dots < a_{k}$ , write $X_{A}$ for the random variable $(X_{a_{1}}, X_{a_{2}}, \dots, X_{a_{k}})$ .

Lemma 4.1 (Shearer). Assuming that:

$X = (X_{1}, \dots, X_{n})$ a random variable
$A$ a family of subsets of $[n]$ such that every $i \in [n]$ belongs to at least $r$ of the sets $A \in A$

Then

H [X_{1}, \dots, X_{n}] \leq \frac{1}{r} \sum_{A \in A} H [X_{A}] .

Proof. For each $a \in [n]$ , write $X_{< a}$ for $(X_{1}, \dots, X_{a - 1})$ .

For each $A \in A$ , $A = {a_{1}, \dots, a_{k}}$ with $a_{1} < \dots < a_{k}$ , we have

\begin{array}{l} H [X_{A}] & = H [X_{a_{1}}] + H [X_{a_{2}} | X_{a_{1}}] + \dots + H [X_{a_{k}} | X_{a_{1}}, \dots, X_{a_{k}}] \\ \geq H [X_{a_{1}} | X_{< a_{1}}] + H [X_{a_{2}} | X_{< a_{2}}] + \dots + H [X_{a_{k}} | X_{< a_{k}}] & (Lemma 1.15) \\ = \sum_{a \in A} H [X_{a} | X_{< a}] \end{array}

Therefore,

\begin{array}{l} \sum_{A \in A} H [X_{A}] & \geq \sum_{A \in A} \sum_{a \in A} H [X_{a} | X_{< a}] \\ \geq r \sum_{a = 1}^{n} H [X_{a} | X_{< a}] \\ = r H [X] □ \end{array}

Alternative version:

Lemma 4.2 (Shearer, expectation version). Assuming that:

$X = (X_{1}, \dots, X_{n})$ a random variable
$A \subset [n]$ a randomly chosen subset of $[n]$ , according to some probability distribution (don’t need any independence conditions!)
for each $i \in [n]$ , $ℙ [i \in A] \geq μ$

Then

H [X] \leq μ^{- 1} 𝔼_{A} H [X_{A}] .

Proof. As before,

H [X_{A}] \geq \sum_{a \in A} H [X_{a} | X_{< a}] .

\begin{array}{l} 𝔼_{A} H [X_{A}] & \geq 𝔼_{A} \sum_{a \in A} H [X_{a} | X_{< a}] \\ \geq μ \sum_{a = 1}^{n} H [X_{a} | X_{< a}] \\ = μ H [X] □ \end{array}

Definition ( $P_{A}$ ). Let $E \subset ℤ^{n}$ and let $A \subset [n]$ . Then we write $P_{A} E$ for the set of all $u \in ℤ^{A}$ such that there exists $v \in ℤ^{[n] ∖ A}$ such that $[u, v] \in E$ , where $[u, v]$ is $u$ suitably intertwined with $v$ (i.e. $u \cup v$ as functions).

Corollary 4.3. Assuming that:

$E \subset ℤ^{n}$
$A$ a family of subsets of $[n]$ such that every $i \in [n]$ is contained at least $r$ sets $A \in A$

Then

| E | \leq \prod_{A \in A} | P_{A} E |^{\frac{1}{r}} .

Proof. Let $X$ be a uniform random element of $E$ . Then by Shearer,

H [X] \leq \frac{1}{r} \sum_{A \in A} H [X_{A}] .

But $X_{A}$ tkaes values in $P_{A} E$ , so

H [X_{A}] \leq \log | P_{A} X,

\log | E | \leq \frac{1}{r} \sum_{A} \log | P_{A} E | . □

If $A = {[n] ∖ {i} : i = 1, \dots, n}$ we get

| E | \leq \prod_{i = 1}^{n} | P_{[n] ∖ {i}} E |^{\frac{1}{n - 1}} .

This case is the discrete Loomis-Whitney theorem.

Theorem 4.4. Assuming that:

$G$ a graph with $m$ edges

Then

G

has at most

\frac{{(2 m)}^{\frac{3}{2}}}{6}

triangles.

Is this bound natural? Yes: if $m = (\binom{n}{2})$ , and we consider a complete graph on $n$ vertices, then we get approximately $\frac{{(2 m)}^{\frac{2}{3}}}{6}$ triangles.

Proof. Let $(X_{1}, X_{2}, X_{3})$ be a random ordered triangle (without loss of generality $G$ has a triangle so that this is possible).

Let $t$ be the number of triangles in $G$ . By Shearer,

\log (6 t) = H [X_{1}, X_{2}, X_{3}] \leq \frac{1}{2} (H [X_{1}, X_{2}] + H [X_{1}, X_{3}] + H [X_{2}, X_{3}]) .

Each edge $H [X_{i}, X_{j}]$ is supported in the set of edges $G$ , given a direction, i.e.

\frac{1}{2} (H [X_{1}, X_{2}] + H [X_{1}, X_{3}] + H [X_{2}, X_{3}]) \leq \frac{3}{2} \cdot \log (2 m) . □

Definition. Let $X$ be a set of size $n$ and let $G$ be a set of graphs with vertex set $X$ . Then $G$ is $Δ$ -intersecting (read as “triangle-intersecting”) if for all $G_{1}, G_{2} \in G$ , $G_{1} \cap G_{2}$ contains a triangle.

Theorem 4.5. Assuming that:

$| V | = n$
$G$ a $Δ$ -intersecting family with vertex set $V$

Then

G

has size at most

2^{(\binom{n}{2}) - 2}

Proof. Let $X$ be chosen uniformly at random from $G$ . We write $V^{(2)}$ for the set of (unordered) pairs of elements of $V$ . Think of any $G \in G$ as a function from $V^{(2)}$ to ${0, 1}$ . So $X = (X_{e} : e \in V^{(2)})$ .

For each $R \subset V$ , let $G_{R}$ be the graph $K_{R} \cup K_{V ∖ R}$

For each $R$ , we shall look at the projection $X_{G_{R}}$ , which we can think of as taking values in the set ${G \cap G_{R} : G \in G} = : G_{R}$ .

Note that if $G_{1}, G_{2} \in G$ , $R \subset [n]$ , then $G_{1} \cap G_{2} \cap G_{R} \neq \emptyset$ , since $G_{1} \cap G_{2}$ contains a triangle, which must intersect $G_{R}$ by Pigeonhole Principle.

Thus, $G_{R}$ is an intersecting family, so it has size at most $2^{| E (G_{R}) | - 1}$ . By Shearer, expectation version,

\begin{array}{l} H [X] & \leq 2 𝔼_{R} H [X_{G_{R}}] & (since each e belongs to G_{R} with probability 1 ∕ 2) \\ \leq 2 𝔼_{R} (| E (G_{R}) | - 1) \\ = 2 (\frac{1}{2} (\binom{m}{2}) - 1) \\ = (\binom{n}{2}) - 2 & □ \end{array}

Definition (Edge-boundary). Let $G$ be a graph and let $A \subset V (G)$ . The edge-boundary $\partial A$ of $A$ is the set of edges $x y$ such that $y \notin A$ .

If $G = ℤ^{n}$ or ${0, 1}^{n}$ and $i \in [n]$ , then the $i$ -th boundary $\partial_{i} A$ is the set of edges $x y \in \partial A$ such that $x - y = \pm e_{i}$ , i.e. $\partial_{i} A$ consists of deges pointing in direction $i$ .

Theorem 4.6 (Edge-isoperimetric inequality in $Z^{n}$ ). Assuming that:

$A \subset ℤ^{n}$ a finite set

Then

| \partial A | \geq 2 n | A |^{\frac{n - 1}{n}}

Proof. By the discrete Loomis-Whitney inequality,

\begin{array}{l} | A | & \leq \prod_{i = 1}^{n} | P_{[n] ∖ {i}} A |^{\frac{1}{n - 1}} \\ = {(\prod_{i = 1}^{n} | P_{[n] ∖ {i}} A |^{\frac{1}{n}})}^{\frac{n}{n - 1}} \\ \leq {(\frac{1}{n} \sum_{i = 1}^{n} | P_{[n] ∖ {i}} A |)}^{\frac{n}{n - 1}} \end{array}

But $| \partial_{i} A | \geq 2 | P_{[n] ∖ {i}} A |$ since each fibre contributes at least 2.

\begin{array}{l} | A | & \leq {(\frac{1}{2 n} \sum_{i = 1}^{n} | \partial_{i} A |)}^{\frac{n}{n - 1}} \\ = {(\frac{1}{2 n} | \partial A |)}^{\frac{n}{n - 1}} □ \end{array}

Theorem 4.7 (Edge-isoperimetric inequality in the cube). Assuming that:

$A \subset {0, 1}^{n}$ (where we take the usual graph)

Then

| \partial A | \geq | A | (n - \log | A |)

Proof. Let $X$ be a uniform random element of $A$ and write $X = (X_{1}, \dots, X_{n})$ . Write $X_{∖ i}$ for $(X_{1}, \dots, X_{i - 1}, X_{i + 1}, \dots, X_{n})$ . By Shearer,

\begin{array}{l} H [X] & \leq \frac{1}{n - 1} \sum_{i = 1}^{r} H [X_{∖ i}] \\ = \frac{1}{n - 1} \sum_{i = 1}^{n} H [X] - H [X_{i} | X_{∖ i}] \end{array}

Hence

\sum_{i = 1}^{n} H [X_{i} | X_{∖ i}] \leq H [X] .

Note

H [X_{i} | X_{∖ i} = u] = {\begin{matrix} 1 & | P_{[n] ∖ {i}}^{- 1} (u) | = 2 \\ 0 & | P_{[n] ∖ {i}}^{- 1} (u) | = 1 \end{matrix}

The number of points of the second kind is $| \partial_{i} A |$ , so $H [X_{i} | X_{∖ i}] = 1 - \frac{| \partial_{i} A |}{| A |}$ . So

\begin{array}{l} H [X] & \geq \sum_{i = 1}^{n} (1 - \frac{| \partial_{i} A |}{| A |}) \\ = n - \frac{| \partial A |}{| A |} \end{array}

Also, $H [X] = \log | A |$ . So we are done. □

Definition (Lower shadow). Let $A$ be a family of sets of size $d$ . The lower shadow $\partial A$ is ${B : | B | = d - 1, \exists A \in A, B \subset A}$ .

Notation. Let $h (x) = x \log \frac{1}{x} + (1 - x) \log \frac{1}{1 - x}$ (for $x \in [0, 1]$ ).

Theorem 4.8 (Kruskal-Katona). Assuming that:

$| A | = (\binom{t}{d}) = \frac{t (t - 1) \dots (t - d + 1)}{d!}$ for some real number $t$

Then

| \partial A | \geq (\binom{t}{d - 1})

Proof. Let $X = (X_{1}, \dots, X_{d})$ be a random ordering of the elements of a uniformly random $A \in A$ . Then

H [X] = \log (d! (\binom{t}{d})) .

Note that $(X_{1}, \dots, X_{d - 1})$ is an ordering of the elements of some $B \in \partial A$ , so

H [X_{1}, \dots, X_{d - 1}] \leq \log ((d - 1)! | \partial A |) .

So it’s enough to show

H [X_{1}, \dots, X_{d - 1}] \geq \log ((d - 1)! (\binom{t}{d - 1})) .

Also,

H [X] = H [X_{1}, \dots, X_{d - 1}] + H [X_{d} | X_{1}, \dots, X_{d - 1}]

and

H [X] = H [X_{1}] + H [X_{2} | X_{1}] + \dots + H [X_{d} | X_{1}, \dots, X_{d - 1}] .

We would like an upper bound for $H [X_{d}] X_{< d}$ . Our strategy will be to obtain a lower bound for $H [X_{k} | X_{< k}]$ in terms of $H [X_{k + 1} | X_{< k + 1}]$ . We shall prove that

2^{H [X_{k} | X_{< k}]} \geq 2^{H [X_{k + 1} | X_{< k + 1}]} + 1 \forall k .

Let $T$ be chosen independently of $X_{1}, \dots, X_{k - 1}$ with

T = {\begin{matrix} 0 & probability p \\ 1 & probability 1 - p \end{matrix}

( $p$ will be chosen and optimised later).

Given $X_{1}, \dots, X_{k - 1}$ , let

X^{*} = {\begin{matrix} X_{k + 1} & T = 0 \\ X_{k} & T = 1 \end{matrix}

Note that $X_{k}$ and $X_{k + 1}$ have the same distribution (given $X_{1}, \dots, X_{k - 1}$ ), so $X^{*}$ does as well. Then

\begin{array}{l} H [X_{k} | X_{< k}] & = H [X^{*} | X_{< k}] \\ \geq H [X^{*} | X_{\leq k}] & (Submodularity) \\ = H [X^{*}, T | X_{\leq k}] & (X_{\leq k} and X^{*} determine T) \\ = H [T | X_{\leq k}] + H [X^{*} | T, X_{\leq k}] & (additivity) \\ = H [T] + p H [X_{k + 1} | X_{1}, \dots, X_{k}] \\ + (1 - p) H [X_{k} | X_{1}, \dots, X_{k}] \\ = h (p) + p s \end{array}

where $h (p) = p \log \frac{1}{p} + (1 - p) \log \frac{1}{1 - p}$ and $s = H [X_{k + 1} | X_{1}, \dots, X_{k}]$ .

It turns out that this is maximised when $p = \frac{2^{s}}{2^{s} + 1}$ . Then we get

\frac{2^{s}}{2^{s} + 1} (\log (2^{s} + 1) - \log 2^{s}) + \frac{\log (2^{s} + 1)}{2^{s} + 1} + \frac{s 2^{s}}{2^{s} + 1} = \log (2^{s} + 1) .

This proves the claim.

Let $r = 2^{H [X_{d} | X_{1}, \dots, X_{d - 1}]}$ . Then

\begin{array}{l} H [X] & = H [X_{1}] + \dots + H [X_{d} | X_{1}, \dots, X_{d - 1}] \\ \geq \log r + \log (r + 1) + \dots + \log (r + d - 1) \\ = \log (\frac{(r + d - 1)!}{(r - 1)!}) \\ = \log (d! (\binom{r + d - 1}{d})) \end{array}

Since $H [X] = \log (d! (\binom{t}{d}))$ , it follows that

r + d - 1 \leq t, r \leq t + 1 - d .

It follows that

\begin{array}{l} H [X_{1}, \dots, X_{d - 1}] & = \log (d! (\binom{t}{d})) - \log r \\ \geq \log (d! \frac{t!}{d! (t - d)! (t + 1 - d)}) \\ = \log ((d - 1)! (\binom{t}{d - 1})) □ \end{array}