Erdos-Ko-Rado theorem
|
|
In combinatorial mathematics, the Erdős-Ko-Rado theorem of Paul Erdős, Chao Ko, and Richard Rado is the following. If <math>n\geq2r<math>, and <math>A<math> is a family of subsets of <math>\{1,2,...,n\}<math>, such that each subset is of size <math>r<math>, and each pair of subsets intersects, then the maximum number of sets that can be in <math>A<math> is given by the binomial coefficient
- <math>{n-1} \choose {r-1}<math>.
The theorem was originally stated in 1961 in an apparently more general form. The subsets in question were only required to be size at most <math>r<math>, and with the additional requirement that no subset be contained in any other. This statement is not actually more general: any subset that has size less than <math>r<math> can be increased to size <math>r<math> to make the above statement apply.
Proof
The original proof of 1961 used induction on <math>n<math>. In 1972, Gyula Katona gave the following short and beautiful proof using double counting.
Suppose we have some such set <math>A<math>. Arrange the elements of <math>\{1,2,...,n\}<math> in any cyclic order, and inquire how many sets from <math>A<math> can form intervals within this cyclic order. For example if <math>n=8<math> and <math>r=3<math>, we could arrange the numbers <math>1,...,8<math> as
- <math>[3,1,5,4,2,7,6,8]<math>
and intervals would be
- <math>\{1,3,5\},\{1,4,5\},\{2,4,5\},\{2,4,7\},\{2,6,7\},\{6,7,8\},\{3,6,8\},\{1,3,8\}<math>.
(Key step) At most <math>r<math> of these intervals can be in <math>A<math>. If
- <math>(a_1,a_2,...,a_r)<math>
is one of these intervals in <math>A<math> then for every <math>i<math>, there is at most one interval in <math>A<math> which separates <math>a_i<math> from <math>a_{i+1}<math>, i.e. contains precisely one of <math>a_i<math> and <math>a_{i+1}<math>. (If there were two, they would be disjoint, since <math>n\geq2r<math>.) Furthermore, if there are <math>r<math> intervals in <math>A<math>, then they must contain some element in common.
There are <math>(n-1)!<math> cyclic orders, and each set from <math>A<math> is an interval in precisely <math>r!(n-r)!<math> of them. Therefore the average number of intervals that <math>A<math> has in a random cyclic order must be
- <math>\frac{|A|\cdot r!(n-r)!}{(n-1)!}\leq r.<math>
Rearranging the inequality, we get
- <math>|A|\leq\frac{r(n-1)!}{r!(n-r)!}=\frac{(n-1)!}{(r-1)!(n-r)!}={n-1\choose r-1},<math>
establishing the theorem.
Further reading
- P. Erdős, C. Ko, R. Rado. Intersection theorems for systems of finite sets, Quarterly Journal of Mathematics, Oxford Series, series 2, volume 12 (1961), pages 313--320.
- G. O. H. Katona. A simple proof of the Erdös-Chao Ko-Rado theorem. Journal of Combinatorial Theory, Series B, volume 13 (1972), pages 183--184.