The Erdős box problem asks for the largest size of a subset of
containing no Cartesian
product
in which every
has exactly two elements (Erdős 1964). Equivalently, it is an extremal problem
for complete
-partite
-uniform hypergraphs
with two vertices in every part.
For , Menezes (2026) constructed, for every power
of 2, a subset
of
of size
containing no such box. The whole grid partitions into
isomorphic box-free sets. For every
positive integer
, this gives
The known general upper bound has exponent , so the exact exponent in four dimensions remains
open.
Let
be the least positive integer
such that every
-coloring of
has a monochromatic box. The same construction gives
for powers of 2 and
for all integers
.