On Families of Weakly Cross-intersecting Set-pairs
Let F be a family of pairs of sets. We call it an (a, b)-set system if for every set-pair (A, B) in F we have that vertical bar A vertical bar = a, vertical bar B vertical bar = b, and A boolean AND B = empty set. Furthermore, F is weakly cross-intersecting if for any (A(i), B-i), (A(j), B-j) is an element of F with i not equal j we have that A(i) boolean AND B-j and A(j) boolean AND 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.
cross-intersecting set-pairs lattice paths