Chris Godsil (Waterloo)

Erdös-Ko-Rado Theorems

Abstract for the Combinatorics Seminar
2008 May 12

The Erdös-Ko-Rado Theorem tells us that if F is a collection of k-subsets of V = {1,...,v} such that any members of F have at least one point in common, then

  1. |F| ≤ C(v-1, k-1).
  2. If equality holds, then F consists of all k-subsets of V that contain some given point i of V.
This is certainly one of the central results in combinatorics.

My aim in this talk is to introduce some of the many analogs of the EKR theorem, and to show how we can use linear algebra to prove them.

To the Combinatorics Seminar Web page.