Please use this identifier to cite or link to this item:
https://www.um.edu.mt/library/oar/handle/123456789/75659
Title: | The Hilton-Spencer cycle theorems via Katona's shadow intersection theorem |
Authors: | Borg, Peter Feghali, Carl |
Keywords: | Mathematics Logic, Symbolic and mathematical Set theory Hypergraphs |
Issue Date: | 2023 |
Publisher: | Uniwersytet Zielonogorski |
Citation: | Borg, P., & Feghali, C. (2023). The Hilton-Spencer cycle theorems via Katona's shadow intersection theorem. Discussiones Mathematicae Graph Theory, 43, 277-286. |
Abstract: | A family A of sets is said to be intersecting if every two sets in A intersect. An intersecting family is said to be \emph{trivial} it 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(ω(1Ck1),…,ω(sCks))≥2k∗+1, then G is r-EKR. They had shown that the same holds if ∗C is replaced by a path and the condition on the clique numbers is relaxed to min(ω(1Ck1),…,ω(sCks))≥k∗+1. We use the classical Shadow Intersection Theorem of Katona to obtain a short proof of each result for the case where the inequality for the minimum clique number is strict. |
URI: | https://www.um.edu.mt/library/oar/handle/123456789/75659 |
Appears in Collections: | Scholarly Works - FacSciMat |
Files in This Item:
File | Size | Format | |
---|---|---|---|
The_Hilton_Spencer_cycle_theorems_via_Katonas_shadow_intersection_theorem_2023.pdf Restricted Access | 137.72 kB | Adobe PDF | View/Open Request a copy |
Items in OAR@UM are protected by copyright, with all rights reserved, unless otherwise indicated.