Erd�s-Ko-Rado theorem

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

: > 2,

and is a family of subsets of of size , each pair of which intersects, then the maximum 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.