The maximum product of weights of cross‐intersecting families

A set of sets is called a family . Two families A and B 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. This incorporates the classical Erdös–Ko–Rado (EKR) problem. 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 ] rbe the family of r ‐element subsets of [ n ] , and let[ n ] ≤ rbe the family of subsets of [ n ] that have at most r elements. Let F n , r , tbe the family of sets in[ n ] ≤ rthat 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 ∈ A g ( A ) ∑ B ∈ B h ( B ) ≤ ∑ C ∈ F m , r , tg ( C ) ∑ D ∈ F n , s , th ( D ) , and equality holds if A = F m , r , tand B = F n , s , t. We prove this in a more general setting and characterize the cases of equality. We use the result to show that the maximum product of sizes of two cross‐ t ‐intersecting families A ⊆[ m ] rand B ⊆[ n ] sism - t r - tn - t s - tfor min { m , n } ⩾ n 0 ( r , s , t ) , wheren 0 ( 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 generalizations for k ⩾ 2 cross‐ t ‐intersecting families, and EKR‐type results.