Hypergraphs with the smallest Hall ratio are still hard to colour

Veronica Bitonti, Freddie Illingworth, Pedram Noohi +1

For $H$ a hypergraph, the Hall ratio $\rho (H)={\text{max}}_{X\subseteq V(H)}\frac{|X|}{\alpha (H[X])}$ is a natural lower bound for its chromatic number, and among non-empty $k$-u…