Problems and results on 1-cross intersecting set pair systems

Abstract

The notion of cross intersecting set pair system of size $m$, $(\{A_i{\}}_{i=1}^m,\{B_i{\}}_{i=1}^m)$ with $A_i\cap B_i=\varnothing$ and $A_i\cap B_j\ne \varnothing$, was introduced by Bollobás and it became an important tool of extremal combinatorics. His classical result states that $m\le \left(\genfrac{}{}{0ex}{}{a+b}{a}\right)$ if $|A_i|\le a$ and $|B_i|\le b$ for each $i$. Our central problem is to see how this bound changes with the additional condition $|A_i\cap B_j|=1$ for $i\ne j$. Such a system is called $1$-cross intersecting. We show that the maximum size of a $1$-cross intersecting set pair system is -- at least $5^{n/2}$ for $n$ even, $a=b=n$, -- equal to $(\lfloor \frac{n}{2}\rfloor +1)(\lceil \frac{n}{2}\rceil +1)$ if $a=2$ and $b=n\ge 4$, -- at most $|{\cup }_{i=1}^m{A}_i|$, -- asymptotically $n^2$ if $\{A_i\}$ is a linear hypergraph ($|A_i\cap A_j|\le 1$ for $i\ne j$), -- asymptotically $\frac{1}{2}{n}^2$ if $\{A_i\}$ and $\{B_i\}$ are both linear hypergraphs.