The Erdos-Ko-Rado Theorem and Generalizations on Graphs

Combinatorics Seminar
Friday, April 14, 2017 - 15:05
1 hour (actually 50 minutes)
Skiles 005
Virginia Commonwealth University
The fundamental EKR theorem states that, when n≥2r, no pairwise intersecting family of r-subsets of {1,2,...,n} is larger than the family of all r-subsets that each contain some fixed x (star at x), and that a star is strictly largest when n>2r. We will discuss conjectures and theorems relating to a generalization to graphs, in which only independent sets of a graph are allowed. In joint work with Kamat, we give a new proof of EKR that is injective, and also provide results on a special class of trees called spiders.