Math Conjectures

Brown–Erdős–Sós Conjecture

OPENLandmarkConjectureProposed 1973 · Standard version

Canonical statement

For every integer k≥3k\geq3 and every real δ>0\delta>0, there is an integer n0=n0(k,δ)n_0=n_0(k,\delta) such that every 33-uniform hypergraph H=(V,E)H=(V,E) with ∣V∣=n≥n0|V|=n\geq n_0 and ∣E∣≥δn2|E|\geq\delta n^2 has distinct edges e1,…,eke_1,\ldots,e_k satisfying
∣e1∪⋯∪ek∣≤k+3. \bigl|e_1\cup\cdots\cup e_k\bigr|\leq k+3.
Here 33-uniform means that every edge has exactly three vertices.
View source LaTeX
For every integer \(k\geq3\) and every real
\(\delta>0\), there is an integer \(n_0=n_0(k,\delta)\) such that every
\(3\)-uniform hypergraph \(H=(V,E)\) with \(|V|=n\geq n_0\) and
\(|E|\geq\delta n^2\) has distinct edges
\(e_1,\ldots,e_k\) satisfying
\[
  \bigl|e_1\cup\cdots\cup e_k\bigr|\leq k+3.
\]
Here \(3\)-uniform means that every edge has exactly three vertices.
COMB-014:[BrownErdosSos1973][RuzsaSzemeredi1978][SantosTyomkyn2025BES]
CombinatoricsGraph theory

Notes

The case k=3k=3 is the Ruzsa--Szemerédi (6,3)(6,3)-theorem. The conjecture remains open for every general k≥4k\geq4; recent dense-case progress does not cover arbitrary positive δ\delta.
This is the dense (k+3,k)(k+3,k) conjecture, not the distinct Brown--Erdős--Sós limit-existence problem for (k+2,k)(k+2,k).

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.