On sizes of 1-cross intersecting set pair systems

2021/04/17 by Kostochka, Alexandr V., McCourt, Grace, Nahvi, Mina
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2104.08562

Abstract

Let \(A_i,B_i)\_i=1^m be a set pair system. Füredi, Gyárfás and Király called it \em 1-cross intersecting if |A_i∩ B_j| is 1 when i≠ j and 0 if i=j. They studied such systems and their generalizations, and in particular considered m(a,b,1) -- the maximum size of a 1-cross intersecting set pair system in which |A_i|≤ a and |B_i|≤ b for all i. Füredi, Gyárfás and Király proved that m(n,n,1)≥ 5^(n-1)/2 and asked whether there are upper bounds on m(n,n,1) significantly better than the classical bound 2n\choose n of Bollob' as for cross intersecting set pair systems. Answering one of their questions, Holzman recently proved that if a,b≥ 2, then m(a,b,1)≤ (29)/(30)\binoma+ba. He also conjectured that the factor (29)/(30) in his bound can be replaced by (5)/(6). The goal of this paper is to prove this bound.

Related

• Problems and results on 1-cross intersecting set pair systems
• A bound for 1-cross intersecting set pair systems
• Disjoint pairs in set systems with restricted intersection
• Union-intersecting set systems
• The maximum product of sizes of cross-t-intersecting uniform families