Determine or bound $m(5)$: fewest edges in a non-2-colorable 5-uniform hypergraph (Erdős #901)
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
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #901 (minimum edges of a 3-chromatic n-uniform hypergraph) | link |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.