An Erd\H os--Ko--Rado theorem for cross $t$-intersecting families

Abstract

Two families $\mathcal{A}$ and $\mathcal{B}$, of $k$-subsets of an $n$-set, are {\em cross $t$-intersecting} if for every choice of subsets $A\in \mathcal{A}$ and $B\in \mathcal{B}$ we have $|A\cap B|\ge t$. We address the following conjectured cross $t$-intersecting version of the Erd\H os--Ko--Rado Theorem: For all $n\ge (t+1)(k-t+1)$ the maximum value of $|\mathcal{A}||\mathcal{B}|$ for two cross $t$-intersecting families $\mathcal{A},\mathcal{B}\subset \left(\genfrac{}{}{0ex}{}{[n]}{k}\right)$ is ${\left(\genfrac{}{}{0ex}{}{n-t}{k-t}\right)}^2$. We verify this for all $t\ge 14$ except finitely many $n$ and $k$ for each fixed $t$. Further, we prove uniqueness and stability results in these cases, showing, for instance, that the families reaching this bound are unique up to isomorphism. We also consider a {\em $p$-weight} version of the problem, which comes from the product measure on the power set of an $n$-set.

arXiv comment40 pages, 2 figures

Cited by in corpus (2)

• Cross-intersecting families of vectors
• The maximum product of sizes of cross-$t$-intersecting uniform families