On Families of Weakly Cross-intersecting Set-pairs

Abstract

Let ℱ be a family of pairs of sets. We call it an (a, b)-set system if for every set-pair (A,B) in ℱ we have that |A| = a, |B| = b, and A ∩ B = Ø. Furthermore, ℱ is weakly cross-intersecting if for any (A_i, B_i), (A_j, B_j) ∈ ℱ with i ≠ j we have that A_i ∩ B_j and A_j ∩ B_i are not both empty. We investigate the maximum possible size of weakly cross-intersecting (a, b)-set systems. We give an explicit construction for the best known asymptotic lower bound. We introduce a fractional relaxation of the problem and prove that the best known upper bound is optimal for this case. We also provide the exact value for the case when a = b = 2.