The sum of sizes of nontrivial cross-intersecting families
Abstract
Families 𝒜1,…,𝒜m⊆binom[n]k are cross-intersecting if every member of one family meets every member of each other family. A family is nontrivial if its members have no common element. For n>2k and m≥3, we determine the maximum sum of the sizes of m nonempty, nontrivial cross-intersecting families. We prove the sharp bound ∑i=1m|𝒜i| ≤ max{m h(n,k,1), g(n,k)+3(m−1)}, where h(n,k,1)=binomn−1k−1−binomn−k−1k−1+1 and g(n,k)=binom nk−2binomn−kk −binomn−k−1k−1+binomn−2k+1k. We also characterize all equality cases. Two types of extremal configurations arise: copies of a maximum nontrivial intersecting family, and copies of a specific three-member nontrivial intersecting family together with its full cross-intersecting companion. The proof applies a known restricted lexicographic comparison to obtain the weighted bound for shifted families, and uses local generator reductions for critically shifted families. These reductions exploit shiftedness after removing the common core of a section, while preserving nontriviality and the required shadow relations between sections.
Related
- On the product of nontrivial cross-intersecting families
- Sizes of cross-intersecting families
- A product inequality and its application to cross-intersecting families
- A product theorem for r-cross intersecting families of subspaces
- Sharp stability for cross t-intersecting families of permutations in the linear range
BibTeX
@misc{zhang2026sizes,
title = {{The sum of sizes of nontrivial cross-intersecting families}},
author = {Huajun Zhang},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.00148},
eprint = {2611.00148},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.00148},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - The sum of sizes of nontrivial cross-intersecting families
AU - Huajun Zhang
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.00148
UR - https://arxiv.org/abs/2611.00148
AB - Families 𝒜_1,…,𝒜_m⊆binom[n]k are cross-intersecting if every member of one family meets every member of each other family. A family is nontrivial if its members have no common element. For n>2k and m≥3, we determine the maximum sum of the sizes of m nonempty, nontrivial cross-intersecting families. We prove the sharp bound ∑_i=1^m|𝒜_i| ≤ max{m h(n,k,1), g(n,k)+3(m−1)}, where h(n,k,1)=binomn−1k−1−binomn−k−1k−1+1 and g(n,k)=binom nk−2binomn−kk −binomn−k−1k−1+binomn−2k+1k. We also characterize all equality cases. Two types of extremal configurations arise: copies of a maximum nontrivial intersecting family, and copies of a specific three-member nontrivial intersecting family together with its full cross-intersecting companion. The proof applies a known restricted lexicographic comparison to obtain the weighted bound for shifted families, and uses local generator reductions for critically shifted families. These reductions exploit shiftedness after removing the common core of a section, while preserving nontriviality and the required shadow relations between sections.
ER -