Geodesic
The Hilton-Spencer cycle theorems via Katona's shadow intersection theorem
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 1, pp. 277-286 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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.
Keywords: cycle, independent set, intersecting family, Erd\H{o}s-Ko-Rado theorem, Hilton-Spencer theorem, Katona's shadow intersection theorem 
@article{DMGT_2023_43_1_a17,
     author = {Borg, Peter and Feghali, Carl},
     title = {The {Hilton-Spencer} cycle theorems via {Katona's} shadow intersection theorem},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {277--286},
     year = {2023},
     volume = {43},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_1_a17/}
}
TY  - JOUR
AU  - Borg, Peter
AU  - Feghali, Carl
TI  - The Hilton-Spencer cycle theorems via Katona's shadow intersection theorem
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 277
EP  - 286
VL  - 43
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_1_a17/
LA  - en
ID  - DMGT_2023_43_1_a17
ER  - 
%0 Journal Article
%A Borg, Peter
%A Feghali, Carl
%T The Hilton-Spencer cycle theorems via Katona's shadow intersection theorem
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 277-286
%V 43
%N 1
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_1_a17/
%G en
%F DMGT_2023_43_1_a17
Borg, Peter; Feghali, Carl. The Hilton-Spencer cycle theorems via Katona's shadow intersection theorem. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 1, pp. 277-286. http://geodesic.mathdoc.fr/item/DMGT_2023_43_1_a17/

[1] R. Ahlswede and L.H. Khachatrian, The complete intersection theorem for systems of finite sets, European J. Combin. 18 (1997) 125–136. https://doi.org/10.1006/eujc.1995.0092

[2] P. Borg, Extremal t-intersecting sub-families of hereditary families, J. Lond. Math. Soc. 79 (2009) 167–185. https://doi.org/10.1112/jlms/jdn062

[3] P. Borg, Intersecting families, cross-intersecting families, and a proof of a conjecture of Feghali, Johnson and Thomas, Discrete Math. 341 (2018) 1331–1335. https://doi.org/10.1016/j.disc.2018.02.004

[4] P. Borg, Intersecting families of sets and permutations: a survey, Int. J. Math. Game Theory Algebra 21 (2012) 543–559.

[5] P. Borg, On t-intersecting families of signed sets and permutations, Discrete Math. 309 (2009) 3310–3317. https://doi.org/10.1016/j.disc.2008.09.039

[6] P. Borg, The maximum product of sizes of cross-intersecting families, Discrete Math. 340 (2017) 2307–2317. https://doi.org/10.1016/j.disc.2017.04.019

[7] P. Borg and F. Holroyd, The Erdős-Ko-Rado properties of set systems defined by double partitions, Discrete Math. 309 (2009) 4754–4761. https://doi.org/10.1016/j.disc.2008.05.052

[8] P. Borg and F. Holroyd, The Erdős-Ko-Rado property of various graphs containing singletons, Discrete Math. 309 (2009) 2877–2885. https://doi.org/10.1016/j.disc.2008.07.021

[9] D.E. Daykin, Erdős-Ko-Rado from Kruskal-Katona, J. Combin. Theory Ser. A 17 (1974) 254–255. https://doi.org/10.1016/0097-3165(74)90013-2

[10] M. Deza and P. Frankl, The Erdős-Ko-Rado theorem–-22 years later, SIAM J. Algebraic Discrete Methods 4 (1983) 419–431. https://doi.org/10.1137/0604042

[11] P. Erdős, C. Ko and R. Rado, Intersection theorems for systems of finite sets, Q. J. Math. 12 (1961) 313–320. https://doi.org/10.1093/qmath/12.1.313

[12] C. Feghali, M. Johnson and D. Thomas, Erdős-Ko-Rado theorems for a family of trees, Discrete Appl. Math. 236 (2018) 464–471. https://doi.org/10.1016/j.dam.2017.10.009

[13] P. Frankl, Extremal set systems, in: Handbook of Combinatorics, 2, R.L. Graham, M. Grötschel and L. Lovász (Ed(s)), (Elsevier, Amsterdam 1995) 1293–1329.

[14] P. Frankl, The Erdős-Ko-Rado Theorem is true for n=ckt, in: Proc. Fifth Hung. Comb. Coll., (North-Holland, Amsterdam 1978) 365–375.

[15] P. Frankl, The shifting technique in extremal set theory, in: Surveys in Combinatorics, C. Whitehead (Ed(s)), (Cambridge Univ. Press, London/New York 1987) 81–110.

[16] P. Frankl and Z. Füredi, A new short proof of the EKR theorem, J. Combin. Theory Ser. A 119 (2012) 1388–1390. https://doi.org/10.1016/j.jcta.2012.03.012

[17] P. Frankl and N. Tokushige, Invitation to intersection problems for finite sets, J. Combin. Theory Ser. A 144 (2016) 157–211. https://doi.org/10.1016/j.jcta.2016.06.017

[18] A.J.W. Hilton, F.C. Holroyd and C.L. Spencer, King Arthur and his knights with two round tables, Q. J. Math. 62 (2011) 625–635. https://doi.org/10.1093/qmath/haq005

[19] A.J.W. Hilton and C.L. Spencer, A graph-theoretical generalisation of Berge's analogue of the Erdős-Ko-Rado theorem, in: Trends in Graph Theory, (Birkhauser Verlag, Basel, Switzerland 2006) 225–242.

[20] A.J.W. Hilton and C.L. Spencer, A generalization of Talbot's theorem about King Arthur and his knights of the round table, J. Combin. Theory Ser. A 116 (2009) 1023–1033. https://doi.org/10.1016/j.jcta.2009.02.001

[21] F. Holroyd, C. Spencer and J. Talbot, Compression and Erdős-Ko-Rado graphs, Discrete Math. 293 (2005) 155–164. https://doi.org/10.1016/j.disc.2004.08.041

[22] F. Holroyd and J. Talbot, Graphs with the Erdős-Ko-Rado property, Discrete Math. 293 (2005) 165–176. https://doi.org/10.1016/j.disc.2004.08.028

[23] G. Hurlbert and V. Kamat, Erdős-Ko-Rado theorems for chordal graphs and trees, J. Combin. Theory Ser. A 118 (2011) 829–841. https://doi.org/10.1016/j.jcta.2010.11.017

[24] G. Hurlbert and V. Kamat, New injective proofs of the Erdős-Ko-Rado and Hilton-Milner theorems, Discrete Math. 341 (2018) 1749–1754. https://doi.org/10.1016/j.disc.2018.03.010

[25] G.O.H. Katona, A simple proof of the Erdős-Chao Ko-Rado theorem, J. Combin. Theory Ser. B 13 (1972) 183–184. https://doi.org/10.1016/0095-8956(72)90054-8

[26] G.O.H. Katona, A theorem of finite sets, in: Theory of Graphs, Proc. Colloq., (Tihany, Akadémiai Kiadó 1968) 187–207.

[27] G.O.H. Katona, Intersection theorems for systems of finite sets, Acta Math. Acad. Sci. Hungar. 15 (1964) 329–337. https://doi.org/10.1007/BF01897141

[28] J.B. Kruskal, The number of simplices in a complex, in: Mathematical Optimization Techniques, (University of California Press, Berkeley, California 1963) 251–278.

[29] J. Talbot, Intersecting families of separated sets, J. London Math. Soc. 68 (2003) 37–51. https://doi.org/10.1112/S0024610703004356

[30] R.M. Wilson, The exact bound in the Erdős-Ko-Rado theorem, Combinatorica 4 (1984) 247–257. https://doi.org/10.1007/BF02579226

[31] R. Woodroofe, Erdős-Ko-Rado theorems for simplicial complexes, J. Combin. Theory Ser. A 118 (2011) 1218–1227. https://doi.org/10.1016/j.jcta.2010.11.022