Past exam of the mathematics course of the University of Cambridge / 2014 / iii / Paper 11 / 2 / i

The Erdős-Ko-Rado theorem states that for $1\le r\le n/2$, an intersecting family $\mathcal{F}$ of $r$-subsets of $[n]$ satisfiesThe bound is sharp: take all $r$-sets containing one fixed element.

Use the Katona circle method. In any cyclic ordering of $[n]$, the cyclic interval intersection bound permits at most $r$ members of $\mathcal{F}$ to appear as length-$r$ intervals. To see the bound directly, rotate a chosen interval so that it ends at $n$. Intervals ending at $r,\dots ,n-r$ miss it. Pair the remaining endpoints except $n$ as $(j,j+n-r)$, $1\le j\le r-1$; the two intervals in each pair are disjoint, so at most one is chosen. Including the fixed interval gives at most $r$.

There are $(n-1)!$ oriented cyclic orders. A fixed $r$-set appears consecutively in $r!(n-r)!$ of them: collapse it to a block, cyclically order that block with the other $n-r$ elements, and order its members internally. Double counting the compatible family-member/order pairs gives $|\mathcal{F}|r!(n-r)!\le r(n-1)!$, proving the theorem.