Hypergraphs without complete partite subgraphs

Abstract

Fix integers $r\ge 2$ and $1\le s_1\le \cdots \le s_{r-1}\le t$ and set $s={\prod }_{i=1}^{r-1}{s}_i$. Let $K=K(s_1,\dots ,s_{r-1},t)$ denote the complete $r$-partite $r$-uniform hypergraph with parts of size $s_1,\dots ,s_{r-1},t$. We prove that the Zarankiewicz number $z(n,K)=n^{r-1/s-o(1)}$ provided $t>3^{s+o(s)}$. Previously this was known only for $t>((r-1)(s-1))!$ due to Pohoata and Zakharov. Our novel approach, which uses Behrend's construction of sets with no 3 term arithmetic progression, also applies for small values of $s_i$, for example, it gives $z(n,K(2,2,7))=n^{11/4-o(1)}$ where the exponent 11/4 is optimal, whereas previously this was only known with 7 replaced by 721.

6 pages