Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 43 min ago
PreprintarXiv licencearXiv

Hypergraphs with the smallest Hall ratio are still hard to colour

  • Veronica Bitonti
  • Freddie Illingworth
  • Pedram Noohi
  • Jane Tan
Open at sourcePDFDOICite

Abstract

For H a hypergraph, the Hall ratio ρ(H)=maxX⊆ V(H)lvertXrvert/α(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.

Related

  1. The smallest Mealy automaton of intermediate growth
    Laurent Bartholdi, Illya I. Reznykov, Vitaly I. Sushchansky
    Journal of AlgebraPeer-reviewedLicence not stated30 citedAlgebra & number theoryHAL
  2. The integrability of sesqui-regular graphs with smallest eigenvalue at least −3
    Qianqian Yang, Ruo-Lan Ding
    arXivPreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. A Combinatorial Proof of an Identity of Malik and Sarma on Overpartitions with Repeated Smallest Non-Overlined Part
    Suparno Ghoshal, Arijit Jana
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. On the second smallest ideal right-angled hyperbolic four-polytope
    Alexander Kolpakov
    arXivPreprintarXiv licenceFull textGeometry & topologyarXiv
  5. Smallest Singular Value Estimates for Nonuniform Fourier Matrices via Periodic Nonuniform Sampling
    Liang Chen, Rongrong Lin, Haizhang Zhang
    arXivPreprintCC BY 4.0Full textNumerical analysis & scientific computingarXiv

Cite

BibTeXRIS
BibTeX
@misc{bitonti2026hypergraphs,
  title = {{Hypergraphs with the smallest Hall ratio are still hard to colour}},
  author = {Veronica Bitonti and Freddie Illingworth and Pedram Noohi and Jane Tan},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.20562},
  eprint = {2610.20562},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.20562},
}
RIS
TY  - UNPB
TI  - Hypergraphs with the smallest Hall ratio are still hard to colour
AU  - Veronica Bitonti
AU  - Freddie Illingworth
AU  - Pedram Noohi
AU  - Jane Tan
PY  - 2026
DA  - 2026/10/14
PB  - arXiv
DO  - 10.48550/arxiv.2610.20562
UR  - https://arxiv.org/abs/2610.20562
AB  - For H a hypergraph, the Hall ratio ρ(H)=max_X⊆ V(H)lvertXrvert/α(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.
ER  -