2024/11/25 by Biao Wu, Wu, Biao, Huajun Zhang +1
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Mathematical functions and polynomials
paper · pdf · doi:10.48550/arxiv.2411.16091
openalex publication_date 2024/11/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Two families A and B of sets are called cross-intersecting if each pair of sets A∈ A and B∈ B has nonempty intersection. Let \calA and \cal B be two cross-intersecting families of k-subsets and ℓ-subsets of [n]. Matsumoto and Tokushige [J. Combin. Theory Ser. A 52 (1989) 90--97] studied the extremal problem of the size |\calA||\calB| and obtained the uniqueness of extremal families whenever n≥ 2 ℓ≥ 2k, building on the work of Pyber. This paper will explore the second extremal size of |\calA||\calB| and obtain that if A and B are not the subfamilies of Matsumoto--Tokushige's extremal families, then, for n≥ 2ℓ >2k or n> 2ℓ=2k, \beginitemize \item[1)]either |\calA||\calB|≤ (\binomn-1k-1+\binomn-2 k-1)\binomn-2ℓ-2 with the unique extremal families (up to isomorphism) \mboxA=\A∈ \binom[n]k: 1∈ A \rm or 2∈ A\ and B=\B∈ \binom[n]ℓ: [2] ⊆ B\; \item[2)] or |\calA||\calB|≤ (\binomn-1k-1+1)(\binomn-1ℓ-1-\binomn-k-1ℓ-1) with the unique extremal families (up to isomorphism) \mboxA=\A∈ \binom[n]k: 1∈ A\∪ \[2,k+1] \ and B=\B∈ \binom[n]ℓ: 1∈ B, B∩ [2,k+1]≠ ∅ \. \enditemize The bound ``n≥ 2ℓ >2k or n> 2ℓ=2k" is sharp for n. To achieve the above results, we establish some size-sensitive inequalities for cross-intersecting families. As by-products, we will recover the main results of Frankl and Kupavskii [European J. Combin. 62 (2017) 263--271].