A cross-intersection theorem for subsets of a set

Abstract

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|≤∑i=1r(m−1i−1)∑j=1s(n−1j−1), and equality holds if A={A∈([m]≤r):1∈A} and B={B∈([n]≤s):1∈B}⁠.