A Turan Problem for Cartesian Products of Hypergraphs

Abstract

Let $S$ and $T$ be sets with $|S|=m$ and $|T|=n$. Let $S_3,S_2$ and $T_3,T_2$ be the sets of all $3$-subsets ($2$-subsets) of $S$ and $T$, respectively. Define $Q((m,2,3),(n,2,3))$ as the smallest subset of $S_2\times T_2$ needed to cover all elements of $S_3\times T_3$. A more general version of this problem is initially defined, but the bulk of the investigation is devoted to studying this number. Its property as a lower bound for a planar crossing number is the reason for this focus.