A cross-intersection theorem for subsets of a set

borg, peter;

A set of sets is called a family. Two families A and B are said to be cross-intersecting if each set in A intersects each set in B. For any two integers n and k with 1 <= k <= n, let ([n]<=k) denote the family of all subsets of {1, . . . , n} that have at most k elements. We show that if A is a subfamily of ([m]<=r), B is a subfamily of ([n]<=s), and A and B are cross-intersecting, then
|A||B| <= ri=1m − 1i − 1sj=1n − 1j − 1,
and equality holds if A = {A ∈([m]<=r): 1 ∈ A} and B = {B ∈([n]<=s)
: 1 ∈ B}.