The Erdos-Ko-Rado Theorem

Combinatorics Seminar
Monday, October 20, 2008 - 11:05
1.5 hours (actually 80 minutes)
Skiles 255
University of Waterloo
In its simplest form, the Erdos-Ko-Rado theorem tells us that if we have a family F of subsets of size k from set of size v such that any two sets in the family have at least one point in common, then |F|<=(v-1)\choose(k-1) and, if equality holds, then F consists of all k-subsets that contain a given element of the underlying set. This theorem can also be viewed as a result in graph theory, and from this viewpoint it has many generalizations. I will outline how it can be proved using linear algebra, and then discuss how this approach can be applied in other cases.