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 -