TY - JOUR

T1 - On Sizes of 1-Cross Intersecting Set Pair Systems

AU - Kostochka, A. V.

AU - McCourt, G.

AU - Nahvi, M.

N1 - Publisher Copyright:
© 2021, Pleiades Publishing, Ltd.

PY - 2021/9

Y1 - 2021/9

N2 - Let $ \{(A_{i},B_{i})\}_{i=1}^{m} $ be a set pair system. Füredi, Gyárfás, and Királycalled it $ 1 $-cross intersecting if $ |A_{i}\cap B_{j}| $ is $ 1 $when $ i\neq j $ and $ 0 $ if $ i=j $. They studied the systems and theirgeneralizations and, in particular, considered $ m(a,b,1) $, the maximum size ofa $ 1 $-cross intersecting set pair system in which $ |A_{i}|\leq a $ and $ |B_{i}|\leq b $ for all $ i $. Füredi, Gyárfás, and Király proved that$ m(n,n,1)\geq 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} $ ofBollobás for cross intersecting set pair systems.Answering one of their questions, Holzman proved recently that if $ a,b\geq 2 $,then$ m(a,b,1)\leq\frac{29}{30}\binom{a+b}{a} $. He also conjectured that the factor$ \frac{29}{30} $ in his bound can be replaced by$ \frac{5}{6} $. Our goal is to prove this bound.

AB - Let $ \{(A_{i},B_{i})\}_{i=1}^{m} $ be a set pair system. Füredi, Gyárfás, and Királycalled it $ 1 $-cross intersecting if $ |A_{i}\cap B_{j}| $ is $ 1 $when $ i\neq j $ and $ 0 $ if $ i=j $. They studied the systems and theirgeneralizations and, in particular, considered $ m(a,b,1) $, the maximum size ofa $ 1 $-cross intersecting set pair system in which $ |A_{i}|\leq a $ and $ |B_{i}|\leq b $ for all $ i $. Füredi, Gyárfás, and Király proved that$ m(n,n,1)\geq 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} $ ofBollobás for cross intersecting set pair systems.Answering one of their questions, Holzman proved recently that if $ a,b\geq 2 $,then$ m(a,b,1)\leq\frac{29}{30}\binom{a+b}{a} $. He also conjectured that the factor$ \frac{29}{30} $ in his bound can be replaced by$ \frac{5}{6} $. Our goal is to prove this bound.

KW - 519.101

KW - cross intersecting systems

KW - edge partitions

KW - set pair system

UR - http://www.scopus.com/inward/record.url?scp=85115612145&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85115612145&partnerID=8YFLogxK

U2 - 10.1134/S0037446621050062

DO - 10.1134/S0037446621050062

M3 - Article

AN - SCOPUS:85115612145

SN - 0037-4466

VL - 62

SP - 842

EP - 849

JO - Siberian Mathematical Journal

JF - Siberian Mathematical Journal

IS - 5

ER -