Maximum number of edges in a subgraph of hypercube Let $H_n$ is an $n$-dimensional hypercube, $|V(H_n)|=2^n, |E(H_n)|=n2^{n-1}$. Let $M\subset V(H_n), |M|=2^k, 1\le k<n$, and $G_M$ is a subgraph of $H_n$ induced by $M$, $V(G_M)=2^k$. 
Prove that the maximum $|E(G_M)|$ is achieved iff $G_M$ is a $k$-dimensional hyperface of $H_n$ (then $|E(G_M)|=k2^{k-1}$).
I found this sequence and this paper. But I believe that simple and beautiful proof exists for this particular case.
 A: The slickest proof I've seen for this fact uses an entropy argument.  The idea is to let $X = (X_1,\ldots,X_n)$ be a uniformly random vertex in $M$ and upper and lower bound the entropy $H(X)$.   Using the chain rule and the fact that conditioning never increases entropy, we have  
\begin{eqnarray} \log_2|M| = H(X) 
= \sum_{i=1}^n H(X_i\mid X_{< i}) 
\geq \sum_{i=1}^n H(X_i\mid X_{-i}) 
= \frac{2\cdot|E(G_m)|}{|M|}.\end{eqnarray}
The final equality is because, by definition, $H(X_i \mid X_{-i}=x) = 1$ if and only if the edge $\{x, x^{i}\}$ exists in $M$, where $x^{i}$ is the vector obtained from $x$ by flipping the $i$th bit. The factor of two is because  each edge in $M$ corresponds to two endpoints in $M$.
To answer your question, notice that the inequality in the proof obtains equality if and only if the variables $X_1,\ldots,X_n$ are independent.  This follows since we actually know the stronger condition 
$$H(X_i\mid X_{< i}) 
= H(X_i\mid X_{-i}),$$
for each $i \in [n]$ and for every permutation of the coordinates. For the variables to be independent, and induced by $M \subseteq \{0,1\}^n$, each $X_i$ must be either constant or uniform in $\{0,1\}$. Therefore, equality holds if and only if $|M| = 2^k$ for some $k$ and $M$ is a hyperface (a.k.a subcube).  
A reference for the counting part of this proof is Theorem 4.2 in the book Concentration Inequalities: A Nonasymptotic Theory of Independence, By Stéphane Boucheron, Gábor Lugosi, Pascal Massart.  (Here is a link for google books, see Sections 4.3 and 4.4).
FYI, this bound is known as the "edge-isoperimetric inequality" for the hypercube.
