← All problems

Nešetřil–Rödl–Sales Hall-ratio question

For every integer k≥3k\geq 3, is every nonempty finite kk-uniform hypergraph HH satisfying ρ(H)=kk−1\rho(H)=\frac{k}{k-1} necessarily kk-colourable; equivalently, does ρ(H)=kk−1\rho(H)=\frac{k}{k-1} imply χ(H)≤k\chi(H)\leq k, where ρ(H)=max⁡X⊆V(H)∣X∣α(H[X])\rho(H)=\max_{X\subseteq V(H)}\frac{|X|}{\alpha(H[X])}?

References

Source: arXiv

Progress summary

Refreshed
Open · solution reported

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.