Article in volume
Authors:
Title:
The Hilton-Spencer cycle theorems via Katona's shadow intersection theorem
PDFSource:
Discussiones Mathematicae Graph Theory 43(1) (2023) 277-286
Received: 2020-01-14 , Revised: 2020-09-08 , Accepted: 2020-09-19 , Available online: 2020-10-12 , https://doi.org/10.7151/dmgt.2365
Abstract:
A family $\mathcal{A}$ of sets is said to be intersecting if every two sets in
$\mathcal{A}$ 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 $\alpha(G)$ and $\omega(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}, \dots, {_sC}$ raised to the powers $k_1, \dots, k_s$,
respectively, $1 \leq r \leq \alpha(G)$, and
$$
\min\left(\omega\big(_1C^{k_1}\big), \dots, \omega\big(_sC^{k_s}\big)\right)
\geq \omega\big(C^{k}\big),
$$
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\big(\omega\big(_1C^{k_1}\big), \dots, \omega\big(_sC^{k_s}\big)\big)
\geq \omega\big(P^{k}\big).
$$
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ős-Ko-Rado theorem, Hilton-Spencer theorem, Katona's shadow intersection theorem
References:
- 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 - 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 - 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 - P. Borg, Intersecting families of sets and permutations: a survey, Int. J. Math. Game Theory Algebra 21 (2012) 543–559.
- 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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.
- 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.
- 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.
- 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 - 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 - 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 - 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.
- 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 - 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 - 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 - 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 - 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 - 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 - G.O.H. Katona, A theorem of finite sets, in: Theory of Graphs, Proc. Colloq., (Tihany, Akadémiai Kiadó 1968) 187–207.
- 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 - J.B. Kruskal, The number of simplices in a complex, in: Mathematical Optimization Techniques, (University of California Press, Berkeley, California 1963) 251–278.
- J. Talbot, Intersecting families of separated sets, J. London Math. Soc. 68 (2003) 37–51.
https://doi.org/10.1112/S0024610703004356 - R.M. Wilson, The exact bound in the Erdős-Ko-Rado theorem, Combinatorica 4 (1984) 247–257.
https://doi.org/10.1007/BF02579226 - 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
Close