The notion of cross intersecting set pair system of size $m$, $Big({A_i}_{i=1}^m, {B_i}_{i=1}^mBig)$ with $A_icap B_i=emptyset$ and $A_icap B_j eemptyset$, was introduced by Bollobas and it became an important tool of extremal combinatorics. His classical result states that $mle {a+bchoose a}$ 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_icap B_j|=1$ for $i e 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 $bigl(lfloorfrac{n}{2}rfloor+1bigr)bigl(lceilfrac{n}{2}rceil+1bigr)$ if $a=2$ and $b=nge 4$, -- at most $|cup_{i=1}^m A_i|$, -- asymptotically $n^2$ if ${A_i}$ is a linear hypergraph ($|A_icap A_j|le 1$ for $i e j$), -- asymptotically ${1over 2}n^2$ if ${A_i}$ and ${B_i}$ are both linear hypergraphs.
تحميل البحث