Hypergraphs with the smallest Hall ratio are still hard to colour
En palabras de los autores
For a hypergraph, the Hall ratio is a natural lower bound for its chromatic number, and among non-empty -uniform hypergraphs the smallest possible Hall ratio is . For graphs (), having minimum Hall ratio forces chromatic number . Ne\v{s}et\v{r}il, R\"{o}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 there are -uniform hypergraphs with Hall ratio exactly and arbitrarily large fractional chromatic number.
Resultado principalEl resumen no menciona limitaciones.
Apareció: jueves, 15 de octubre. arXiv. Preprint, todavía sin revisión por pares.