Erdős–Ko–Rado theorem

Remarks

Katona's proof places $1, \ldots, n$ around a circle in a random order. An intersecting family contains at most $k$ of the $n$ arcs of $k$ consecutive points, when $n \ge 2k$. Each $k$-set is such an arc with probability $n / \binom{n}{k}$, so averaging gives $|\mathcal{F}| \cdot n / \binom{n}{k} \le k$, that is, $|\mathcal{F}| \le \frac{k}{n} \binom{n}{k} = \binom{n-1}{k-1}$.

Example: the star of all $k$-sets that contain the element $1$ is intersecting and has exactly $\binom{n-1}{k-1}$ members. For $n > 2k$ the stars are the only families that attain the bound. For $n = 2k$ there are others, for example one set from each complementary pair. The hypothesis $n \ge 2k$ is necessary: if $k < n < 2k$, any two $k$-subsets intersect, and there are $\binom{n}{k} = \frac{n}{k} \binom{n-1}{k-1} > \binom{n-1}{k-1}$ of them.

Going deeper

For a student

The theorem is a basic result of extremal set theory, with many extensions: to $t$-intersecting families, to vector spaces, to permutations, and to other structures. Its circle proof is an averaging argument of the same kind as the proof of the LYM inequality. The Kruskal–Katona theorem gives another proof. In graph language it gives the independence number of the Kneser graph.