Abstract
A set system F is said to be pairwise-intersecting if, for every pair of its members A and B in F, the intersection of A and B is non-empty. What is the largest cardinality of a family of pairwise-intersecting sets? A 1961 result of Erdős, Ko, and Rado answers this question if the sets all have the same small number of elements and are otherwise unrestricted. The upper bound part of their result says that the maximum family of sufficiently small pairwise-intersecting objects is given by a family with a common intersection. The characterization part of their result says that under slightly stronger hypotheses, this is the only such family. Holroyd and Johnson asked at the 1997 British Combinatorial Conference about whether an analogue of EKR holds for independent sets in cyclic and similar graphs. Talbot showed the answer to be ‘yes’.
Later, Hurlbert and Kamat showed that the upper bound part of the EKR theorem holds for independent sets of a chordal graph with an isolated vertex. We showed that the characterization part holds for this family as well. Moreover, if sufficient isolated vertices are present, we can extend two more generalizations of the EKR theorem to independent sets of a chordal graph. These are a bound on cross-intersecting families and a stability result for pairwise-intersecting families due to Hilton and Milner.
This is a joint work with Russ Woodroofe.