On Turán problems for Cartesian products of graphs

Abstract

Let $A,B$ be disjoint sets of sizes $n$ and $m$. Let $\mathcal{Q}$ be a family of quadruples, having $2$ elements from $A$ and $2$ from $B$, such that any subset $S\subseteq A\cup B$ with $|S|=7$, $|S\cap A|\ge 2$ and $|S\cap B|\ge 2$ contains one of the quadruples. We prove that the smallest size of $\mathcal{Q}$ is $(1/16+O(1/n)+O(1/m))n^2{m}^2$ as $n,m\to \infty$. We also solve asymptotically a more general two-partite Turán problem for quadruples.

Changes suggested by the referees have been made

Cited by in corpus (1)

• On a question of Sidorenko