Abstrakt
A family of sets is intersecting if any two sets in the family intersect. Given a graph G and an integer r >= 1, let I-(r)(G) denote the family of independent sets of size r of G.
For a vertex v of G, the family of independent sets of size r that contain v is called an r-star. Then G is said to be r-EKR if no intersecting subfamily of I-(r)(G) is bigger than the largest r-star.
Let n be a positive integer, and let G consist of the disjoint union of n paths each of length 2. We prove that if 1 <= r <= n/2, then G is r-EKR.
This affirms a longstanding conjecture of Holroyd and Talbot for this class of graphs and can be seen as an analogue of a well-known theorem on signed sets, proved using different methods, by Deza and Frankl and by Bollobas and Leader. Our main approach is a novel probabilistic extension of Katona's elegant cycle method, which might be of independent interest. (c) 2020 Elsevier B.V.
All rights reserved.