The Hilton-Spencer Cycle Theorems Via Katona’s Shadow Intersection Theorem

Abstract

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 1C, . . ., sC raised to the powers k1, . . ., ks, respectively, 1 ≤ r ≤ α (G), andmin(ω(C1k1),…,ω(Csks))≥ω(Ck),\min \left( {\omega \left( {{}_1{C^{k1}}} \right), \ldots ,\omega \left( {{}_s{C^{ks}}} \right)} \right) \ge \omega \left( {{C^k}} \right), 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(ω(C1k1),…,ω(Csks))≥ω(Pk),\min \left( {\omega \left( {{}_1{C^{k1}}} \right), \ldots ,\omega \left( {{}_s{C^{ks}}} \right)} \right) \ge \omega \left( {{P^k}} \right),

Keywords

• cycle
• independent set
• intersecting family
• erdős-ko-rado theorem
• hilton-spencer theorem
• katona’s shadow intersection theorem
• 05d05
• 05c35
• 05c38
• 05c69