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.
Further reading:
- P. Erdős, C. Ko, R. Rado, Intersection theorems for systems of finite sets, Quart. J. Math. Oxford Set. 2 12 (1961), 313-320. 19
