The maximum product of weights of cross-intersecting families

preprint2015arXivOpen access

Abstract

Two families A\mathcal{A} and B\mathcal{B} of sets are said to be cross-tt-intersecting if each set in A\mathcal{A} intersects each set in B\mathcal{B} in at least tt elements. An active problem in extremal set theory is to determine the maximum product of sizes of cross-tt-intersecting subfamilies of a given family. We prove a cross-tt-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}r\in[n]=\{1,2,\dots,n\}, let ([n]r){[n]\choose r} be the family of rr-element subsets of [n][n], and let ([n]≤r){[n]\choose\leq r} be the family of subsets of [n][n] that have at most rr elements. Let Fn,r,t\mathcal{F}_{n,r,t} be the family of sets in ([n]≤r){[n]\choose\leq r} that contain [t][t]. We show that if g:([m]≤r)→R+g:{[m]\choose\leq r}\rightarrow\mathbb{R}^+ and h:([n]≤s)→R+h:{[n]\choose\leq s}\rightarrow\mathbb{R}^+ are functions that obey certain conditions, A⊆([m]≤r)\mathcal{A}\subseteq{[m]\choose\leq r}, B⊆([n]≤s)\mathcal{B}\subseteq{[n]\choose\leq s}, and A\mathcal{A} and B\mathcal{B} are cross-tt-intersecting, then ∑A∈Ag(A)∑B∈Bh(B)≤∑C∈Fm,r,tg(C)∑D∈Fn,s,th(D),\sum_{A\in\mathcal{A}}g(A)\sum_{B\in\mathcal{B}}h(B)\leq\sum_{C\in\mathcal{F}_{m,r,t}}g(C)\sum_{D\in\mathcal{F}_{n,s,t}}h(D), and equality holds if A=Fm,r,t\mathcal{A}=\mathcal{F}_{m,r,t} and B=Fn,s,t\mathcal{B}=\mathcal{F}_{n,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-tt-intersecting families A⊆([m]r)\mathcal{A}\subseteq{[m]\choose r} and B⊆([n]s)\mathcal{B}\subseteq{[n]\choose s} is (m−tr−t)(n−ts−t){m-t\choose r-t}{n-t\choose s-t} for min⁡{m,n}≥n0(r,s,t)\min\{m,n\}\geq n_0(r,s,t), where n0(r,s,t)n_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 generalisations for k≥2k\geq2 cross-tt-intersecting families, and Erdos-Ko-Rado-type results.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.