The maximum product of sizes of cross-intersecting families

Abstract

A set of sets is called a family. Two families A and B are said to be cross-t-intersecting if each set in A intersects each set in B in at least t elements. For a family F, let l(F, t) denote the size of a largest subfamily of F whose sets have at least t common elements. We call F a (≤ r)-family if each set in F has at most r elements. We show that for any positive integers r, s and t, there exists an integer c(r, s, t) such that the following holds. If A is a subfamily of a (≤ r)-family F with l(F, t) ≥ c(r, s, t)l(F, t + 1), B is a subfamily of a (≤ s)-family G with l(G, t) ≥ c(r, s, t)l(G, t +1), and A and B are cross-t-intersecting, then |A||B| ≤ l(F, t)l(G, t). We give c(r, s, t) explicitly. Some known results follow from this, and we identify several natural classes of families for which the bound is attained.