×

\(r\)-cross \(t\)-intersecting families via necessary intersection points. (English) Zbl 1532.05163

The paper generalizes the classical theorem of A. J. W. Hilton and E. C. Milner [Q. J. Math., Oxf. II. Ser. 18, 369–384 (1967; Zbl 0168.26205)] for cross-intersecting families in various directions. Let \(n\), \(r\) and \(t\) be positive integers, where \(r \geq 2\). If \(\mathcal{F}_1, \dots, \mathcal{F}_r\) are families of sets such that \(|\bigcap_{i=1}^r F_i| \geq t\) for every \((F_1, \dots, F_r) \in \mathcal{F}_1 \times \dots \times \mathcal{F}_r\), then they are said to be \(r\)-cross \(t\)-intersecting. The authors determine the maximum sum of sizes of \(r\) non-empty \(r\)-cross \(t\)-intersecting families \(\mathcal{F}_1, \dots, \mathcal{F}_r\) of subsets of \([n] = \{1, \dots, n\}\). They also address the more general setting where \(\mathcal{F}_1, \dots, \mathcal{F}_r\) are equipped with certain natural and important measures, such as the product measure and the uniform measure. For each \(i \in [r]\), let \(\mu_i \colon \{0, 1, \dots, n\} \rightarrow \mathbb{R}_{\geq 0}\), and let \(\mu_i(\mathcal{F}_i)\) denote the measure \(\sum_{F \in \mathcal{F}_i} \mu_i(|F|)\) of \(\mathcal{F}_i\). The authors determine the largest possible value of \(\sum_{i=1}^r \mu_i(\mathcal{F}_i)\) for the case where \(\mu_1, \dots, \mu_r\) are non-increasing. For \(1 \leq k_1 \leq \cdots \leq k_r \leq n\), they determine the largest possible value of \(\sum_{i=1}^r \mu_i(\mathcal{F}_i)\) for the case where \(n \geq 2k_r + k_2 - t\) and \(\emptyset \neq \mathcal{F}_i \subseteq \{A \subseteq [n] \colon |A| \leq k_i\}\) for each \(i \in [r]\). By taking \(k_1 = \cdots = k_r = k\), \(\mu_1(k) = \dots = \mu_r(k) = 1\) and \(\mu_1(j) = \dots = \mu_r(j) = 0\) for each \(j \in \{0, 1, \dots, n\} \backslash \{k\}\), the maximum sum of sizes of \(r\) non-empty \(r\)-cross \(t\)-intersecting families of \(k\)-element subsets of \([n]\) is obtained.
Reviewer: Peter Borg (Msida)

MSC:

05D05 Extremal set theory
05C35 Extremal problems in graph theory

Citations:

Zbl 0168.26205

References:

