A bound for 1-cross intersecting set pair systems

2020/11/01 by Holzman, Ron
#05D05 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2011.00528

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 ≠ ∅ if and only if i ≠ j, then m ≤ a+b \choose 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.

Related

• Problems and results on 1-cross intersecting set pair systems
• On sizes of 1-cross intersecting set pair systems
• Disjoint pairs in set systems with restricted intersection
• Uniform s-cross-intersecting families
• Some new Bollobás-type inequalities