Back to Search Start Over

Uniform s-Cross-Intersecting Families

Authors :
Peter Frankl
Andrey Kupavskii
Source :
Combinatorics, Probability and Computing. 26:517-524
Publication Year :
2017
Publisher :
Cambridge University Press (CUP), 2017.

Abstract

In this paper we study a question related to the classical Erd\H{o}s-Ko-Rado theorem, which states that any family of $k$-element subsets of the set $[n] = \{1,\ldots,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\subset {[n]\choose k}$ are {\it $s$-cross-intersecting}, if for any $A\in\mathcal A,B\in \mathcal B$ we have $|A\cap B|\ge 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.<br />Comment: This article was previously a portion of arXiv:1603.00938v1, which has been split

Details

ISSN :
14692163 and 09635483
Volume :
26
Database :
OpenAIRE
Journal :
Combinatorics, Probability and Computing
Accession number :
edsair.doi.dedup.....3298a7efc10ce34204fa569117e0aed4