A sharp bound for the product of weights of cross-intersecting families

Abstract

Two families A and B of sets 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 subsets of {1,…,n} of size at most k, and let S n,k denote the family of sets in ([n]≤k) that contain 1. The author recently showed that if A⊆([m]≤r), B⊆([n]≤s), and A and B are cross-intersecting, then |A||B|≤Sm,r||Sn,s|. We prove a version of this result for the more general setting of \emph{weighted} sets. We show that if g:([m]≤r)→R+ and h:([n]≤s)→R+ are functions that obey certain conditions, A⊆([m]≤r), B⊆([n]≤s), and A and B are cross-intersecting, then∑A∈A g(A)∑B∈B h(B)≤∑C∈Sm,r g(C)∑D∈Sn,s h(D). The bound is attained by taking A=Sm,r and B=Sn,s. We also show that this result yields new sharp bounds for the product of sizes of cross-intersecting families of integer sequences and of cross-intersecting families of multisets.