= Solution
The <Erdős-Ko-Rado theorem> asserts that, for $1\leq r<n/2$, every <intersecting family> $\mathcal A\subseteq\binom{[n]}r$ satisfies
$$
\boxed{|\mathcal A|\leq\binom{n-1}{r-1}.}
$$
The bound is attained by the <set family> of all $r$-subsets containing one prescribed point. Here <lexicographic order> means that $X<Y$ when the smallest element of their <symmetric difference> belongs to $X$.
The first $M=\binom{n-1}{r-1}$ members in <lexicographic order> are exactly those containing $1$. An initial segment longer than $M$ contains all of them and also the first member avoiding $1$, namely $B=\{2,\ldots,r+1\}$. There is an $r$-subset containing $1$ and disjoint from $B$: choose its other $r-1$ elements from $\{r+2,\ldots,n\}$, which has $n-r-1\geq r-1$ elements. Consequently any longer <lexicographic> initial segment fails to be an <intersecting family>. Thus preservation of the <intersection> property upon replacing a <set family> by the equally large <lexicographic> initial segment proves the displayed bound.
Here is a direct <UV-compression> proof of that preservation statement. For disjoint nonempty <sets> $U,V$ with $|U|=|V|$ and $\min U<\min V$, an eligible member $A$ contains $V$ and misses $U$; its proposed image is $A'=(A\setminus V)\cup U$. The <UV-compression> moves $A$ to $A'$ only if $A'$ is not already present. Each eligible pair is either kept as a pair or moved from its later to its earlier member, so this operation preserves cardinality and uniformity and strictly decreases the sum of <lexicographic order> positions whenever it changes the <set family>.
The essential <intersection-preserving lexicographic UV-compression> lemma is that this operation preserves an <intersecting family> whenever all smaller lexicographically improving <UV-compressions> already leave that <set family> unchanged. Suppose instead that the compressed <set family> has disjoint members. At least one, say $A'$, must be newly moved. Both newly moved members would contain $U$, so the other, $B$, is a retained old member. Write $A=(A'\setminus U)\cup V$ for the old preimage. Since $A'\cap B=\varnothing$, we have $B\cap U=\varnothing$ and $(A\setminus V)\cap B=\varnothing$. Old intersectingness forces
$$
V'=V\cap B\ne\varnothing.
$$
If $V'=V$, then $B$ was eligible for the same <UV-compression>. Since it was retained, $B'=(B\setminus V)\cup U$ was already present. But $A\cap B'=\varnothing$, contradicting old intersectingness.
Otherwise $0<|V'|<|V|$. Choose $U'\subset U$ with $|U'|=|V'|$ and $\min U\in U'$. This is a smaller improving pair, since $\min U'=\min U<\min V\leq\min V'$. The old member $A$ is eligible for its <UV-compression>. The assumed stability therefore forces $A''=(A\setminus V')\cup U'$ to be present already. Yet its portion outside $V$ misses $B$, its remaining portion $V\setminus V'$ misses $B$, and $U'$ misses $B$. Thus $A''\cap B=\varnothing$, the required contradiction. This proves the lemma, including the size-one case, where only the first alternative can arise.
Starting with $\mathcal A$, repeatedly choose a changing improving <UV-compression> with the smallest possible $|U|$. The lemma applies at each step because every smaller improving <UV-compression> is then unchanged. Thus every intermediate <set family> is intersecting. The strictly decreasing nonnegative integer sum of <lexicographic order> positions ensures termination. If the terminal <set family> were not an initial segment, there would be a missing $X$ earlier than a present $Y$. Taking $U=X\setminus Y$ and $V=Y\setminus X$ gives equally sized nonempty disjoint <sets> with $\min U<\min V$, and moves $Y$ to the missing $X$. That contradicts termination. The terminal <set family> is therefore exactly the equally large <lexicographic> initial segment, and it is intersecting. \b[This proves the required lexicographic statement directly, and hence the <Erdős-Ko-Rado theorem>.]
Back to article page
