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

Abstract

We say that a set $A$ \emph{$t$-intersects} a set $B$ if $A$ and $B$ have at least $t$ common elements. Two families $\mathcal{A}$ and $\mathcal{B}$ are said to be \emph{cross-$t$-intersecting} if each set in $\mathcal{A}$ $t$-intersects each set in $\mathcal{B}$. For any positive integers $n$ and $r$, let $\left(\genfrac{}{}{0ex}{}{[n]}{r}\right)$ denote the family of all $r$-element subsets of $\{1,2,\dots ,n\}$. We show that for any integers $r$, $s$ and $t$ with $1\le t\le r\le s$, there exists an integer $n_0(r,s,t)$ such that for any integer $n\ge n_0(r,s,t)$, if $\mathcal{A}\subset \left(\genfrac{}{}{0ex}{}{[n]}{r}\right)$ and $\mathcal{B}\subset \left(\genfrac{}{}{0ex}{}{[n]}{s}\right)$ such that $\mathcal{A}$ and $\mathcal{B}$ are cross-$t$-intersecting, then $|\mathcal{A}||\mathcal{B}|\le \left(\genfrac{}{}{0ex}{}{n-t}{r-t}\right)\left(\genfrac{}{}{0ex}{}{n-t}{s-t}\right)$, and equality holds if and only if for some $T\in \left(\genfrac{}{}{0ex}{}{[n]}{t}\right)$, $\mathcal{A}=\{A\in (\genfrac{}{}{0ex}{}{[n]}{r}):T\subset A\}$ and $\mathcal{B}=\{B\in (\genfrac{}{}{0ex}{}{[n]}{s}):T\subset B\}$. This verifies a conjecture of Hirschorn.

arXiv comment9 pages

References in corpus (3)

• Intersecting families of sets and permutations: a survey
• Asymptotic upper bounds on the shades of t-intersecting families
• An Erd\H os--Ko--Rado theorem for cross $t$-intersecting families