Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Claim. Dean Menezes, The Three-Dimensional Erdős Box Problem Has Exponent 11/4, arXiv:2609.22381v2 (7 October 2026, 5 pages), writes z(n)z(n) for the largest number of edges of a tripartite 33-uniform hypergraph with nn vertices in each part and no box, a copy of K2,2,2(3)K^{(3)}_{2,2,2}. Theorem 1.1 (p. 1): for each q=2mq=2^m there is a box-free tripartite 33-uniform hypergraph with q4q^4 vertices in each part and q11q^{11} edges. Corollary 1.2 (p. 1): z(n)=Θ(n11/4)z(n)=\Theta(n^{11/4}). The lower bound z(n)≥q11>(n/16)11/4z(n)\ge q^{11}>(n/16)^{11/4} takes q=2⌊log⁡16n⌋q=2^{\lfloor\log_{16}n\rfloor} and pads each part with isolated vertices; the upper bound is Erdős's Theorem 1 of 1964. The construction (Construction 3.1, p. 3) takes k=Fqk=\mathbb F_q, K=Fq3K=\mathbb F_{q^3}, τ(s)=sq2−q+1\tau(s)=s^{q^2-q+1} and the trace Tr:K→k\mathrm{Tr}:K\to k. Each part is a copy of K×kK\times k, and (W,ω)(W,\omega), (Y,η)(Y,\eta), (Z,ζ)(Z,\zeta) form an edge when Tr(τ(Y+Z)W)+ω=E(Y,Z)+η+ζ\mathrm{Tr}(\tau(Y+Z)W)+\omega=E(Y,Z)+\eta+\zeta, with the offset E(Y,Z)=Tr(Y2qτ(Y+Z))E(Y,Z)=\mathrm{Tr}(Y^{2q}\tau(Y+Z)). Theorem 2.1 (p. 2) shows that τ\tau maps the fibers of δ(s)=τ(s+1)+τ(s)\delta(s)=\tau(s+1)+\tau(s) onto pairwise skew affine lines over kk; the argument needs characteristic 22 (Remark 2.2). In a box the four points τ(Yi+Zj)\tau(Y_i+Z_j) lie in an affine plane, so by Lemma 3.2 (p. 3) they sum to 00 while the four offsets E(Yi,Zj)E(Y_i,Z_j) do not sum to 00. Summing the four edge equations at one vertex of the first part then gives a contradiction. Section 4.1 adds Corollary 4.1: z(n,K2,2,s(3))=Θ(n11/4)z(n,K^{(3)}_{2,2,s})=\Theta(n^{11/4}) for each fixed s≥2s\ge2 (the paper writes tt for ss), since a box-free hypergraph contains no K2,2,s(3)K^{(3)}_{2,2,s}.

In the problem's letters (tt the uniformity, rr the class size) the box is K3(2)K_3(2). Each edge of a tripartite 33-graph meets each part once, so the two vertices of a class of a copy of K3(2)K_3(2) lie in one part and its three classes lie in different parts: every copy is a box (an observation made here). The hypergraph of Corollary 1.2 with ⌊n/3⌋\lfloor n/3\rfloor vertices in each part, plus isolated vertices, is therefore K3(2)K_3(2)-free on nn vertices, and ex3(n,K3(2))≥z(⌊n/3⌋)=Ω(n11/4)\mathrm{ex}_3(n,K_3(2))\ge z(\lfloor n/3\rfloor)=\Omega(n^{11/4}). This is the instance (t,r)=(3,2)(t,r)=(3,2) of the modified Statement, ex3(n,K3(2))≥n3−2−2−o(1)\mathrm{ex}_3(n,K_3(2))\ge n^{3-2^{-2}-o(1)}, in the form Ω(n11/4)\Omega(n^{11/4}).

Covers. The instance (t,r)=(3,2)(t,r)=(3,2) of the modified Statement of Problem 1158, answered yes. It is the first instance with t≥3t\ge3; the earlier lower bounds for t=3t=3 reach only Ω(n8/3)\Omega(n^{8/3}). The instances (2,2)(2,2) and (2,3)(2,3) are the refereed claims of Problem 714. Nothing for t=3t=3 with r≥3r\ge3, for t≥4t\ge4, or for t=2t=2 with r≥4r\ge4. The paper's open questions 1 and 2 (Section 4.2) ask about t=3t=3 with r≥3r\ge3 and about r=2r=2 with t≥4t\ge4. The problem stays open.

Depends on. No page of this wiki. The construction and the proof of Theorem 1.1 are self-contained. Erdős's upper bound enters only the Θ\Theta of Corollary 1.2, not the instance, which asks for the lower bound alone.

Postings. arXiv:2609.22381, v1 of 18 September 2026 (7 pages) and v2 of 7 October 2026 (5 pages). Both state Theorem 1.1 and Corollaries 1.2 and 4.1, and this page follows v2. Version 2 drops the term N(Y)N(Y), the field norm of YY, from v1's offset E(Y,Z)=N(Y)+Tr(Y2qτ(Y+Z))E(Y,Z)=N(Y)+\mathrm{Tr}(Y^{2q}\tau(Y+Z)). That changes the hypergraph only by the relabeling η↦η+N(Y)\eta\mapsto\eta+N(Y) of the second part (an observation made here). Version 2 also merges v1's Lemmas 3.2 and 3.3 into one direct computation, states Theorem 2.1 without v1's explicit lines c2/N(c)+ckc^2/N(c)+ck, writes out the padding in Corollary 1.2, and drops v1's Section 4.2 on the octahedron problem for graphs.

Standing. Claimed: an arXiv preprint with no refereed version, Lean proof or outside review known to this corpus. The proofs of Theorem 2.1, Lemma 3.2, Theorem 1.1 and Corollary 1.2 in v2 were checked step by step here; that check is author-recorded, not independent review. The erdosproblems.com page for the problem was last edited on 23 January 2026, before the result, and no proof claim on erdosproblems.com records it; Bloom's catalog labeled the problem OPEN.