### The Erdos-Ko-Rado Theorem

- Series
- Combinatorics Seminar
- Time
- Monday, October 20, 2008 - 11:05 for 1.5 hours (actually 80 minutes)
- Location
- Skiles 255
- Speaker
- Chris Godsil – 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.