The Hilton-Spencer cycle theorems via Katona's shadow intersection theorem

Borg, Peter  ; Feghali, Carl

Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 1, pp. 277-286

Résumé

A family 𝒜 of sets is said to be intersecting if every two sets in 𝒜 intersect. An intersecting family is said to be trivial if its sets have a common element. A graph G is said to be r-EKR if at least one of the largest intersecting families of independent r-element sets of G is trivial. Let α(G) and ω(G) denote the independence number and the clique number of G, respectively. Hilton and Spencer recently showed that if G is the vertex-disjoint union of a cycle C raised to the power k and s cycles _1 C , . . . , _s C raised to the powers k_1, . . . , k_s, respectively, 1 ≤ r ≤α(G), and min(ω(_1C^k_1), …, ω(_sC^k_s)) ≥ω(C^k), then G is r-EKR. They had shown that the same holds if C is replaced by a path P and the condition on the clique numbers is relaxed to min(ω(_1C^k_1), …, ω(_sC^k_s)) ≥ω(P^k). We use the classical Shadow Intersection Theorem of Katona to obtain a significantly shorter proof of each result for the case where the inequality for the minimum clique number is strict.

Détail

Keywords: cycle, independent set, intersecting family, Erd\H{o}s-Ko-Rado theorem, Hilton-Spencer theorem, Katona's shadow intersection theorem