[1] R.Ahlswede and G. O. H.Katona, Contributions to the geometry of Hamming spaces, Discrete Math.17 (1977), no. 1, 1-22, DOI http://doi.org/10.1016/0012‐365X(77)90017‐6. MR465883 · Zbl 0368.05001 · doi:10.1016/0012‐365X(77)90017‐6
[2] R.Ahlswede and L. H.Khachatrian, The complete intersection theorem for systems of finite sets, European J. Combin.18 (1997), no. 2, 125-136, DOI http://doi.org/10.1006/eujc.1995.0092. MR1429238 · Zbl 0869.05066 · doi:10.1006/eujc.1995.0092
[3] R.Ahlswede and L. H.Khachatrian, A pushing‐pulling method: new proofs of intersection theorems, Combinatorica19 (1999), no. 1, 1-15, DOI http://doi.org/10.1007/s004930050042. MR1722359 · Zbl 0980.05049 · doi:10.1007/s004930050042
[4] R.Ahlswede and L. H.Khachatrian, The diametric theorem in Hamming spaces—optimal anticodes, Adv. Appl. Math.20 (1998), no. 4, 429-449, DOI http://doi.org/10.1006/aama.1998.0588. MR1612850 · Zbl 0909.05044 · doi:10.1006/aama.1998.0588
[5] C.Bey and K.Engel, Old and new results for the weighted \(t\)‐intersection problem via AK‐methods, Numbers, information and complexity (Bielefeld, 1998), Kluwer Acad. Publ., Boston, MA, 2000, pp. 45-74, DOI http://doi.org/10.1007/978‐1‐4757‐6048‐4_5. MR1752947 · Zbl 1122.05316 · doi:10.1007/978‐1‐4757‐6048‐4_5
[6] P.Borg, The maximum sum and the maximum product of sizes of cross‐intersecting families, European J. Combin.35 (2014), 117-130, DOI http://doi.org/10.1016/j.ejc.2013.06.029. MR3090491 · Zbl 1296.05191 · doi:10.1016/j.ejc.2013.06.029
[7] P.Borg, A cross‐intersection theorem for subsets of a set, Bull. Lond. Math. Soc.47 (2015), no. 2, 248-256, DOI http://doi.org/10.1112/blms/bdu110. MR3335119 · Zbl 1314.05205 · doi:10.1112/blms/bdu110
[8] P.Borg, The maximum product of weights of cross‐intersecting families, J. Lond. Math. Soc. (2)94 (2016), no. 3, 993-1018, DOI http://doi.org/10.1112/jlms/jdw067. MR3614937 · Zbl 1358.05294 · doi:10.1112/jlms/jdw067
[9] P.Borg, The maximum product of sizes of cross‐intersecting families, Discrete Math.340 (2017), no. 9, 2307-2317, DOI http://doi.org/10.1016/j.disc.2017.04.019. MR3665084 · Zbl 1365.05287 · doi:10.1016/j.disc.2017.04.019
[10] P.Borg and C.Feghali, The maximum sum of sizes of cross‐intersecting families of subsets of a set, Discrete Math.345 (2022), no. 11, Paper No. 112981, 4, DOI http://doi.org/10.1016/j.disc.2022.112981. MR4441255 · Zbl 1495.05322 · doi:10.1016/j.disc.2022.112981
[11] I.Dinur and S.Safra, On the hardness of approximating minimum vertex cover, Ann. of Math. (2)162 (2005), no. 1, 439-485, DOI http://doi.org/10.4007/annals.2005.162.439. MR2178966 · Zbl 1084.68051 · doi:10.4007/annals.2005.162.439
[12] P.Erdős, My joint work with Richard Rado, Surveys in combinatorics 1987 (New Cross, 1987), London Math. Soc. Lecture Note Ser., vol. 123, Cambridge Univ. Press, Cambridge, 1987, pp. 53-80. MR905276 · Zbl 0623.01010
[13] P.Erdős, C.Ko, and R.Rado, Intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser. (2)12 (1961), 313-320, DOI http://doi.org/10.1093/qmath/12.1.313. MR140419 · Zbl 0100.01902 · doi:10.1093/qmath/12.1.313
[14] Y.Filmus, The weighted complete intersection theorem, J. Combin. Theory Ser. A151 (2017), 84-101, DOI http://doi.org/10.1016/j.jcta.2017.04.008. MR3663490 · Zbl 1366.05111 · doi:10.1016/j.jcta.2017.04.008
[15] Y.Filmus, More complete intersection theorems, Discrete Math.342 (2019), no. 1, 128-142, DOI http://doi.org/10.1016/j.disc.2018.09.017. MR3886256 · Zbl 1400.05251 · doi:10.1016/j.disc.2018.09.017
[16] P.Frankl, Extremal set systems, Hungarian Academy of Sciences, PhD thesis, in Hungarian, 1977. · Zbl 0844.05094
[17] P.Frankl, The Erdős‐Ko‐Rado theorem is true for \(n=ckt\), Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Colloq. Math. Soc. János Bolyai, vol. 18, North‐Holland, Amsterdam‐New York, 1978, pp. 365-375. MR519277 · Zbl 0401.05001
[18] P.Frankl and Z.Füredi, Beyond the Erdős‐Ko‐Rado theorem, J. Combin. Theory Ser. A56 (1991), no. 2, 182-194, DOI http://doi.org/10.1016/0097‐3165(91)90031‐B. MR1092847 · Zbl 0742.05080 · doi:10.1016/0097‐3165(91)90031‐B
[19] P.Frankl and A.Kupavskii, A size‐sensitive inequality for cross‐intersecting families, European J. Combin.62 (2017), 263-271, DOI http://doi.org/10.1016/j.ejc.2017.01.004. MR3621739 · Zbl 1358.05295 · doi:10.1016/j.ejc.2017.01.004
[20] P.Frankl and A.Kupavskii, Uniform \(s\)‐cross‐intersecting families, Combin. Probab. Comput.26 (2017), no. 4, 517-524, DOI http://doi.org/10.1017/S0963548317000062. MR3656339 · Zbl 1371.05298 · doi:10.1017/S0963548317000062
[21] P.Frankl and N.Tokushige, Some best possible inequalities concerning cross‐intersecting families, J. Combin. Theory Ser. A61 (1992), no. 1, 87-97, DOI http://doi.org/10.1016/0097‐3165(92)90054‐X. MR1178386 · Zbl 0767.05093 · doi:10.1016/0097‐3165(92)90054‐X
[22] P.Frankl and N.Tokushige, On \(r\)‐cross intersecting families of sets, Combin. Probab. Comput.20 (2011), no. 5, 749-752, DOI http://doi.org/10.1017/S0963548311000289. MR2825588 · Zbl 1283.05259 · doi:10.1017/S0963548311000289
[23] P.Frankl and N.Tokushige, Extremal problems for finite sets, Student Mathematical Library, vol. 86, American Mathematical Society, Providence, RI, 2018. MR3822342 · Zbl 1416.05001
[24] P.Frankl and H. W. W.Wong, Analogues of Katona’s and Milner’s theorems for two families, Discrete Math.344 (2021), no. 5, Paper No. 112327, 10, DOI http://doi.org/10.1016/j.disc.2021.112327. MR4212039 · Zbl 1460.05186 · doi:10.1016/j.disc.2021.112327
[25] A. J. W.Hilton, An intersection theorem for a collection of families of subsets of a finite set, J. London Math. Soc. (2)15 (1977), no. 3, 369-376, DOI http://doi.org/10.1112/jlms/s2‐15.3.369. MR444483 · Zbl 0364.05002 · doi:10.1112/jlms/s2‐15.3.369
[26] A. J. W.Hilton and E. C.Milner, Some intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser. (2)18 (1967), 369-384, DOI http://doi.org/10.1093/qmath/18.1.369. MR219428 · Zbl 0168.26205 · doi:10.1093/qmath/18.1.369
[27] G.Katona, A theorem of finite sets, Theory of graphs (Proc. Colloq., Tihany, 1966), Academic Press, New York, 1968, pp. 187-207. MR0290982 · Zbl 0313.05003
[28] J. B.Kruskal, The number of simplices in a complex, Mathematical optimization techniques, Univ. California Press, Berkeley, CA, 1963, pp. 251-278. MR0154827 · Zbl 0116.35102
[29] M.Matsumoto and N.Tokushige, The exact bound in the Erdős‐Ko‐Rado theorem for cross‐intersecting families, J. Combin. Theory Ser. A52 (1989), no. 1, 90-97, DOI http://doi.org/10.1016/0097‐3165(89)90065‐4. MR1008163 · Zbl 0734.05085 · doi:10.1016/0097‐3165(89)90065‐4
[30] L.Pyber, A new generalization of the Erdős‐Ko‐Rado theorem, J. Combin. Theory Ser. A43 (1986), no. 1, 85-90, DOI http://doi.org/10.1016/0097‐3165(86)90025‐7. MR859299 · Zbl 0614.05001 · doi:10.1016/0097‐3165(86)90025‐7
[31] C.Shi, P.Frankl, and J.Qian, On non‐empty cross‐intersecting families, available at arXiv:2009.09396v2.
[32] S.Suda and H.Tanaka, A cross‐intersection theorem for vector spaces based on semidefinite programming, Bull. Lond. Math. Soc.46 (2014), no. 2, 342-348, DOI http://doi.org/10.1112/blms/bdt101. MR3194752 · Zbl 1285.05181 · doi:10.1112/blms/bdt101
[33] N.Tokushige, Intersecting families—uniform versus weighted, Ryukyu Math. J.18 (2005), 89-103, MR2200201 · Zbl 1108.05091
[34] J.Wang and H.Zhang, Cross‐intersecting families and primitivity of symmetric systems, J. Combin. Theory Ser. A118 (2011), no. 2, 455-462, DOI http://doi.org/10.1016/j.jcta.2010.09.005. MR2739496 · Zbl 1220.05130 · doi:10.1016/j.jcta.2010.09.005
[35] J.Wang and H.Zhang, Nontrivial independent sets of bipartite graphs and cross‐intersecting families, J. Combin. Theory Ser. A120 (2013), no. 1, 129-141, DOI http://doi.org/10.1016/j.jcta.2012.07.005. MR2971702 · Zbl 1253.05112 · doi:10.1016/j.jcta.2012.07.005
[36] R. M.Wilson, The exact bound in the Erdős‐Ko‐Rado theorem, Combinatorica4 (1984), no. 2‐3, 247-257, DOI http://doi.org/10.1007/BF02579226. MR771733 · Zbl 0556.05039 · doi:10.1007/BF02579226
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.