Uniformly cross intersecting families

Abstract

Let $\mathcal{A}$ and $\matchcal{B}$ denote two families of subsets of an $n$-element set. The pair $(\mathcal{A},\mathcal{B})$ is said to be $\ell$-cross-intersecting iff $|A\cap B|=\ell$ for all $A\in \mathcal{A}$ and $B\in \mathcal{B}$. Denote by $P_{\ell }(n)$ the maximum value of $|\mathcal{A}||\mathcal{B}|$ over all such pairs. The best known upper bound on $P_{\ell }(n)$ is $\Theta (2^n)$, by Frankl and Rödl. For a lower bound, Ahlswede, Cai and Zhang showed, for all $n\ge 2\ell$, a simple construction of an $\ell$-cross-intersecting pair $(\mathcal{A},\mathcal{B})$ with $|\mathcal{A}||\mathcal{B}|=\left(\genfrac{}{}{0ex}{}{2\ell }{\ell }\right)2^{n-2\ell }=\Theta (2^n/\sqrt{\ell })$, and conjectured that this is best possible. Consequently, Sgall asked whether or not $P_{\ell }(n)$ decreases with $\ell$. In this paper, we confirm the above conjecture of Ahlswede et al. for any sufficiently large $\ell$, implying a positive answer to the above question of Sgall as well. By analyzing the linear spaces of the characteristic vectors of $\mathcal{A},\mathcal{B}$ over $\mathbb{R}$, we show that there exists some ${\ell }_0>0$, such that $P_{\ell }(n)\le \left(\genfrac{}{}{0ex}{}{2\ell }{\ell }\right)2^{n-2\ell }$ for all $\ell \ge {\ell }_0$. Furthermore, we determine the precise structure of all the pairs of families which attain this maximum.