The Brown-Erdős-Sós conjecture asserts that for each integer
and real number
, every 3-uniform hypergraph
on sufficiently many vertices
with at least
hyperedges contains
distinct hyperedges whose union
has at most
vertices (Brown et al. 1973).
The case
is the Ruzsa-Szemerédi theorem.
The conjecture remains open in general (Conlon et al. 2023, Shapira and Tyomkyn
2025). The corresponding
-uniform formulation for
replaces the vertex bound by
.
Kong et al. (2026) constructed 3-uniform hypergraphs on vertices with at least
hyperedges,
for some absolute constant
and all sufficiently large
, in which every six distinct hyperedges
span at least ten vertices. This gives the
case of the companion conjecture that the maximum number
of hyperedges avoiding the configuration is at least
for each fixed
.
The conjectured
upper bound for
remains open.
The same construction also gives the lower bound in the cases
, 10, and 11 of the companion conjecture for 3-uniform
hypergraphs. For every fixed uniformity
, Kong et al. (2026, Theorem 1.3)
also give
-uniform
hypergraphs with at least
hyperedges in which
no six distinct hyperedges span at most
vertices.
This is problem 1178 in the Erdős problems collection (Bloom 2026).