A sharp product bound for non-trivial cross-intersecting families

Two families $\mathcal{A},\mathcal{B}\subset \left(\genfrac{}{}{0px}{}{[n]}{k}\right)$ are cross-intersecting if $A\cap B\mathrm{\ne }\mathrm{\varnothing }$ for all $A\in \mathcal{A}$ and $B\in \mathcal{B}$, and non-trivial if neither $\text{m}A$ nor $\text{m}B$ is a star. Pyber proved that any two cross-intersecting families $\mathcal{A},\mathcal{B}\subset \left(\genfrac{}{}{0px}{}{[n]}{k}\right)$ satisfy $\mathrm{\mid }\mathcal{A}\mathrm{\mid }\mathrm{\mid }\mathcal{B}\mathrm{\mid }\le {\left(\genfrac{}{}{0px}{}{n-1}{k-1}\right)}^2$, and the maximum is attained by two full stars. Frankl, as well as Frankl and Wang, conjectured that the sharp bound, when both families are required to be non-trivial, is $h(n,k{)}^2$, where $h(n,k)=\left(\genfrac{}{}{0px}{}{n-1}{k-1}\right)-\left(\genfrac{}{}{0px}{}{n-k-1}{k-1}\right)+1$, the size of the Hilton–Milner family. The cases $k=3$, and the range $k\ge 8$ and $n\ge 4k$, were established earlier by Frankl and by Frankl and Wang, respectively. In this paper, we prove their conjecture in the full range. We show that every non-trivial cross-intersecting pair $\mathcal{A},\mathcal{B}\subset \left(\genfrac{}{}{0px}{}{[n]}{k}\right)$ with $n\ge 2k$ and $k\ge 3$ satisfies $\mathrm{\mid }\mathcal{A}\mathrm{\mid }\mathrm{\mid }\mathcal{B}\mathrm{\mid }\le h(n,k{)}^2$. Moreover, we characterize all extremal pairs. Whereas the corresponding sum problem admits asymmetric and unbalanced extremizers, the product extremum forces a balanced, symmetric-or-dual structure: the two families are isomorphic when $n>2k$ and complement-dual when $n=2k$. Independently and contemporaneously with the present work, Frankl and Wang obtained the same bound for $k\ge 8$ and $n\ge 2k+1$ by a different method. Our proof combines a diversity technique with several new properties of an extended shift operation. Moreover, we show that the problem behaves differently for different uniformities, exhibiting new extremal configurations. In particular, we disprove a related conjecture proposed by Frankl and Wang.