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 A and B are said to be \emph{cross-t-intersecting} if each set in A t-intersects each set in B. For any positive integers n and r, let ([n]r) denote the family of all r-element subsets of {1,2,…,n}. We show that for any integers r, s and t with 1≤t≤r≤s, there exists an integer n0(r,s,t) such that for any integer n≥n0(r,s,t), if A⊂([n]r) and B⊂([n]s) such that A and B are cross-t-intersecting, then |A||B|≤(n−tr−t)(n−ts−t), and equality holds if and only if for some T∈([n]t), A={A∈([n]r):T⊂A} and B={B∈([n]s):T⊂B}. This verifies a conjecture of Hirschorn.