Compression and Erdős–Ko–Rado graphs

AbstractFor a graph G and integer r⩾1 we denote the collection of independent r-sets of G by I(r)(G). If v∈V(G) then Iv(r)(G) is the collection of all independent r-sets containing v. A graph G, is said to be r-EKR, for r⩾1, iff no intersecting family A⊆I(r)(G) is larger than maxv∈V(G)|Iv(r)(G)|. There are various graphs that are known to have his property: the empty graph of order n⩾2r (this is the celebrated Erdős–Ko–Rado theorem), any disjoint union of at least r copies of Kt for t⩾2, and any cycle. In this paper we show how these results can be extended to other classes of graphs via a compression proof technique.In particular we extend a theorem of Berge (Hypergraph Seminar, Columbus, Ohio 1972, Springer, New York, 1974, pp. 13–20.), showing that any disjoint union of at least r complete graphs, each of order at least two, is r-EKR. We also show that paths are r-EKR for all r⩾1