Document Zbl 1408.05132

The Katona cycle proof of the Erdős-Ko-Rado theorem and its possibilities. (English) Zbl 1408.05132

J. Algebr. Comb. 43, No. 4, 915-939 (2016).

Summary: In this paper we give a framework for applying Katona’s cycle proof of the Erdős-Ko-Rado theorem to other objects. We also show how this method can be realized as a result using homomorphisms of graphs.

Cited in 1 Document

MathOverflow Questions:

What is the independence number of hamming graph?

MSC:

05D05	Extremal set theory
05A05	Permutations, words, matrices

Keywords:

Katona’s cycle proof; Erdős-Ko-Rado theorem; graph homomorphism

Software:

MathOverflow

Cite Review PDF

Full Text: DOI

References:

[1]	Ahlswede, R., Khachatrian, L.H.: The complete intersection theorem for systems of finite sets. Eur. J. Comb. 18(2), 125-136 (1997) · Zbl 0869.05066 · doi:10.1006/eujc.1995.0092
[2]	Ahlswede, R., Khachatrian, L.H.: The diametric theorem in Hamming spaces-optimal anticodes. Adv. Appl. Math. 20(4), 429-449 (1998) · Zbl 0909.05044 · doi:10.1006/aama.1998.0588
[3]	Albertson, M.O., Collins, K.L.: Homomorphisms of \[33\]-chromatic graphs. Discrete Math. 54(2), 127-132 (1985) · Zbl 0572.05024 · doi:10.1016/0012-365X(85)90073-1
[4]	Berge, C.: Nombres de coloration de l’hypergraphe \[h\] h-parti complet. Lecture Notes Math. 411, 13-20 (1974) · Zbl 0295.05130 · doi:10.1007/BFb0066175
[5]	Bollobás, B., Leader, I.: An Erdős-Ko-Rado theorem for signed sets. Comput. Math. Appl. 34(11), 9-13 (1997) · Zbl 0901.05088 · doi:10.1016/S0898-1221(97)00215-0
[6]	Borg, P.: On \[t\] t-intersecting families of signed sets and permutations. Discrete Math. 309, 3310-3317 (2009) · Zbl 1216.05003 · doi:10.1016/j.disc.2008.09.039
[7]	Borg, P.: Cross-intersecting families of partial permutations. SIAM J. Discrete Math. 24, 600-608 (2010) · Zbl 1236.05199 · doi:10.1137/080731281
[8]	Borg, P.: A Hilton-Milner-type theorem and an intersection conjecture for signed sets. Discrete Math. 313(18), 1805-1815 (2013) · Zbl 1277.05158 · doi:10.1016/j.disc.2013.04.030
[9]	Borg, P., Leader, I.: Multiple cross-intersecting families of signed sets. J. Comb. Theory Ser. A 117(5), 583-588 (2010) · Zbl 1216.05163 · doi:10.1016/j.jcta.2009.11.010
[10]	Borg, P., Meagher, K.: Intersecting generalised permutations. Australas. J. Comb. 61, 147-155 (2015) · Zbl 1309.05005
[11]	Brouwer, A.E., Godsil, C.D., Koolen, J.H., Martin, W.J.: Width and dual width of subsets in polynomial association schemes. J. Comb. Theory Ser. A 102(2), 255-271 (2003) · Zbl 1018.05108 · doi:10.1016/S0097-3165(03)00006-2
[12]	Brunk, F., Huczynska, S.: Some Erdős-Ko-Rado theorems for injections. Eur. J. Comb. 31(3), 839-860 (2010) · Zbl 1226.05004 · doi:10.1016/j.ejc.2009.07.013
[13]	Cameron, P.J., Ku, C.Y.: Intersecting families of permutations. Eur. J. Comb. 24(7), 881-890 (2003) · Zbl 1026.05001 · doi:10.1016/S0195-6698(03)00078-7
[14]	Daykin, D.E.: Erdős-Ko-Rado from Kruskal-Katona. J. Comb. Theory Ser. A 17, 254-255 (1974) · Zbl 0287.05005 · doi:10.1016/0097-3165(74)90013-2
[15]	Deza, M., Frankl, P.: Erdős-Ko-Rado theorem-\[2222\] years later. SIAM J. Algebraic Discrete Methods 4(4), 419-431 (1983) · Zbl 0526.05001 · doi:10.1137/0604042
[16]	Dyck, A., Meagher, K.: An Erdős-Ko-Rado theorem for subset partitions. Involve 8(1), 119-127 (2015) · Zbl 1309.05176 · doi:10.2140/involve.2015.8.119
[17]	Engel, K.: An Erdős-Ko-Rado theorem for the subcubes of a cube. Combinatorica 4, 133-140 (1984) · Zbl 0557.05008 · doi:10.1007/BF02579213
[18]	Erdős, P., Faigle, U., Kern, W.: A group-theoretic setting for some intersecting sperner families. Comb. Probab. Comput. 1, 323-334 (1992) · Zbl 0793.05137 · doi:10.1017/S0963548300000377
[19]	Erdős, P., Ko, C., Rado, R.: Intersection theorems for systems of finite sets. Quart. J. Math. Oxford Ser. (2) 12, 313-320 (1961) · Zbl 0100.01902 · doi:10.1093/qmath/12.1.313
[20]	Frankl, P.: The Erdős-Ko-Rado theorem is true for \[n=ckt\] n=ckt. In: Combinatorics. Colloq. Math. Soc. János Bolyai, vol. 18, pp. 365-375. North-Holland, Amsterdam (1978) · Zbl 0401.05001
[21]	Frankl, P., Füredi, Z.: The Erdős-Ko-Rado theorem for integer sequences. SIAM J. Algebraic Discrete Methods 1(4), 376-381 (1980) · Zbl 0506.05001 · doi:10.1137/0601044
[22]	Frankl, P., Füredi, Z.: A new short proof of the EKR theorem. J. Comb. Theory Ser. A 119(6), 1388-1390 (2012) · Zbl 1244.05008 · doi:10.1016/j.jcta.2012.03.012
[23]	Frankl, P., Graham, R.L.: Old and new proofs of the Erdős-Ko-Rado theorem. Sichuan Daxue Xuebao 26, 11-122 (1989) · Zbl 0716.05039
[24]	Füredi, Z., Hwang, K-W., Weichsel, P.M.: A proof and generalizations of the Erdős-Ko-Rado theorem using the method of linearly independent polynomials. In: Topics in Discrete Mathematics, vol. 26, pp. 215-224. Springer, Berlin (2006) · Zbl 1115.05090
[25]	Godsil, C. D.: What is the independence number of Hamming graph? MathOverFlow. http://mathoverflow.net/questions/141842/what-is-the-independence-number-of-hamming-graph/ (2013) · Zbl 0572.05024
[26]	Godsil, C.D.: Algebraic Combinatorics. Chapman and Hall Mathematics Series. Chapman & Hall, New York (1993) · Zbl 0784.05001
[27]	Godsil, C., Meagher, K.: The Erdős-Ko-Rado Theorems: Algebraic Approaches. Cambridge University Press, Cambridge (2016) · Zbl 1343.05002
[28]	Howard, R., Károlyi, G., Székely, L.: Towards a Katona type proof for the 2-intersecting Erdős-Ko-Rado theorem. Electron. J. Combin. 8(1): Research Paper 31, pp. 8 (2001) · Zbl 0989.05122
[29]	Kamat, V., Misra, N.: An Erdős-Ko-Rado theorem for matchings in the complete graph. In: The Seventh European Conference on Combinatorics, Graph Theory and Applications of CRM Series 16, 613 (2013) · Zbl 1291.05159
[30]	Katona, G.: Intersection theorems for systems of finite sets. Acta Math. Acad. Sci. Hungar 15, 329-337 (1964) · Zbl 0134.25101 · doi:10.1007/BF01897141
[31]	Katona, G.O.H.: A simple proof of the Erdős-Chao Ko-Rado theorem. J. Comb. Theory Ser. B 13, 183-184 (1972) · Zbl 0262.05002 · doi:10.1016/0095-8956(72)90054-8
[32]	Katona, G.O.H.: The cycle method and its limits. Numbers, information and complexity (Bielefeld, 1998), pp. 129-141. Kluwer Acad. Publ, Boston, MA (2000) · Zbl 0948.05054
[33]	Ku, C.Y., Leader, I.: An Erdős-Ko-Rado theorem for partial permutations. Discrete Math. 306, 74-86 (2006) · Zbl 1088.05072 · doi:10.1016/j.disc.2005.11.007
[34]	Larose, B., Malvenuto, C.: Stable sets of maximal size in Kneser-type graphs. Eur. J. Comb. 25(5), 657-673 (2004) · Zbl 1048.05078 · doi:10.1016/j.ejc.2003.10.006
[35]	Li, Y.-S.: A Katona-type proof for intersecting families of permutations. Int. J. Contemp. Math. Sci. 3(25-28), 1261-1268 (2008) · Zbl 1202.05144
[36]	Li, Y-S., Wang, J.: Erdős-Ko-Rado-type theorems for colored sets. Electron. J. Combin., 14, Research Paper 1, p. 9 (2007) · Zbl 1111.05094
[37]	Mahdian, Mohammad: Private Communication, (2010)
[38]	Moon, A.: An analogue of the Erdős-Ko-Rado theorem for the Hamming schemes \[H(n,\, q)H\](n,q). J. Comb. Theory Ser. A. 32(3), 386-390 (1982) · Zbl 0483.05002 · doi:10.1016/0097-3165(82)90054-1
[39]	Swenson, J.: A probabilistic proof of the Erdős-Ko-Rado theorem. (2011). https://jmswen.wordpress.com/2011/06/05/a-probabilistic-proof-of-the-erdos-ko-rado-theorem/ · Zbl 1236.05199
[40]	Suda, S.: A generalization of the Erdős-Ko-Rado theorem to \[t\] t-designs in certain semilattices. Discrete Math. 312(10), 1827-1831 (2012) · Zbl 1242.05033 · doi:10.1016/j.disc.2012.01.032
[41]	van Lint, J.H., Wilson, R.M.: A Course in Combinatorics, 2nd edn. Cambridge University Press, Cambridge (2001) · Zbl 0980.05001 · doi:10.1017/CBO9780511987045
[42]	Wang, J., Zhang, H.: Nontrivial independent sets of bipartite graphs and cross-intersecting families. J. Comb. Theory Ser. A. 120, 129-141 (2013) · Zbl 1253.05112 · doi:10.1016/j.jcta.2012.07.005
[43]	Wilson, R.M.: The exact bound in the Erdős-Ko-Rado theorem. Combinatorica 4(2-3), 247-257 (1984) · Zbl 0556.05039 · doi:10.1007/BF02579226
[44]	Zhu, X.: Circular perfect graphs. J. Graph Theory 48(3), 186-209 (2005) · Zbl 1071.05037 · doi:10.1002/jgt.20050

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.