2016/11/22 by Péter Frankl, Peter Frankl, Frankl, Peter +2
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1611.07258
This article was previously a portion of arXiv:1603.00938v1, which has been split
openalex publication_date 2016/11/22 · arxiv created 2017/01/15 · arxiv updated 2017/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 n-1\choose k-1. We say that two non-empty families are \mathcal A, \mathcal B⊂ [n]\choose k are \it 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 nonempty 1-cross-intersecting families.