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

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

(a_1,a_2,...,a_r)

is one of these intervals in

A

then for every

i

, there is at most one interval in

A

which separates

a_i

from

a_{i+1}

, i.e. contains precisely one of

a_i

and

a_{i+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.

Erdos-ko-rado Theorem

Proof

Further reading