Nešetřil–Rödl–Sales Hall-ratio question
For every integer , is every nonempty finite -uniform hypergraph satisfying necessarily -colourable; equivalently, does imply , where ?
References
- Hypergraphs with the smallest Hall ratio are still hard to colour — arXiv — Veronica Bitonti, Freddie Illingworth, Pedram Noohi, Jane Tan
Source: arXiv
Progress summary
An unrefereed preprint claims to disprove the proposed connection between Hall ratio and easy colouring in every higher uniformity.
The Nešetřil–Rödl–Sales question asks whether a strong independence-number guarantee, expressed through the Hall ratio, forces low chromatic complexity for hypergraphs. The reported construction gives a negative answer uniformly in higher uniformities.
Recent negative answer (date not stated)
Veronica Bitonti, Freddie Illingworth, Pedram Noohi, and Jane Tan claim that hypergraphs with the smallest Hall ratio can nevertheless remain hard to colour. Their preprint separates the independence-number lower bound from fractional colourability and is presented as a uniform counterexample, but it has appeared only as an unrefereed preprint.
Current status (as of October 2026): The question is claimed solved negatively by a recent preprint, but the construction has not been independently verified in the retrieved sources.
Sources
Solutions 0
No solutions have been posted yet.