Combinatorial Nullstellensatz and Turán numbers of complete $r$-partite $r$-uniform hypergraphs

Abstract

In this note we describe how Lasoń's generalization of Alon's Combinatorial Nullstellensatz gives a framework for constructing lower bounds on the Turán number $\mathrm{ex}(n,K_{s_1,\dots ,s_r}^{(r)})$ of the complete $r$-partite $r$-uniform hypergraph $K_{s_1,\dots ,s_r}^{(r)}$. To illustrate the potential of this method, we give a short and simple explicit construction for the Erdős box problem, showing that $\mathrm{ex}(n,K_{2,\dots ,2}^{(r)})=\Omega (n^{r-1/r})$, which asymptotically matches best known bounds when $r\le 4$.

3 pages