Abstract
Let \([n]{:}{=}\lbrace 1,2,\ldots ,n \rbrace \), and M be a set of positive integers. Denote the family of all subsets of [n] with sizes in M by \(\left( {\begin{array}{c}\left[ n\right] \\ M\end{array}}\right) \). The non-empty families \(\mathcal {A}\subseteq \left( {\begin{array}{c}\left[ n\right] \\ R\end{array}}\right) \) and \(\mathcal {B}\subseteq \left( {\begin{array}{c}\left[ n\right] \\ S\end{array}}\right) \) are said to be cross t-intersecting if \(|A\cap B|\ge t\) for all \(A\in \mathcal {A}\) and \(B\in \mathcal {B}\). In this paper, we determine the maximum sum of sizes of non-empty cross t-intersecting families, and characterize the extremal families. Similar result for finite vector spaces is also proved.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Data Availability
Data sharing not applicable to this paper as no datasets were generated or analysed during the current study.
References
Ahlswede, R., Khachatrian, L.H.: The complete intersection theorem for systems of finite sets. Eur. J. Combin. 18(2), 125–136 (1997)
Aschbacher, M.: On the maximal subgroups of the finite classical groups. Invent. Math. 76(3), 469–514 (1984)
Borg, P., Feghali, C.: The maximum sum of sizes of cross-intersecting families of subsets of a set. Discr. Math. 345(11), 112981 (2022)
Deza, M., Frankl, P.: The Erdős–Ko–Rado theorem–\(22\) years later. SIAM J. Algebr. Discr. Methods 4(4), 419–431 (1983)
Erdős, P., Ko, C., Rado, R.: Intersection theorems for systems of finite sets. Quart. J. Math. Oxf. 2(12), 313–320 (1961)
Frankl, P.: The Erdős-Ko-Rado theorem is true for \(n=ckt\). Coll. Math. Soc. J. Bolyai 18, 365–375 (1978)
Frankl, P., Graham, R.L.: Intersection theorems for vector spaces. Eur. J. Combin. 6(2), 183–187 (1985)
Frankl, P., Liu, E.L.L., Wang, J., Yang, Z.: Non-trivial \(t\)-intersecting separated families. Discr. Appl. Math. 342, 124–137 (2024)
Frankl, P., Tokushige, N.: Some best possible inequalities concerning cross-intersecting families. J. Combin. Theory Ser. A 61(1), 87–97 (1992)
Frankl, P., Wilson, R.M.: The Erdős-Ko-Rado theorem for vector spaces. J. Combin. Theory Ser. A 43(2), 228–236 (1986)
Gupta, P., Mogge, Y., Piga, S., Schülke, B.: \(r\)-cross \(t\)-intersecting families via necessary intersection points. Bull. Lond. Math. Soc. 55(3), 1447–1458 (2023)
Hilton, A.J.W., Milner, E.C.: Some intersection theorems for systems of finite sets. Quart. J. Math. Oxf. Ser. 2(18), 369–384 (1967)
Hsieh, W.N.: Families of intersecting finite vector spaces. J. Combinatorial Theory Ser. A 18, 252–261 (1975)
Hsieh, W.N.: Intersection theorems for systems of finite vector spaces. Discr. Math. 12(1), 1–16 (1975)
Liu, E.L.L.: The maximum sum of the sizes of cross \(t\)-intersecting separated families. AIMS Math. 8(12), 30910–30921 (2023)
Newton, B., Benesh, B.: A classification of certain maximal subgroups of symmetric groups. J. Algebra 304(2), 1108–1113 (2006)
Tanaka, H.: Classification of subsets with minimal width and dual width in Grassmann, bilinear forms and dual polar graphs. J. Combin. Theory Ser. A 113(5), 903–910 (2006)
Wang, J., Zhang, H.: Normalized matching property of a class of subspace lattices. Taiwan. J. Math. 11(1), 43–50 (2007)
Wang, J., Zhang, H.: Nontrivial independent sets of bipartite graphs and cross-intersecting families. J. Combin. Theory Ser. A 120(1), 129–141 (2013)
Wang, Y.: On a class of subspace lattices. J. Math. Res. Expos. 19(2), 341–348 (1999)
Wilson, R.M.: The exact bound in the Erdős–Ko–Rado theorem. Combinatorica 4, 247–257 (1984)
Funding
The authors declare that no funds, grants, or other support were received during the preparation of this manuscript.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors declare that they have no Conflict of interest.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Li, S., Liu, D., Song, D. et al. The Maximum Sum of Sizes of Non-Empty Cross t-Intersecting Families. Graphs and Combinatorics 40, 103 (2024). https://doi.org/10.1007/s00373-024-02835-z
Received:
Revised:
Accepted:
Published:
Version of record:
DOI: https://doi.org/10.1007/s00373-024-02835-z
