On non-empty cross-intersecting families

Abstract

Let $2^{[n]}$ and $\left(\genfrac{}{}{0ex}{}{[n]}{i}\right)$ be the power set and the class of all $i$-subsets of $\{1,2,\cdots ,n\}$, respectively. We call two families $\mathcal{A}$ and $\mathcal{B}$ cross-intersecting if $A\cap B\ne \varnothing$ for any $A\in \mathcal{A}$ and $B\in \mathcal{B}$. In this paper we show that, for $n\ge k+l,l\ge r\ge 1,c>0$ and $\mathcal{A}\subseteq \left(\genfrac{}{}{0ex}{}{[n]}{k}\right),\mathcal{B}\subseteq \left(\genfrac{}{}{0ex}{}{[n]}{l}\right)$, if $\mathcal{A}$ and $\mathcal{B}$ are cross-intersecting and $\left(\genfrac{}{}{0ex}{}{n-r}{l-r}\right)\le |\mathcal{B}|\le \left(\genfrac{}{}{0ex}{}{n-1}{l-1}\right)$, then $$|\mathcal{A}|+c|\mathcal{B}|\le \max \left\{\left(\genfrac{}{}{0ex}{}{n}{k}\right)-\left(\genfrac{}{}{0ex}{}{n-r}{k}\right)+c\left(\genfrac{}{}{0ex}{}{n-r}{l-r}\right),\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)+c\left(\genfrac{}{}{0ex}{}{n-1}{l-1}\right)\right\}$$ and the families $\mathcal{A}$ and $\mathcal{B}$ 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).

12 pages