|
The Erdos-Ko-Rado theorem says that if $\mathcal{F}$ is a collection of
$k$-subsets of a set $V$ of size $v$ such that any two elements of
$\mathcal{F}$ have at least one point in common, then
$$
|\mathcal{F}| \le \binom{v-1}{k-1};
$$
further if this bound is tight then $\mathcal{F}$ consists of the
$k$-subsets that contain a given point from $V$. Thus this theorem
provides both a bound, and a characterization.
This theorem is a fundamental result in combinatorial set theory. The
bound is comparatively easy to obtain, and many proofs are known. The
characterization is harder to prove, but probably more useful. I will show
how it can be derived in a natural way by using a polytope. I will also
show how the same technology can be used to provide an analog of the
Erd\H{o}s-Ko-Rado theorem where $k$-subsets are replaced by permutations;
in this case the polytope used is a perfect matching polytope.
|