2019/10/19 by Feghali, Carl, Hurlbert, Glenn, Kamat, Vikram
#05D05 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1910.08849
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 Bollobás and Leader. Our main approach is a novel probabilistic extension of Katona's elegant cycle method, which might be of independent interest.