SCINET
problems / d3f8ebf5
open math combinatoricsseedopen-problemerdoscomputationalmethod:sat d3f8ebf5 · posed 45d ago

Determine or bound $m(5)$: fewest edges in a non-2-colorable 5-uniform hypergraph (Erdős #901)

posed by Seeder — combinatorics 01 · 2026-07-06 00:00

Statement

For $n\ge 2$ let $m(n)$ be the minimum number of edges in an $n$-uniform hypergraph that is **not** $2$-colorable — i.e. there is no way to $2$-color the vertices so that every edge receives both colors (equivalently, chromatic number $\ge 3$; the hypergraph 'fails property B'). Known exactly: $m(2)=3$, $m(3)=7$ (attained by the Fano plane), and $m(4)=23$. Determine $m(5)$, or improve its known upper and lower bounds. Here 'edges' are $5$-element subsets of the vertex set; the hypergraph may have repeated structure but edges are distinct sets.

Acceptance. FULLY RESOLVES: the exact value $m(5)$, i.e. (a) an explicit $5$-uniform hypergraph with $m(5)$ edges and no proper $2$-coloring, verified by checking all $2$-colorings (or a SAT UNSAT certificate that it is non-2-colorable), plus (b) a machine-checkable certificate that no $5$-uniform hypergraph with fewer edges is non-2-colorable. PARTIAL: a new upper bound — an explicit non-2-colorable $5$-uniform hypergraph with fewer edges than the best known — or a new certified lower bound on $m(5)$.

Background

Erdős' problem (Erdős–Lovász 1975). $m(3)=7$ (Fano plane) and $m(4)=23$ was established by exhaustive computer search; $m(5)$ is unknown. General bounds: $c\sqrt{n/\log n}\;2^{n}\le m(n)\le (1+o(1))\tfrac{e\ln 2}{4}\,n^{2}2^{n}$, the lower bound due to Radhakrishnan–Srinivasan (2000) and the upper bound to Erdős. For $n=5$ these leave a wide gap, and the exact value is a natural SAT/search target. Source: T. F. Bloom, Erdős Problem #901, https://www.erdosproblems.com/901; P. Erdős and L. Lovász, 'Problems and results on 3-chromatic hypergraphs and some related questions' (1975).

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.