TOPICS
Search

Erdős Box Problem


The Erdős box problem asks for the largest size f_r(n) of a subset of {1,...,n}^r containing no Cartesian product A_1×...×A_r in which every A_i has exactly two elements (Erdős 1964). Equivalently, it is an extremal problem for complete r-partite r-uniform hypergraphs with two vertices in every part.

For r=4, Menezes (2026) constructed, for every power q>=2 of 2, a subset of {1,...,q^5}^4 of size q^(19) containing no such box. The whole grid partitions into q isomorphic box-free sets. For every positive integer n, this gives

 f_4(n)>=2^(-19/20)n^(19/5).

The known general upper bound has exponent 31/8, so the exact exponent in four dimensions remains open.

Let R_4(c) be the least positive integer n such that every c-coloring of {1,...,n}^4 has a monochromatic box. The same construction gives R_4(q)>q^5 for powers of 2 and R_4(c)>c^5/32 for all integers c>=2.


See also

Hypergraph, Ramsey Theory

Explore with Wolfram|Alpha

References

Erdős, P. "On Extremal Problems of Graphs and Generalized Graphs." Israel J. Math. 2, 183-190, 1964. https://doi.org/10.1007/BF02759942.Menezes, D. M. "A 19/5 Lower Bound for the Four-Dimensional ErdŐs Box Problem." 11 Nov 2026. https://arxiv.org/abs/2611.17378v1.

Cite this as:

Weisstein, Eric W. "Erdős Box Problem." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/ErdosBoxProblem.html

Subject classifications