Uniform s-cross-intersecting families

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,\dots ,n\}$ in which any two sets intersect, has cardinality at most $\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$. We say that two non-empty families are $\mathcal{A},\mathcal{B}\subset \left(\genfrac{}{}{0ex}{}{[n]}{k}\right)$ 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.

This article was previously a portion of arXiv:1603.00938v1, which has been split