A bound for 1-cross intersecting set pair systems. (August 2021)

• Record Type: Journal Article
• Authors: Holzman, Ron
• Is Part Of: European journal of combinatorics. Volume 96(2021)
• Publication Date: 2021-08
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2021.103345
• Languages: English
• ISSNs: 0195-6698

Abstract

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.