Skip to content
Preprint

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

Sep 2026 · 0 citations · 13 references
Mathematics

Abstract

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 $\Omega(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) = \Theta(n^{11/4})$. The construction is algebraic, defined over ${\bf F}_{q^3}$ via the power map $\tau(s) = s^{q^2-q+1}$. The proof shows that the direction-$1$ finite differences of $\tau$ partition ${\bf F}_{q^3}$ into pairwise skew affine lines over ${\bf F}_q$, preventing boxes from forming.

View source

Similar papers

Preprint Aug 2026

The Erd\H{o}s four-edge intersection problem

For an $n$-vertex graph $G$ and a permutation $\sigma$ of its vertex set, let $\sigma(G)$ denote the corresponding relabelling of $G$, and put \[ I_G(\sigma)=|E(G)\cap E(\sigma(G))|. \] Let $f(n,k)$ be the minimum number of edges in an $n$-vertex graph for which $I_G(\sigma)\geq k$ for every $\sigma$. In 1977 Erd\H{o}s...

Andrzej Żak · 0 citations
Preprint Sep 2026

The Erd\H{o}s--Hajnal hypergraph Ramsey problem for $r_4(6,n)$

The Ramsey number $r_k(s,n)$ is the smallest integer $N$ such that every $N$-vertex $k$-graph contains either a copy of $K_s^{(k)}$ or an independent set of size $n$. Erd\H{o}s and Hajnal conjectured that for every fixed $s>k\ge 4$, one has $r_k(s,n)\ge \operatorname{twr}_{k-1}(\Omega(n))$. This conjecture was independ...

Long-Ma Du, Xin-Yu Hu, Rui-Long Liu et al. · 0 citations
Preprint Aug 2026

An asymptotic solution to the Erd\H{o}s four-edge intersection problem

For an $n$-vertex graph $G$ and a permutation $\sigma$ of its vertex set, let $\sigma(G)$ denote the corresponding relabelling of $G$, and put $I_G(\sigma)=|E(G)\cap E(\sigma(G))|$. Let $f(n,k)$ be the minimum number of edges in an $n$-vertex graph for which $I_G(\sigma)\geq k$ for every $\sigma$. In his 1977 formulati...

Andrzej Żak · 0 citations
Preprint Oct 2026

The quadratic Brown--Erd\H{o}s--S\'os problem for 3-uniform hypergraphs with 8 and 9 edges

The famous and actively studied problem of Brown--Erd\H{o}s--S\'os from 1973 asks for $f^{(r)}(n;s,k)$, the maximum number of edges in an $r$-graph with $n$ vertices in which no $s$ vertices span $k$ or more edges. In this paper, we concentrate on the case $r=3$ and $s=k+2$, with $k\ge2$ fixed and $n\to\infty$; then it...

Levente Bodnár, O. Pikhurko, Shu-Min Sun et al. · 0 citations
Preprint Oct 2026

The $O(m^{2/3})$ error term for judicious partitions of 3-uniform hypergraphs

Let $k\ge2$ be a fixed integer. Bollob\'as and Scott proved that every $3$-uniform hypergraph with $m$ edges admits a partition of its vertex set into $k$ parts such that each part spans at most $m/k^3+O_k(m^{6/7})$ edges. Scott later suggested that the error term should be $O_k(m^{2/3})$. In this paper, we show that e...

Si-Wei Lin, Qing-Hou Zeng · 0 citations
Preprint Aug 2026

On the large-clique version of the Erd\H{o}s-S\'os theorem

For graphs $H$ and $F$, let $\operatorname{ex}(n,H,F)$ denote the maximum number of copies of $H$ in an $F$-free graph of order $n$. Motivated by the Erd\H{o}s-S\'{o}s theorem, Gerbner and Palmer and, independently, Zhao and Peng conjectured that for every tree $T$ of order $k$ and every $3\le r\le k-1,$ $$\operatornam...

Kun Cheng, Yu-Rui Tang · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.