The maximum size of the partial ground set of skew Bollobás systems

Abstract

A skew Bollobás system $\mathcal{P}=\{(A_i,B_i):1\le i\le m\}$ is a collection of pairs of disjoint subsets of $[n]$ such that $A_i\cap B_j\ne \varnothing$ for any $1\le i<j\le m$. Denote by $S_1(a,b)$ or $S_2(a,b)$ the maximum size of ${\bigcup }_{i=1}^m{A}_i$ or ${\bigcup }_{i=1}^m{B}_i$, respectively, over all possible skew Bollobás systems $\mathcal{P}=\{(A_i,B_i):1\le i\le m\}$ satisfying $|A_i|\le a$ and $|B_i|\le b$ for all $i\in [m]$. It is shown that for any non-negative integers $a$ and $b$, $S_1(a,b)=\left(\genfrac{}{}{0ex}{}{a+b+1}{a}\right)-1$ and $S_2(a,b)=\left(\genfrac{}{}{0ex}{}{a+b+1}{a+1}\right)-1$.

To appear in Acta Mathematica Hungarica