A bound for 1-cross intersecting set pair systems. (August 2021) - Holzman, Ron
Abstract: A well-known result of Bollobás says that if { ( A i, B i ) } i = 1 m is a set pair system such that | A i | ≤ a and | B i | ≤ b for 1 ≤ i ≤ m, and A i ∩ B j ≠ 0̸ if and only if i ≠ j, then m ≤ a + b a . Füredi, Gyárfás and Király recently initiated the study of such systems with the additional property that | A i ∩ B j | = 1 for all i ≠ j . Confirming a conjecture of theirs, we show that this extra condition allows an improvement of the upper bound (at least) by a constant factor.