Let
\(X=(X_1,\dots,X_d)\) be a uniformly random vertex of
\(A\) where, for
\(1\leq i\leq d\text{,}\) \(X_i\) is the
\(i\)th coordinate of
\(X\text{.}\) By
Lemma 7.1.4 and Han’s Inequality, we have
\begin{equation*}
\log_2(|A|) = \mathbb{H}(X) = n\mathbb{H}(X) -(n-1) \mathbb{H}(X)
\end{equation*}
\begin{equation*}
\geq n\mathbb{H}(X) - \sum_{j=1}^n\mathbb{H}(X_i: i\neq j) = \sum_{j=1}^n[\mathbb{H}(X) - \mathbb{H}(X_i: i\neq j)]\text{.}
\end{equation*}
\begin{equation*}
\sum_{j=1}^n\mathbb{H}(X_j\mid X_i: i\neq j)\text{.}
\end{equation*}
Note that, for each \(1\leq j\leq n\text{,}\) \(\rng(X_i:i\neq j)\) is the set of all sequences of the form \((x_1,\dots,x_{j-1},x_{j+1},\dots,x_n)\) where \((x_1,\dots,x_n)\in A\text{.}\) Going all the way back to the definition of conditional entropy, we get that
\begin{equation*}
\mathbb{H}(X_j\mid X_i: i\neq j) = \sum_{(x_i: i\neq j)\in \rng(X_i:i\neq j)}\mathbb{P}((X_i: i\neq j)=(x_i: i\neq j))\mathbb{H}(X_j\mid (X_i: i\neq j)=(x_i: i\neq j))\text{.}
\end{equation*}
Given \(x = (x_1,\dots,x_n)\in \{0,1\}^d\text{,}\) let \(x^j\) be the vertex of the hypercube obtained from \(x\) by changing the \(j\)th coordinate from \(0\) to \(1\) or vice versa. Then, for any such pair \(\{x,x^j\}\subseteq \{0,1\}^d\text{,}\) we have
\begin{equation*}
\mathbb{P}((X_i: i\neq j)=(x_i: i\neq j)) = \frac{|\{x\cap x^j\}\cap A|}{|A|}\text{.}
\end{equation*}
Also, the number of choices for \(X_j\) given that \((X_i:i\neq j)=(x_i:
i\neq j)\) is equal to \(|\{x\cap x^j\}\cap A|\text{.}\) Thus, assuming that \((x_i:i\neq j)\in \rng(X_i:i\neq j)\text{,}\) we have
\begin{equation*}
\mathbb{H}(X_j\mid (X_i: i\neq j)=(x_i: i\neq j))=\log_2(|\{x\cap x^j\}\cap A|)
\end{equation*}
which is equal to \(\log_2(1)=0\) if \(|\{x\cap x^j\}\cap A|=1\) and \(\log_2(2)=1\) otherwise. Thus, \(\mathbb{H}(X_j\mid X_i: i\neq j)\) is equal to \(\frac{2}{|A|}\) times the number of pairs \(\{x,x^j\}\subseteq \{0,1\}^d\) such that both \(x\) and \(x^j\) belong to \(A\text{.}\) In other words, \(\mathbb{H}(X_j\mid X_i:
i\neq j)\) is precisely equal to the number of edges within \(A\) whose endpoints differ on the \(j\)th coordinate. Therefore,
\begin{equation*}
\sum_{j=1}^n\mathbb{H}(X_j\mid X_i: i\neq j) = \frac{2e(A)}{|A|}\text{.}
\end{equation*}
Putting this all together gives us
\begin{equation*}
\log_2(|A|) \geq\frac{2e(A)}{|A|}
\end{equation*}
and we are done by solving for \(e(A)\text{.}\)
