Main Page | See live article | Alphabetical index

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:

This is a standard combinatorial double counting argument.

Further reading:

See also: combinatorics, mathematics, theorem