The Turán number of the grid

Abstract

For a positive integer t$t$, let Ft$F_t$ denote the graph of the txt$t\times t$ grid. Motivated by a 50-year-old conjecture of Erdos about Turan numbers of r$r$-degenerate graphs, we prove that there exists a constant C=C(t)$C=C(t)$ such that ex(n,Ft)<= Cn3/2$\mathrm{ex}(n,F_t)\leqslant Cn<^>{3/2}$. This bound is tight up to the value of C$C$. One of the interesting ingredients of our proof is a novel way of using the tensor power trick.