Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

On Families of Weakly Cross-intersecting Set-pairs

Kiraly Z., Nagy Z. L., Palvölgyi D., Visontai M.

Fundamenta Informaticae

2012

Vol. 117, nr 1-4

189-198

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 |A| = a, |B| = b, and A∩B = ∅. Furthermore, F is weakly crossintersecting if for any (Ai,Bi), (Aj ,Bj) ∈ F 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.