The maximum sum of sizes of cross-intersecting families of subsets of a set

Abstract

A set of sets is called a family. Two families A and B of sets are said to be cross-intersecting if each member of A intersects each member of B. For any two integers n and k with 1≤ k≤ n, let ([n]/≤ k) denote the family of subsets of [n] = {1, . . . ., n} that have at most k elements. We show that if A is a non-empty subfamily of ([n] ≤ r), B is a non-empty subfamily of ([n]/≤ s), r≤ s, and A and ≤ are cross-intersecting, then |A|+|B|≤ 1+Σ((n/i)-(n-r/i)), and equality holds if A ={[r]} and B is the family of sets in ([n]/≤s) that intersect [r].