1. The Hilton-Spencer Cycle Theorems Via Katona's Shadow Intersection Theorem.
- Author
-
Borg, Peter and Feghali, Carl
- Subjects
- *
SHADOWING theorem (Mathematics) , *INDEPENDENT sets - 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), and min (ω (C 1 k 1 ) , ... , ω (C s 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 (ω (C 1 k 1 ) , ... , ω (C s 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. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF