Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper investigates the relationship between the Hall ratio and the chromatic number of $k$-uniform hypergraphs, specifically addressing whether a minimal Hall ratio of $k/(k-1)$ implies a similarly minimal chromatic number, as observed for graphs. The authors construct $k$-uniform hypergraphs ($k \geqslant 3$) that achieve the theoretical minimum Hall ratio of $k/(k-1)$ but exhibit arbitrarily large fractional chromatic numbers. This finding demonstrates a significant divergence from the behavior observed in graphs, where a Hall ratio of 2 forces a chromatic number of 2.
Minimal Hall ratios in $k$-uniform hypergraphs ($k \ge 3$) do not guarantee bounded chromatic numbers, shattering a potential generalization of graph coloring principles.
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 large fractional chromatic number.