The Three-Dimensional Erdős Box Problem Has Exponent $11/4$
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 $Ω(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) = Θ(n^{11/4})$. The construction uses the power map $τ(s) = s^{q^2-q+1}$ on $\F_{q^3}$, which sends the fibers of $s \mapsto τ(s+1) + τ(s)$ to pairwise skew affine lines…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.22381
curl -X POST /api/v1/records/arxiv/2609.22381/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.22381/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'