On the product of nontrivial cross-intersecting families
Abstract
Let n≥2ℓ≥2k≥6 and n>k+ℓ. We determine the maximum of |𝒜||ℬ| over all nonempty, nontrivial cross-intersecting families 𝒜⊆binom[n]k and ℬ⊆binom[n]ℓ. The exact bound is |𝒜||ℬ|≤max{M1,M2}, where M1 &=(binomn−1k−1−binomn−ℓ−1k−1+1) (binomn−1ℓ−1−binomn−k−1ℓ−1+1), M2 &=(binomn−2ℓ−2+1) ∑i=12 (binomn−ik−1−binomn−ℓ−ik−1). Both terms are attained by explicit constructions: a Hilton--Milner-type pair and a two-point construction, respectively. We classify all equality cases, including the additional cross-triangle pairs when k=ℓ=3. Two structural results underlie the proof. First, we establish a restricted-lex comparison theorem showing that restricted lexicographic initial segments minimize disjointness neighborhoods, and characterize equality at the first nontrivial threshold. Second, a decomposition of critically shifted families into two parts with disjoint cores leads to a sharp product theorem, with equality characterized, for all cross-intersecting pairs admitting this decomposition, without additional nontriviality assumptions. Endpoint comparisons and reverse shifting complete the proof for unequal as well as equal uniformities.
Related
- The sum of sizes of nontrivial cross-intersecting families
- A product inequality and its application to cross-intersecting families
- A product theorem for r-cross intersecting families of subspaces
- Sizes of cross-intersecting families
- A Sharp Product Bound for Disjoint Cross-Intersecting 3-Graphs with Covering Number Three
BibTeX
@misc{wu2026product,
title = {{On the product of nontrivial cross-intersecting families}},
author = {Biao Wu and Huajun Zhang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.34944},
eprint = {2610.34944},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.34944},
}
RIS
TY - UNPB
TI - On the product of nontrivial cross-intersecting families
AU - Biao Wu
AU - Huajun Zhang
PY - 2026
DA - 2026/10/26
PB - arXiv
DO - 10.48550/arxiv.2610.34944
UR - https://arxiv.org/abs/2610.34944
AB - Let n≥2ℓ≥2k≥6 and n>k+ℓ. We determine the maximum of |𝒜||ℬ| over all nonempty, nontrivial cross-intersecting families 𝒜⊆binom[n]k and ℬ⊆binom[n]ℓ. The exact bound is |𝒜||ℬ|≤max{M_1,M_2}, where M_1 &=(binomn−1k−1−binomn−ℓ−1k−1+1) (binomn−1ℓ−1−binomn−k−1ℓ−1+1), M_2 &=(binomn−2ℓ−2+1) ∑_i=1^2 (binomn−ik−1−binomn−ℓ−ik−1). Both terms are attained by explicit constructions: a Hilton--Milner-type pair and a two-point construction, respectively. We classify all equality cases, including the additional cross-triangle pairs when k=ℓ=3. Two structural results underlie the proof. First, we establish a restricted-lex comparison theorem showing that restricted lexicographic initial segments minimize disjointness neighborhoods, and characterize equality at the first nontrivial threshold. Second, a decomposition of critically shifted families into two parts with disjoint cores leads to a sharp product theorem, with equality characterized, for all cross-intersecting pairs admitting this decomposition, without additional nontriviality assumptions. Endpoint comparisons and reverse shifting complete the proof for unequal as well as equal uniformities.
ER -