On Sizes of 1-Cross Intersecting Set Pair Systems

A. V. Kostochka, G. McCourt, M. Nahvi

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)842-849
Number of pages8
JournalSiberian Mathematical Journal
Issue number5
StatePublished - Sep 2021


  • 519.101
  • cross intersecting systems
  • edge partitions
  • set pair system

ASJC Scopus subject areas

  • General Mathematics


Dive into the research topics of 'On Sizes of 1-Cross Intersecting Set Pair Systems'. Together they form a unique fingerprint.

Cite this