Erd�s-Ko-Rado theorem

In combinatorial mathematics, the Erdős-Ko-Rado theorem of Paul Erdős, C. Ko and Richard Rado, states that if is larger than 2, and is a family of subsets of of size , each pair of which intersects, then the largest number of sets that can be in is given by the binomial coefficient . Furthermore if equality holds, there is some element of such that is the family of all -size subsets of containing .

Gyula Katona's proof is short and beautiful, and now follows:

Suppose we have some such set with at least sets in.
Now arrange the elements of in a cyclic order, and inquire how many sets from can form intervals within this cyclic order. For example if and , we could arrange them as and intervals would be .
(Key step) At most of these can be in . If is one of these intervals then for every , there is at most one interval which separates from , i.e. contains precisely one of and . Furthermore, if there are intervals in , then they must contain some element in common.
There are cyclic orders, and each set from is an interval in precisely of them. Therefore the average number of intervals in a random cyclic order must be
We must have equality, meaning that , and each cyclic order has exactly r intervals.
The result soon follows.

This is a standard combinatorial double counting argument.