The maximum product of weights of cross-intersecting families

Abstract

Two families A and B of sets are said to be cross-t-intersecting if each set in A intersects each set in B in at least t elements. An active problem in extremal set theory is to determine the maximum product of sizes of cross-t-intersecting subfamilies of a given family. We prove a cross-t-intersection theorem for weighted subsets of a set by means of a new subfamily alteration method, and use the result to provide solutions for three natural families. For r∈[n]={1,2,…,n}, let ([n]r) be the family of r-element subsets of [n], and let ([n]≤r) be the family of subsets of [n] that have at most r elements. Let Fn,r,t be the family of sets in ([n]≤r) that contain [t]. 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-t-intersecting, then ∑A∈Ag(A)∑B∈Bh(B)≤∑C∈Fm,r,tg(C)∑D∈Fn,s,th(D), and equality holds if A=Fm,r,t and B=Fn,s,t. We prove this in a more general setting and characterise the cases of equality. We use the result to show that the maximum product of sizes of two cross-t-intersecting families A⊆([m]r) and B⊆([n]s) is (m−tr−t)(n−ts−t) for min{m,n}≥n0(r,s,t), where n0(r,s,t) is close to best possible. We obtain analogous results for families of integer sequences and for families of multisets. The results yield generalisations for k≥2 cross-t-intersecting families, and Erdos-Ko-Rado-type results.