 Solution

Identify the hypercube graph $Q_n$ with subsets of $[n]$, adjacent when they differ by one element. Write $N(\mathcal{F})$ for a family's closed vertex neighbourhood. The simplicial order on the discrete cube orders first by size and then, within a rank, by lexicographic order: the least element of a symmetric difference belongs to the earlier set. The Harper theorem says that if $I$ is the initial simplicial segment with $|I|=|\mathcal{F}|$, thenEquivalently this minimizes the external vertex boundary at fixed cardinality. This is the vertex-isoperimetric assertion, distinct from the edge version in Question 3.

Here is the deduction of Kruskal-Katona theorem. For a family $\mathcal{B}\subseteq [n{]}^{(k)}$, adjoin every lower rank and set $\mathcal{D}=[n{]}^{(<k)}\cup \mathcal{B}$. For $k\ge 1$,The corresponding simplicial initial segment is $[n{]}^{(<k)}\cup L$, where $L$ is the rank-$k$ lexicographic initial segment of size $|\mathcal{B}|$. Canceling the common lower-rank count in Harper's inequality gives $|\nabla \mathcal{B}|\ge |\nabla L|$. The rank-zero case is immediate by considering its two possible families.

To turn upper shadows into lower shadows, let $\rho (i)=n+1-i$ and $T(B)=\rho ([n]\setminus B)$. This bijection reverses inclusion and changes rank $k$ to $n-k$. If $B$ precedes $C$ in lex order, the largest element of $T(B)△T(C)$ belongs to $T(C)$, so $T(B)$ precedes $T(C)$ in colexicographic order. Also $T(\nabla \mathcal{B})=\partial (T\mathcal{B})$. Hence applying the upper-shadow conclusion to the transformed family proveswhere $C$ is the colex initial segment of the same size and rank as $\mathcal{A}$. This is the Kruskal-Katona lower-shadow theorem. A colex segment's shadow is itself a colex segment: split its sets by their largest element, giving a full initial block of the preceding ground set followed by an initial block with the new largest element. The same description holds one rank lower. Iteration therefore shows that colex segments minimize shadows at every lower rank. This proves the Harper theorem implies the Kruskal-Katona theorem deduction, including the necessary complement and coordinate reversal.

The Erdős-Ko-Rado theorem states that for $1\le r\le n/2$, every intersecting family $\mathcal{A}\subseteq [n{]}^{(r)}$ satisfiesThe family of all $r$-sets containing a fixed point attains the bound. We use the standard convention of positive ranks here.

For the first proof, let $\mathcal{B}$ be the complements of members of $\mathcal{A}$, at rank $k=n-r\ge r$, and let $\mathcal{S}$ be its rank-$r$ lower shadow. It is disjoint from $\mathcal{A}$, since $A\subseteq [n]\setminus A^{\prime }$ would make two family members disjoint. Suppose $|\mathcal{A}|>\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)$. The colex rank-$k$ segment of that size contains every $k$-set on $[n-1]$ and at least one set containing $n$. Its rank-$r$ shadow therefore contains all $\left(\genfrac{}{}{0ex}{}{n-1}{r}\right)$ old $r$-sets and at least one new $r$-set containing $n$. The iterated Kruskal-Katona bound givesThen $|\mathcal{A}|+|\mathcal{S}|>\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)+\left(\genfrac{}{}{0ex}{}{n-1}{r}\right)=\left(\genfrac{}{}{0ex}{}{n}{r}\right)$, impossible for disjoint subfamilies of rank $r$. This proves the Erdős-Ko-Rado theorem from shadows.

For the second proof use the Katona circle method. In any cyclic ordering of the $n$ points, an intersecting collection of length-$r$ intervals has at most $r$ members. To prove this, rotate one selected interval to end at position $n$, so it occupies $n-r+1,\dots ,n$. Intervals ending at $r,\dots ,n-r$ miss it and cannot be selected. Among the remaining endpoints other than $n$, pair $j$ with $j+n-r$ for $1\le j\le r-1$. The two intervals in each pair are disjoint because $n\ge 2r$, so at most one can be selected. Including the fixed interval gives at most $1+(r-1)=r$.

Now count pairs consisting of a family member and a permutation in which it is a cyclic interval. A fixed $r$-set has $nr!(n-r)!$ such permutations: choose its final position, its internal order, and the order of the remaining points. Each of the $n!$ permutations contributes at most $r$ family intervals by the proved cyclic interval intersection bound. ThusThis is the required cyclic-ordering proof, with its interval lemma established explicitly.