On sizes of 1-cross intersecting set pair systems

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\cap B_j|$ is $1$ when $i\ne 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|\le a$ and $|B_i|\le b$ for all $i$. Füredi, Gyárfás and Király proved that $m(n,n,1)\ge 5^{(n-1)/2}$ and asked whether there are upper bounds on $m(n,n,1)$ significantly better than the classical bound $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$ of Bollob\' as for cross intersecting set pair systems. Answering one of their questions, Holzman recently proved that if $a,b\ge 2$, then $m(a,b,1)\le \frac{29}{30}\left(\genfrac{}{}{0ex}{}{a+b}{a}\right)$. He also conjectured that the factor $\frac{29}{30}$ in his bound can be replaced by $\frac{5}{6}$. The goal of this paper is to prove this bound.