Uniform s-Cross-Intersecting Families. (28th March 2017)

• Record Type: Journal Article
• Authors: FRANKL, PETER; KUPAVSKII, ANDREY
• Is Part Of: Combinatorics, probability and computing. Volume 26:Number 4(2017:Jul.)
• Page Start: 517
• Page End: 524
• Publication Date: 2017-03-28
• Subjects: 05D05; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548317000062
• Languages: English
• ISSNs: 0963-5483

Abstract

Abstract : In this paper we study a question related to the classical Erdős–Ko–Rado theorem, which states that any family of k -element subsets of the set [ n ] = {1, . . ., n } in which any two sets intersect has cardinality at most $\binom{n-1}{k-1}$ . We say that two non-empty families ${\mathcal A}, {\mathcal B}\subset \binom{[n]}{k}$ are s-cross-intersecting if, for any A ∈ ${\mathcal A}$, B ∈ ${\mathcal B}$, we have | A ∩ B | ≥ s . In this paper we determine the maximum of | ${\mathcal A}$ |+| ${\mathcal B}$ | for all n . This generalizes a result of Hilton and Milner, who determined the maximum of | ${\mathcal A}$ |+| ${\mathcal B}$ | for non-empty 1-cross-intersecting families.