= Solution
Identify the <Boolean hypercube> $Q_n$ with the subsets of $[n]$. For a family $\mathcal H$, write $N(\mathcal H)$ for its closed <vertex neighbourhood>, consisting of the family and all vertices at <Hamming distance> one from it. Order subsets first by increasing size and, within a fixed size, use <lexicographic order>: at the smallest coordinate on which they differ, the set containing that coordinate comes first. This is the <simplicial order on the discrete cube>. \b[Harper's theorem] states that if $I$ is its initial segment of size $|\mathcal H|$, then
$$
\boxed{|N(\mathcal H)|\geq|N(I)|.}
$$
Thus simplicial initial segments minimize the <external vertex boundary> for each prescribed family size. The closed-neighbourhood and external-boundary formulations are equivalent because $|N(\mathcal H)\setminus\mathcal H|=|N(\mathcal H)|-|\mathcal H|$. No <edge boundary> is involved in this assertion.
We now give the deduction <Harper theorem implies the Kruskal-Katona theorem>, keeping track of the two different orders. For a family $\mathcal F$ of $r$-sets with $r\geq1$, adjoin every smaller set:
$$
\mathcal H=\bigcup_{j<r}\binom{[n]}j\ \cup\ \mathcal F.
$$
Its closed <vertex neighbourhood> is exactly
$$
N(\mathcal H)=\bigcup_{j\leq r}\binom{[n]}j\ \cup\ \nabla\mathcal F,
$$
where $\nabla\mathcal F$ is the <upper shadow>. Applying <Harper theorem> to $\mathcal H$ shows that, among $r$-uniform families of fixed size, the <lexicographic> <initial segment> minimizes the <upper shadow>: all the lower-level contributions to the two neighbourhood sizes are identical.
To convert this into a statement about the <lower shadow> of a $k$-uniform family $\mathcal G$, take $r=n-k$ and map each member $S$ to $R([n]\setminus S)$, where $R(i)=n+1-i$ reverses the ground-set coordinates. Complementation changes <lower shadows> to <upper shadows>, and the coordinate reversal preserves their sizes. Moreover, the resulting <lexicographic order> corresponds exactly to <colexicographic order> on the original $k$-sets: $S$ precedes $T$ in <colexicographic order> precisely when the largest element of $S\triangle T$ lies in $T$. After complementation and reversal, the smallest differing coordinate lies in the image of $S$, as required for the stated <lexicographic order>. Hence \b[a <colexicographic> <initial segment> minimizes the <lower shadow>], which is the <Kruskal-Katona theorem>. The cases $k=n$ and $k=0$ are immediate and need no adjoining construction.
For its usual numerical form, write the unique greedy <binomial representation>
$$
m=\binom{a_k}k+\binom{a_{k-1}}{k-1}+\cdots+\binom{a_t}t,\qquad a_k>a_{k-1}>\cdots>a_t\geq t\geq1.
$$
Then the <Kruskal-Katona theorem> says
$$
\boxed{|\partial\mathcal G|\geq\binom{a_k}{k-1}+\binom{a_{k-1}}{k-2}+\cdots+\binom{a_t}{t-1}\quad(|\mathcal G|=m).}
$$
Here is why the shadow of the <colexicographic> <initial segment> has exactly that size. Its first block consists of all $k$-sets in $[a_k]$. If any members remain, they have the form $\{a_k+1\}\cup T$, where $T$ runs through a <colexicographic> <initial segment> of $(k-1)$-sets. The <lower shadow> consists of all $(k-1)$-sets in $[a_k]$, together with $\{a_k+1\}$ adjoined to the <lower shadow> of that remainder. These two blocks are disjoint. Recursing gives precisely the displayed sum. For $m=0$, both the initial segment and its shadow are empty.
\b[The Erdős-Ko-Rado theorem] states that an <intersecting family> $\mathcal A\subseteq\binom{[n]}r$, with $1\leq r\leq n/2$, satisfies
$$
\boxed{|\mathcal A|\leq\binom{n-1}{r-1}.}
$$
The bound is attained by all $r$-sets containing one fixed element. For the proof <Erdős-Ko-Rado theorem from shadows>, take complements to obtain an $(n-r)$-uniform family $\mathcal B$ of the same size, and let $D$ be its rank-$r$ <lower shadow>. Every member of $D$ is disjoint from some member of $\mathcal A$, so $D\cap\mathcal A=\varnothing$. Iterating the <Kruskal-Katona theorem> bounds $|D|$ below by the rank-$r$ shadow of the <colexicographic> <initial segment> of size $|\mathcal B|$. This iteration is valid because <lower shadows> of <colexicographic> <initial segments> are again <colexicographic> <initial segments>, as the preceding block description shows.
If $|\mathcal A|>\binom{n-1}{r-1}=\binom{n-1}{n-r}$, that initial segment contains all $(n-r)$-sets in $[n-1]$ and at least one further set containing $n$. Since $r\leq n-r\leq n-1$, its rank-$r$ shadow contains every $r$-set in $[n-1]$ and at least one $r$-set containing $n$. Thus $|D|>\binom{n-1}r$, implying
$$
|D|+|\mathcal A|>\binom{n-1}r+\binom{n-1}{r-1}=\binom nr,
$$
contrary to their disjointness. This proves the bound. If $r>n/2$, all $r$-sets intersect and the trivial maximum is instead $\binom nr$.
For an <intersecting family in a product alphabet>, label the alphabet by $\mathbb Z/k\mathbb Z$. Partition the words into the classes
$$
\{(x_1+t,\ldots,x_n+t):t\in\mathbb Z/k\mathbb Z\}.
$$
Each class has $k$ words, and any two distinct words in it disagree in every coordinate. An intersecting family therefore contains at most one word per class. There are $k^{n-1}$ classes, and fixing the first coordinate gives an intersecting family of that size. Consequently \b[the exact maximum is]
$$
\boxed{k^{n-1}\qquad(n\geq1,\ k\geq1).}
$$
For $k=1$ this just says that the single word may be included.
Finally, for a <weakly intersecting family in a product alphabet>, associate to each word its support $S(x)=\{i:x_i>1\}$. The occurring supports form an <intersecting family> of nonempty subsets, and the fibre over support $S$ has $(k-1)^{|S|}$ words. Put $w=k-1$. When $k\geq2$, $w\geq1$, and a support family can contain at most one of each complementary pair $S,[n]\setminus S$. For odd $n$, the larger support in each pair has size greater than $n/2$, so
$$
|\mathcal A|\leq\sum_{\{S,S^c\}}\max\{w^{|S|},w^{n-|S|}\}=\sum_{j>n/2}\binom nj(k-1)^j.
$$
All supports of size greater than $n/2$ are mutually intersecting, so taking every word over those supports achieves this bound. Thus \b[the required extremal family is the strict-majority support family], with size
$$
\boxed{\sum_{j=(n+1)/2}^n\binom nj(k-1)^j.}
$$
This is the <weighted intersecting family bound on an odd Boolean lattice>. For $k>2$, strict inequality between the complementary fibre weights forces this extremal family to be unique. For $k=2$, it is a largest family but need not be the only one; for example, all supports containing one fixed coordinate also attain the same size. For $k=1$, no word has a nonempty support, so the maximum is zero, again agreeing with the formula.
Back to article page
