The Three-Dimensional Erdős Box Problem Has Exponent $11/4$

Abstract

Let $z(n)$ be the maximum number of edges in a tripartite $3$-uniform hypergraph with $n$ vertices in each part and no copy of $K_{2,2,2}^{(3)}$ (a ``box''). Erdős (1964) proved that $z(n)=O(n^{11/4})$, whereas the best previous lower bound, due to Katz, Krop, and Maggioni (2002), was $\Omega (n^{8/3})$. For each $q=2^m$, we construct a box-free hypergraph with $q^4$ vertices in each part and $q^{11}$ edges, showing that $z(n)=\Theta (n^{11/4})$. The construction uses the power map $\tau (s)=s^{q^2-q+1}$ on $\F_{q^3}$, which sends the fibers of $s\mapsto \tau (s+1)+\tau (s)$ to pairwise skew affine lines over $\F_q$.

arXiv comment5 pages