The maximum product of sizes of cross-intersecting families

Abstract

We say that a set $A$ $t$-intersects a set $B$ if $A$ and $B$ have at least $t$ common elements. Two families $\mathcal{A}$ and $\mathcal{B}$ of sets are said to be cross-$t$-intersecting if each set in $\mathcal{A}$ $t$-intersects each set in $\mathcal{B}$. A subfamily $\mathcal{S}$ of a family $\mathcal{F}$ is called a $t$-star of $\mathcal{F}$ if the sets in $\mathcal{S}$ have $t$ common elements. Let $l(\mathcal{F},t)$ denote the size of a largest $t$-star of $\mathcal{F}$. We call $\mathcal{F}$ a $(\le r)$-family if each set in $\mathcal{F}$ has at most $r$ elements. We determine a function $c:{\mathbb{N}}^3\to \mathbb{N}$ such that the following holds. If $\mathcal{A}$ is a subfamily of a $(\le r)$-family $\mathcal{F}$ with $l(\mathcal{F},t)\ge c(r,s,t)l(\mathcal{F},t+1)$, $\mathcal{B}$ is a subfamily of a $(\le s)$-family $\mathcal{G}$ with $l(\mathcal{G},t)\ge c(r,s,t)l(\mathcal{G},t+1)$, and $\mathcal{A}$ and $\mathcal{B}$ are cross-$t$-intersecting, then $|\mathcal{A}||\mathcal{B}|\le l(\mathcal{F},t)l(\mathcal{G},t)$. Some known results follow from this, and we identify several natural classes of families for which the bound is attained.

arXiv comment16 pages