The maximum product of weights of cross-intersecting families

Abstract

Two families $\mathcal{A}$ and $\mathcal{B}$ of sets are said to be cross-$t$-intersecting if each set in $\mathcal{A}$ intersects each set in $\mathcal{B}$ in at least $t$ elements. An active problem in extremal set theory is to determine the maximum product of sizes of cross-$t$-intersecting subfamilies of a given family. We prove a cross-$t$-intersection theorem for weighted subsets of a set by means of a new subfamily alteration method, and use the result to provide solutions for three natural families. For $r\in [n]=\{1,2,\dots ,n\}$, let $\left(\genfrac{}{}{0ex}{}{[n]}{r}\right)$ be the family of $r$-element subsets of $[n]$, and let $\left(\genfrac{}{}{0ex}{}{[n]}{\le r}\right)$ be the family of subsets of $[n]$ that have at most $r$ elements. Let ${\mathcal{F}}_{n,r,t}$ be the family of sets in $\left(\genfrac{}{}{0ex}{}{[n]}{\le r}\right)$ that contain $[t]$. We show that if $g:\left(\genfrac{}{}{0ex}{}{[m]}{\le r}\right)\to {\mathbb{R}}^{+}$ and $h:\left(\genfrac{}{}{0ex}{}{[n]}{\le s}\right)\to {\mathbb{R}}^{+}$ are functions that obey certain conditions, $\mathcal{A}\subseteq \left(\genfrac{}{}{0ex}{}{[m]}{\le r}\right)$, $\mathcal{B}\subseteq \left(\genfrac{}{}{0ex}{}{[n]}{\le s}\right)$, and $\mathcal{A}$ and $\mathcal{B}$ are cross-$t$-intersecting, then \[\sum_{A\in\mathcal{A}}g(A)\sum_{B\in\mathcal{B}}h(B)\leq\sum_{C\in\mathcal{F}_{m,r,t}}g(C)\sum_{D\in\mathcal{F}_{n,s,t}}h(D),\] and equality holds if $\mathcal{A}={\mathcal{F}}_{m,r,t}$ and $\mathcal{B}={\mathcal{F}}_{n,s,t}$. We prove this in a more general setting and characterise the cases of equality. We use the result to show that the maximum product of sizes of two cross-$t$-intersecting families $\mathcal{A}\subseteq \left(\genfrac{}{}{0ex}{}{[m]}{r}\right)$ and $\mathcal{B}\subseteq \left(\genfrac{}{}{0ex}{}{[n]}{s}\right)$ is $\left(\genfrac{}{}{0ex}{}{m-t}{r-t}\right)\left(\genfrac{}{}{0ex}{}{n-t}{s-t}\right)$ for $\min \{m,n\}\ge n_0(r,s,t)$, where $n_0(r,s,t)$ is close to best possible. We obtain analogous results for families of integer sequences and for families of multisets. The results yield generalisations for $k\ge 2$ cross-$t$-intersecting families, and Erdos-Ko-Rado-type results.

arXiv comment33 pages. arXiv admin note: text overlap with arXiv:1212.6955