2015/12/30 by Borg, Peter · 3 citations
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1512.09108
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]\choose r be the family of r-element subsets of [n], and let [n]\choose≤ 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]\choose≤ r that contain [t]. We show that if g:[m]\choose≤ r→ℝ+ and h:[n]\choose≤ s→ℝ+ are functions that obey certain conditions, A⊆[m]\choose≤ r, B⊆[n]\choose≤ s, and A and B are cross-t-intersecting, then ∑A\inAg(A)∑B\inBh(B)≤∑_C\inFm,r,tg(C)∑_D\inFn,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]\choose r and B⊆[n]\choose s is m-t\choose r-tn-t\choose s-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.