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<\cdots <a_k$, we have

$$\begin{array}{llllll}\hfill H[X_A]& =H[X_{a_1}]+H[X_{a_2}|X_{a_1}]+\cdots +H[X_{a_k}|X_{a_1},\dots ,X_{a_k}]& \hfill & & \hfill & \\ \hfill & \ge H[X_{a_1}|X_{<a_1}]+H[X_{a_2}|X_{<a_2}]+\cdots +H[X_{a_k}|X_{<a_k}]& \hfill & \text{(Lemma }\text{1.15}\text{)}& \hfill & & \hfill & \\ \hfill & =\sum _{a\in A}H[X_a|X_{<a}]& \hfill & & \hfill & \end{array}$$

Therefore,

$$\begin{array}{llll}\hfill \sum _{A\in A}H[X_A]& \ge \sum _{A\in A}\sum _{a\in A}H[X_a|X_{<a}]& \hfill & \\ \hfill & \ge r\sum _{a=1}^{n}H[X_a|X_{<a}]& \hfill & \\ \hfill & =rH[X]\square & \hfill & \end{array}$$

Proof. As before,

$$H[X_A]\ge \sum _{a\in A}H[X_a|X_{<a}].$$

So

$$\begin{array}{llll}\hfill {𝔼}_{A}H[X_A]& \ge {𝔼}_A\sum _{a\in A}H[X_a|X_{<a}]& \hfill & \\ \hfill & \ge \mu \sum _{a=1}^{n}H[X_a|X_{<a}]& \hfill & \\ \hfill & =\mu H[X]\square & \hfill & \end{array}$$

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

$$H[X]\le \frac{1}{r}\sum _{A\in A}H[X_A].$$

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

$$H[X_A]\le \log |P_{A}X,$$

so

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 (6t)=H[X_1,X_2,X_3]\le \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])\le \frac{3}{2}\cdot \log (2m).\square$$

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\setminus 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\ne \varnothing$, 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}{llllllll}\hfill H[X]& \le 2{𝔼}_{R}H[X_{G_R}]& \hfill & (\text{since each }e\text{ belongs to }{G}_R\text{ with probability }1∕2)& \hfill & & \hfill & \\ \hfill & \le 2{𝔼}_R(|E(G_R)|-1)& \hfill & & \hfill & \\ \hfill & =2\left(\frac{1}{2}\left(\genfrac{}{}{0ex}{}{m}{2}\right)-1\right)& \hfill & & \hfill & \\ \hfill & =\left(\genfrac{}{}{0ex}{}{n}{2}\right)-2& \hfill & \square & \hfill & & \hfill & \end{array}$$

Proof. By the discrete Loomis-Whitney inequality,

$$\begin{array}{llll}\hfill |A|& \le \prod _{i=1}^n|P_{[n]\setminus \{i\}}A{|}^{\frac{1}{n-1}}& \hfill & \\ \hfill & ={\left(\prod _{i=1}^n|P_{[n]\setminus \{i\}}A{|}^{\frac{1}{n}}\right)}^{\frac{n}{n-1}}& \hfill & \\ \hfill & \le {\left(\frac{1}{n}\sum _{i=1}^n|P_{[n]\setminus \{i\}}A|\right)}^{\frac{n}{n-1}}& \hfill & \end{array}$$

But $|{\partial }_{i}A|\ge 2|P_{[n]\setminus \{i\}}A|$ since each fibre contributes at least 2.

So

$$\begin{array}{llll}\hfill |A|& \le {\left(\frac{1}{2n}\sum _{i=1}^n|{\partial }_{i}A|\right)}^{\frac{n}{n-1}}& \hfill & \\ \hfill & ={\left(\frac{1}{2n}|\partial A|\right)}^{\frac{n}{n-1}}\square & \hfill & \end{array}$$

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

$$\begin{array}{llll}\hfill H[X]& \le \frac{1}{n-1}\sum _{i=1}^{r}H[X_{\setminus i}]& \hfill & \\ \hfill & =\frac{1}{n-1}\sum _{i=1}^{n}H[X]-H[X_i|X_{\setminus i}]& \hfill & \end{array}$$

Hence

$$\sum _{i=1}^{n}H[X_i|X_{\setminus i}]\le H[X].$$

Note

$$H[X_i|X_{\setminus i}=u]=\{\begin{array}{cc}1\hfill & |P_{[n]\setminus \{i\}}^{-1}(u)|=2\hfill \\ 0\hfill & |P_{[n]\setminus \{i\}}^{-1}(u)|=1\hfill \end{array}$$

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

$$\begin{array}{llll}\hfill H[X]& \ge \sum _{i=1}^n\left(1-\frac{|{\partial }_{i}A|}{|A|}\right)& \hfill & \\ \hfill & =n-\frac{|\partial A|}{|A|}& \hfill & \end{array}$$

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

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 \left(d!\left(\genfrac{}{}{0ex}{}{t}{d}\right)\right).$$

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}]\le \log \left((d-1)!|\partial A|\right).$$

So it’s enough to show

$$H[X_1,\dots ,X_{d-1}]\ge \log \left((d-1)!\left(\genfrac{}{}{0ex}{}{t}{d-1}\right)\right).$$

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]+\cdots +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}]}\ge 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{array}{cc}0\hfill & \text{probability }p\hfill \\ 1\hfill & \text{probability }1-p\hfill \end{array}$$

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

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

$$X^{\ast }=\{\begin{array}{cc}{X}_{k+1}\hfill & T=0\hfill \\ X_k\hfill & T=1\hfill \end{array}$$

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

$$\begin{array}{llllll}\hfill H[X_k|X_{<k}]& =H[X^{\ast }|X_{<k}]& \hfill & & \hfill & \\ \hfill & \ge H[X^{\ast }|X_{\le k}]& \hfill & \text{(}\text{Submodularity}\text{)}& \hfill & & \hfill & \\ \hfill & =H[X^{\ast },T|X_{\le k}]& \hfill & \text{(}{X}_{\le k}\text{ and }{X}^{\ast }\text{ determine }T\text{)}& \hfill & & \hfill & \\ \hfill & =H[T|X_{\le k}]+H[X^{\ast }|T,X_{\le k}]& \hfill & \text{(}\text{additivity}\text{)}& \hfill & & \hfill & \\ \hfill & =H[T]+pH[X_{k+1}|X_1,\dots ,X_k]& \hfill & & \hfill & \\ \hfill & +(1-p)H[X_k|X_1,\dots ,X_k]& \hfill & & \hfill & \\ \hfill & =h(p)+ps& \hfill & & \hfill & \end{array}$$

where 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

This proves the claim.

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

Since $H[X]=\log \left(d!\left(\genfrac{}{}{0ex}{}{t}{d}\right)\right)$, it follows that

$$r+d-1\le t,r\le t+1-d.$$

It follows that