A size-sensitive inequality for cross-intersecting families

Abstract

Two families $\mathcal{A}$ and $\mathcal{B}$ of $k$-subsets of an $n$-set are called cross-intersecting if $A\cap B\ne \varnothing$ for all $A\in \mathcal{A},B\in \mathcal{B}$. Strengthening the classical Erd\H os-Ko-Rado theorem, Pyber proved that $|\mathcal{A}||\mathcal{B}|\le {\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)}^2$ holds for $n\ge 2k$. In the present paper we sharpen this inequality. We prove that assuming $|\mathcal{B}|\ge \left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)+\left(\genfrac{}{}{0ex}{}{n-i}{k-i+1}\right)$ for some $3\le i\le k+1$ the stronger inequality $$|\mathcal{A}||\mathcal{B}|\le \left(\right(\genfrac{}{}{0ex}{}{n-1}{k-1})+(\genfrac{}{}{0ex}{}{n-i}{k-i+1}\left)\right)\left(\right(\genfrac{}{}{0ex}{}{n-1}{k-1})-(\genfrac{}{}{0ex}{}{n-i}{k-1}\left)\right)$$ holds. These inequalities are best possible.