= Solution
The \b[<Kruskal-Katona theorem>] states that a <colexicographic initial segment> minimizes the <lower shadow> of a <uniform set family> of prescribed size. Its numerical form is as follows. For $m>0$, write the unique <combinatorial number system> expansion
$$
m=\binom{a_r}r+\binom{a_{r-1}}{r-1}+\cdots+\binom{a_s}s,\qquad a_r>a_{r-1}>\cdots>a_s\geq s\geq1.
$$
Every $\mathcal F\subseteq[n]^{(r)}$ of size $m$ satisfies
$$
\boxed{|\partial\mathcal F|\geq\binom{a_r}{r-1}+\binom{a_{r-1}}{r-2}+\cdots+\binom{a_s}{s-1}}.
$$
The empty family has empty <lower shadow>. Equality is attained by the first $m$ $r$-sets in <colexicographic order>, where the largest differing element belongs to the later set. Iterating the <Kruskal-Katona theorem> shows that the same <colexicographic initial segment> minimizes every <iterated lower shadow>.
For $1\leq r<n/2$, the \b[<Erdős-Ko-Rado theorem>] gives
$$
\boxed{|\mathcal F|\leq\binom{n-1}{r-1}}
$$
for an <intersecting family> $\mathcal F\subseteq[n]^{(r)}$. All $r$-sets containing one prescribed point show that the bound is sharp.
For the proof from the <Kruskal-Katona theorem>, put $k=n-r$ and form the complement family $\mathcal G=\{[n]\setminus A:A\in\mathcal F\}\subseteq[n]^{(k)}$. Let $\mathcal S$ be its rank-$r$ <iterated lower shadow>. No member $B\in\mathcal F$ belongs to $\mathcal S$: containment in $[n]\setminus A$ would give $A\cap B=\varnothing$, impossible for an <intersecting family> of nonempty sets. Hence
$$
|\mathcal F|+|\mathcal S|\leq\binom nr.
$$
Suppose $|\mathcal F|>\binom{n-1}{r-1}=\binom{n-1}k$. The first $\binom{n-1}k$ members of the <colexicographic order> are all $k$-sets of $[n-1]$. Their rank-$r$ <iterated lower shadow> is all $r$-sets of $[n-1]$, since $r<k$. The next $k$-set contains $n$ and has an $r$-subset containing $n$, so taking even one more member strictly enlarges that <iterated lower shadow>. By the iterated <Kruskal-Katona theorem>, $|\mathcal S|>\binom{n-1}r$. Together with $|\mathcal F|>\binom{n-1}{r-1}$ this contradicts <Pascal's identity> and the preceding inequality. This proves the <Erdős-Ko-Rado theorem>.
For the <Katona circle method> proof, fix a <cyclic ordering> of $[n]$. A <cyclic interval> of length $r$ is specified by its final position. If no such interval belongs to $\mathcal F$, the bound below is automatic. Otherwise rotate one selected interval so that it ends at position $n$, and thus occupies positions $n-r+1,\ldots,n$. Intervals ending at positions $r,\ldots,n-r$ are disjoint from it and cannot be selected. Among the remaining endpoints, pair $j$ with $n-r+j$ for $1\leq j\leq r-1$. The corresponding intervals are disjoint when $n\geq2r$, so at most one interval per pair is selected. Together with the interval ending at $n$, this gives the <cyclic interval intersection bound> of $r$ selected intervals.
Choose a uniformly random <permutation> and read its positions cyclically. A fixed $r$-set is a <cyclic interval> with probability $n/\binom nr$: each cyclic position gives a uniformly distributed $r$-set, and for $r<n$ the $n$ intervals are distinct. Summing over $\mathcal F$, the <expected value> of the number of selected intervals is $n|\mathcal F|/\binom nr$. The <cyclic interval intersection bound> makes this at most $r$, giving $|\mathcal F|\leq(r/n)\binom nr=\binom{n-1}{r-1}$.
Finally apply the <Katona circle method> to an arbitrary <antichain> $\mathcal A$. If it contains $\varnothing$ or $[n]$, it has exactly one member and the <LYM inequality> holds with equality. Otherwise all its members have sizes $1,\ldots,n-1$. In a fixed <cyclic ordering>, the <cyclic intervals> sharing a final position form a nested chain as their lengths increase. At most one of them can belong to the <antichain>. Summing over the $n$ final positions proves the <cyclic interval antichain bound> of $n$ intervals. Taking the <expected value> over a uniformly random <permutation> gives
$$
n\sum_{r=1}^{n-1}\frac{|\mathcal A\cap[n]^{(r)}|}{\binom nr}\leq n.
$$
After division by $n$, this is \b[the <LYM inequality> proved by cyclic intervals]. The case $n=0$ consists only of the empty set and is immediate.
Back to article page
