On non-empty cross-intersecting families

2020/09/20 by Chao Shi, Shi, Chao, Péter Frankl +3 · 2 citations
Mathematics · #05D05 #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2009.09396

openalex publication_date 2020/09/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let 2^[n] and \binom[n]i be the power set and the class of all i-subsets of \1,2,⋯,n\, respectively. We call two families \mathscrA and \mathscrB cross-intersecting if A∩ B≠ ∅ for any A∈ \mathscrA and B∈ \mathscrB. In this paper we show that, for n≥ k+l,l≥ r≥ 1,c>0 and \mathscrA⊆ \binom[n]k,\mathscrB⊆ \binom[n]l, if \mathscrA and \mathscrB are cross-intersecting and \binomn-rl-r≤|\mathscrB|≤ \binomn-1l-1, then |\mathscrA|+c|\mathscrB|≤ max\\binomnk-\binomn-rk+c\binomn-rl-r, \binomn-1k-1+c\binomn-1l-1\ and the families \mathscrA and \mathscrB attaining the upper bound are also characterized. This generalizes the corresponding result of Hilton and Milner for c=1 and r=k=l, and implies a result of Tokushige and the second author (Theorem 1.3).

Cited by

• Extremal t-intersecting families for finite sets with t-covering number at least t+2
• The maximum sum of sizes of non-empty cross L-intersecting families

Related

• On cross-2-intersecting families
• Sharp results concerning disjoint cross-intersecting families
• A note on non-empty cross-intersecting families
• Non-uniform Cross-intersecting Families
• Disjoint Cross Intersecting Families