Science Fair Project Encyclopedia

Science Fair Project Encyclopedia Contents Page

Categories: Set families | Theorems | Proofs

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

(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.

All Science Fair Projects