Affiliations: Department of Computer Science, Eötvös University Budapest, Pázmány Péter sétány 1/C. H-1117 Hungary, kiraly@cs.elte.hu; nagyzoltanlorant@gmail.com; dom@cs.elte.hu | Department of Mathematics, University of Pennsylvania, 209 S. 33rd Street, Philadelphia, PA 19104 USA, mirko@math.upenn.edu
Note: [] Research of Z.K. was partially supported by grants (no. CNK 77780 and no. CK 80124) from the National Development Agency of Hungary, based on a source from the Research and Technology Innovation Fund, and also by TÁMOP grant 4.2.1./B-09/1/KMR-2010-0003.
Note: [] Research of Z.L.N. was supported by the Hungarian National Foundation for Scientific Research (OTKA), Grant no. K 81310.
Note: [] Research of D.P. was partially supported by grant no. CNK 77780 from the National Development Agency of Hungary, based on a source from the Research and Technology Innovation Fund and TÁMOP grant 4.2.1./B-09/1/KMR-2010-0003.
Note: [] Research of M.V. was supported by the Benjamin Franklin Fellowship of the University of Pennsylvania. Address for correspondence: Department of Mathematics, University of Pennsylvania, 209 S. 33rd Street, Philadelphia, PA 19104 USA
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 (Ai, Bi), (Aj, Bj) ∈ ℱ with i ≠ j we have that Ai ∩ Bj and Aj ∩ Bi 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.
