The Three-Dimensional Erd\H{o}s Box Problem Has Exponent 11/4

Dean Menezes

In the authors' words

The Zarankiewicz problem for $3$ -uniform hypergraphs asks for the maximum number $z (n)$ of edges in a tripartite hypergraph with $n$ vertices in each part containing no copy of $K_{2, 2, 2}^{(3)}$ (a "box"). Erd\H{o}s (1964) proved $z (n) = O (n^{11/4})$ . The best previously known lower bound was $Ω (n^{8/3})$ , due to Katz, Krop, and Maggioni (2002). We construct a family of box-free hypergraphs matching Erd\H{o}s's upper bound: for each $q = 2^{m}$ ( $m \geq 1$ ), our hypergraph has $q^{4}$ vertices in each part and $q^{11}$ edges, establishing that $z (n) = Θ (n^{11/4})$ . The construction is algebraic, defined over $F_{q^{3}}$ via the power map $τ (s) = s^{q^{2} - q + 1}$ . The proof shows that the direction- $1$ finite differences of $τ$ partition $F_{q^{3}}$ into pairwise skew affine lines over $F_{q}$ , preventing boxes from forming.

Main resultThe abstract does not state a limitation.

The Three-Dimensional Erd\H{o}s Box Problem Has Exponent 11/4

In the authors' words

More on Combinatorics & discrete math that day

Circular s-choice parking functions: an exact closed formula via rotational symmetry

Single-Fragment Forensic Coding via Multidimensional Cyclically Permutable Codes

The Deterministic Broadcast Channel Revisited: A Bipartite Graph Approach

Proof of Almkvist's conjecture on the unimodality of partition polynomials

On infinite families of [Pn​]-irregular graphs

The Three-Dimensional Erd\H{o}s Box Problem Has Exponent $11/4$

On infinite families of $[P_{n}]$ -irregular graphs