1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

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

Published Online: 24 Nov 2020
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 14 Jan 2020
Accepted: 19 Sep 2020
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
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),

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

MSC 2010

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

[2] P. Borg, Extremal t-intersecting sub-families of hereditary families, J. Lond. Math. Soc. 79 (2009) 167–185. doi:10.1112/jlms/jdn06210.1112/jlms/jdn062Search in Google Scholar

[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. doi:10.1016/j.disc.2018.02.00410.1016/j.disc.2018.02.004Search in Google Scholar

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

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

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

[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. doi:10.1016/j.disc.2008.05.05210.1016/j.disc.2008.05.052Search in Google Scholar

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

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

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

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

[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. doi:10.1016/j.dam.2017.10.00910.1016/j.dam.2017.10.009Search in Google Scholar

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

[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.Search in Google Scholar

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

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

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

[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. doi:10.1093/qmath/haq00510.1093/qmath/haq005Search in Google Scholar

[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.10.1007/978-3-7643-7400-6_18Search in Google Scholar

[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. doi:10.1016/j.jcta.2009.02.00110.1016/j.jcta.2009.02.001Search in Google Scholar

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

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

[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. doi:10.1016/j.jcta.2010.11.01710.1016/j.jcta.2010.11.017Search in Google Scholar

[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. doi:10.1016/j.disc.2018.03.01010.1016/j.disc.2018.03.010Search in Google Scholar

[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. doi:10.1016/0095-8956(72)90054-810.1016/0095-8956(72)90054-8Search in Google Scholar

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

[27] G.O.H. Katona, Intersection theorems for systems of finite sets, Acta Math. Acad. Sci. Hungar. 15 (1964) 329–337. doi:10.1007/BF0189714110.1007/BF01897141Search in Google Scholar

[28] J.B. Kruskal, The number of simplices in a complex, in: Mathematical Optimization Techniques (University of California Press, Berkeley, California, 1963) 251–278.10.1525/9780520319875-014Search in Google Scholar

[29] J. Talbot, Intersecting families of separated sets, J. London Math. Soc. 68 (2003) 37–51. doi:10.1112/S002461070300435610.1112/S0024610703004356Search in Google Scholar

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

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

Recommended articles from Trend MD

Plan your remote conference with Sciendo