A Survey of the Holroyd-Talbot Conjecture

Abstract

A family of sets is intersecting if every pair of its members has an element in common. Such a family of sets is called a star if some element is in every set of the family. Given a graph $G$, let $\mu (G)$ denote the size of the smallest maximal independent set of $G$. In 2005, Holroyd and Talbot conjectured the following generalization of the Erdős-Ko-Rado Theorem: for $1\le r\le \mu (G)/2$, there is a maximum size intersecting family of independent $r$-sets that is a star. In this paper we present the history of this conjecture and survey the results that have supported it over the last 20 years.

arXiv commentAdded references to Frankl's work on the best bound for EKR to hold, and to Frankl-Furedi's work on the Complete Intersection Theorem that predated Ahlswede-Khachatrian