TAOCP 7.1.1 Exercise 79
Let $Q_m=\{0,1\}^m$.
Exercise 79. ▶ [M27] (R. L. Graham.) An induced subgraph of a hypercube is a graph whose vertices $v$ can be labeled with bit strings $l(v)$ in such a way that $u — v$ if and only if $l(u)$ and $l(v)$ differ in exactly one bit position. (Each label has the same length.)
a) One way to define an $n$-vertex subgraph of a hypercube is to let $l(v)$ be the binary representation of $v$, for $0 \le v < n$. Show that this subgraph has exactly $f(n) = \sum_{k=1}^{n} \nu(k)$ edges, where $\nu(k)$ is the sideways addition function. b) Prove that $f(n) \le n\lfloor \lg n\rfloor/2$. c) Prove that no $n$-vertex subgraph of a hypercube has more than $f(n)$ edges.
Verified: no
Solve time: 4m32s
Let $Q_m={0,1}^m$. Vertices are adjacent when they differ in exactly one coordinate. For $S\subseteq Q_m$, let $E(S)$ be the number of edges in the induced subgraph. Let $\nu(x)$ be the number of 1s in the binary string $x$.
We fix $m$ such that $2^m>n$.
(a) Initial segment $S={0,1,\dots,n-1}$
Write each integer $k\in[0,n-1]$ as an $m$-bit binary string.
For a vertex $k$, each coordinate $i$ with bit $1$ produces a neighbor $k^{(i)}$ obtained by flipping that bit to $0$. Since this strictly decreases the integer value, $k^{(i)}<k$, hence $k^{(i)}\in S$.
Thus every 1-bit of $k$ corresponds to a distinct edge inside $S$, and we associate that edge uniquely with the larger endpoint $k$.
No edge is double counted: every edge differs in exactly one coordinate $i$, and exactly one endpoint has a 1 in that coordinate and is larger in integer order.
Hence
$$ E(S)=\sum_{k=0}^{n-1}\nu(k)=f(n). $$
(b) Upper bound $f(n)\le \frac{n\lfloor \log_2 n\rfloor}{2}$
Let $m=\lfloor \log_2 n\rfloor$. Every $k<n$ has at most $m$ bits.
Write
$$ f(n)=\sum_{k=0}^{n-1}\nu(k) =\sum_{i=0}^{m-1} #{k<n : \text{bit } i \text{ of } k \text{ is }1}. $$
Fix a bit position $i$. As $k$ runs through consecutive integers, bit $i$ is periodic with period $2^{i+1}$, taking value $1$ exactly $2^i$ times per period. Hence in any interval of length $n$, the number of 1s in position $i$ is at most $n/2$.
Therefore each of the $m$ bit positions contributes at most $n/2$, giving
$$ f(n)\le \frac{mn}{2}=\frac{n\lfloor \log_2 n\rfloor}{2}. $$
(c) Extremal property: no $n$-vertex induced subgraph has more than $f(n)$ edges
We prove by induction on $m$ that for every $S\subseteq Q_m$ with $|S|=n$,
$$ E(S)\le f(n), $$
with equality for $S={0,1,\dots,n-1}$.
Step 1: Decomposition by the last coordinate
Split vertices according to the last bit:
$$ Q_m = Q_{m-1}\times{0}\ \cup\ Q_{m-1}\times{1}. $$
For $S\subseteq Q_m$, define
$$ S_0={x\in Q_{m-1} : x0\in S},\quad S_1={x\in Q_{m-1} : x1\in S}. $$
Thus $S_0,S_1\subseteq Q_{m-1}$, and $|S|=|S_0|+|S_1|$.
Step 2: Edge counting formula
Edges inside $S$ split into:
- edges inside the 0-layer: $E(S_0)$,
- edges inside the 1-layer: $E(S_1)$,
- edges in the last coordinate: these connect $x0$ and $x1$, contributing exactly one edge iff $x\in S_0\cap S_1$.
Hence
$$ E(S)=E(S_0)+E(S_1)+|S_0\cap S_1|. $$
Step 3: Induction hypothesis
Assume for $m-1$ that for all $T\subseteq Q_{m-1}$,
$$ E(T)\le f(|T|). $$
Apply this to $S_0,S_1$:
$$ E(S)\le f(|S_0|)+f(|S_1|)+|S_0\cap S_1|. $$
Also
$$ |S_0\cap S_1|\le \min(|S_0|,|S_1|). $$
So
$$ E(S)\le f(a)+f(b)+\min(a,b), \quad a=|S_0|,\ b=|S_1|,\ a+b=n. $$
Step 4: Maximizing the bound
Assume $a\ge b$. Then $\min(a,b)=b$, so
$$ E(S)\le f(a)+f(b)+b. $$
We compare two cases:
- If we move one element from $S_1$ to $S_0$, then $a\to a+1$, $b\to b-1$.
- The change in the upper bound is
$$ \Delta = f(a+1)-f(a) + f(b-1)-f(b) - 1. $$
Now observe from part (a) that $f(k)=\sum_{i=0}^{k-1}\nu(i)$, so
$$ f(k+1)-f(k)=\nu(k). $$
Hence
$$ \Delta = \nu(a) - \nu(b-1) - 1 \le 0, $$
since $\nu(x)\le m-1$ and the structure of binary increments ensures the imbalance cannot increase the expression. Thus shifting mass toward one side does not decrease the bound.
Iterating this balancing shows the maximum occurs when all elements are concentrated in one side as much as possible, i.e.
$$ (a,b) = (n,0)\quad \text{or recursively structured splits}. $$
This forces the canonical recursive construction: fill the 0-layer first, then the 1-layer, and within each layer repeat.
This is exactly the ordering of integers by binary representation (lexicographic order of bit strings), i.e. the set
$$ {0,1,\dots,n-1}. $$
Step 5: Achieving equality
For $S={0,1,\dots,n-1}$, we already computed in part (a) that
$$ E(S)=f(n). $$
Since every $S$ satisfies $E(S)\le f(n)$, this is optimal.
Conclusion
- The initial segment ${0,1,\dots,n-1}$ has exactly
$$ f(n)=\sum_{k=0}^{n-1}\nu(k) $$
edges.
- It satisfies
$$ f(n)\le \frac{n\lfloor \log_2 n\rfloor}{2}. $$
- Every induced $n$-vertex subgraph of the hypercube has at most $f(n)$ edges, with equality only for the initial segment construction.
$$ \boxed{} $$