Search

The Online Encyclopedia and Dictionary

 
     
 

Encyclopedia

Dictionary

Quotes

 

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 n\geq2r, and A is a family of subsets of {1,2,...,n}, such that each subset is of size r, and each pair of subsets intersects, then the maximum number of sets that can be in A is given by the binomial coefficient

{n-1} \choose {r-1}.

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 r, 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 r can be increased to size r to make the above statement apply.

Proof

The original proof of 1961 used induction on n. In 1972, Gyula Katona gave the following short and beautiful proof using double counting.

Suppose we have some such set A. Arrange the elements of {1,2,...,n} in any cyclic order, and inquire how many sets from A can form intervals within this cyclic order. For example if n = 8 and r = 3, we could arrange the numbers 1,...,8 as

[3,1,5,4,2,7,6,8]

and intervals would be

{1,3,5},{1,4,5},{2,4,5},{2,4,7},{2,6,7},{6,7,8},{3,6,8},{1,3,8}.

(Key step) At most r of these intervals can be in A. If

(a1,a2,...,ar)

is one of these intervals in A then for every i, there is at most one interval in A which separates ai from ai + 1, i.e. contains precisely one of ai and ai + 1. (If there were two, they would be disjoint, since n\geq2r.) Furthermore, if there are r intervals in A, then they must contain some element in common.

There are (n - 1)! cyclic orders, and each set from A is an interval in precisely r!(n - r)! of them. Therefore the average number of intervals that A has in a random cyclic order must be

\frac{|A|\cdot r!(n-r)!}{(n-1)!}\leq r.

Rearranging the inequality, we get

|A|\leq\frac{r(n-1)!}{r!(n-r)!}=\frac{(n-1)!}{(r-1)!(n-r)!}={n-1\choose r-1},

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.
Last updated: 06-06-2005 07:55:15
The contents of this article are licensed from Wikipedia.org under the GNU Free Documentation License. How to see transparent copy