Recently, Domagoj Brada\v{ c}, Oliver Janzer, Benny Sudakov and Istv\'an Tomon have proved that the Tur\'an number of $2$-dimensional grids is $\Theta(n^{ 3/2})$, or more general, $\mathrm{ ex}\left(n,T\square{ P}\right)=\Theta(n^{ 3/2})$, where $T$ is a non-trivial tree, $P$ is a non-trivial path, and $T\square{ P}$ denotes the Cartesian product. In their proof, they exhibited a novel way of using the tensor power trick, which has lots of potential in Tur\'an type problems. By the end of their proof, they conjectured that $\mathrm{ ex}\left(n,T\square{ R}\right)=\Theta(n^{ 3/2})$ for non-trivial trees $T$ and $R$. This paper is an extension based on their work, we successfully prove the above conjecture by adapting their approach.

Categories: math.CO

The Tur\'an number of the Cartesian product of graphs