{"id":"arxiv/2610.20562","url":"https://arxiv.org/abs/2610.20562","tags":["math.CO"],"score":0,"title":"Hypergraphs with the smallest Hall ratio are still hard to colour","domain":"math.CO","source":"arxiv","authors":["Veronica Bitonti","Freddie Illingworth","Pedram Noohi","Jane Tan"],"reviews":0,"subject":"math.CO","summary":"For $H$ a hypergraph, the Hall ratio $ρ(H)=\\text{max}_{X\\subseteq V(H)}\\frac{\\lvert{X}\\rvert}{α(H[X])}$ is a natural lower bound for its chromatic number, and among non-empty $k$-uniform hypergraphs the smallest possible Hall ratio is $k/(k-1)$. For graphs ($k = 2$), having minimum Hall ratio $2$ forces chromatic number $2$. Nešetřil, Rödl, and Sales asked whether a similar phenomenon holds at higher uniformities. We answer this question negatively in a strong form, showing that for every $k \\geqslant 3$ there are $k$-uniform hypergraphs with Hall ratio exactly $k/(k-1)$ and arbitrarily…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-14","reactions":{}}