Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 43 min ago
PreprintCC BY 4.0arXiv

Almost All 3-uniform Hypergraphs are Class 1

  • Arnab Chaterjee
  • Asaf Ferber
  • Marcelo Sales
  • Mason Shurman
Open at sourcePDFDOICite

Abstract

The chromatic index χ'(H) of a hypergraph H is the smallest number of colors needed to color its edges so that no two adjacent edges share the same color. The chromatic index is trivially bounded below by the maximum degree Δ(H), and when χ'(H)= Δ(H), we say that H is Class 1. It is well known that almost every 2-graph is Class 1, and we extend this result to 3-graphs. We show for n−2/3−1/200≤ p ≤ 0.99 that the $3$-uniform binomial random hypergraph H∼ Hn,p(3) is Class 1 with high probability. We also show that this result doesn't hold for uniformities above $3$. For a broad range of p, when k ≥ 4 and k nmid n, the hypergraph H ∼ Hn,p(k) is with high probability not Class 1.

Related

  1. Infinitely Many Almost-Uniform 3-Qualitative Independence Hypergraphs are Cores
    Raina Mary Thomas, Yasmeen Akhtar
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. Phase transition of random non-uniform hypergraphs
    Élie de Panafieu
    Journal of Discrete AlgorithmsPeer-reviewedLicence not statedFull text17 citedCombinatorics & discrete mathematicsHAL
  3. Irregular Triads in 3-Uniform Hypergraphs
    C. Terry, J. Wolf
    Memoirs of the American Mathematical SocietyPeer-reviewedLicence not statedFull text30 citedCombinatorics & discrete mathematicsOpenAlex
  4. Towards the Erdős matching conjecture for 4‐uniform hypergraphs: Stability and applications
    Péter Frankl, Hongliang Lu, Jie Ma +1
    MathematikaPeer-reviewedLicence not statedFull text11 citedCombinatorics & discrete mathematicsOpenAlex
  5. On the growth of weak regular partitions in k-uniform hypergraphs
    H. Sheats, C. Terry
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsLogic & foundationsarXiv

Cite

BibTeXRIS
BibTeX
@misc{chaterjee2026almost,
  title = {{Almost All 3-uniform Hypergraphs are Class 1}},
  author = {Arnab Chaterjee and Asaf Ferber and Marcelo Sales and Mason Shurman},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.05622},
  eprint = {2611.05622},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.05622},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Almost All 3-uniform Hypergraphs are Class 1
AU  - Arnab Chaterjee
AU  - Asaf Ferber
AU  - Marcelo Sales
AU  - Mason Shurman
PY  - 2026
DA  - 2026/11/03
PB  - arXiv
DO  - 10.48550/arxiv.2611.05622
UR  - https://arxiv.org/abs/2611.05622
AB  - The chromatic index χ'(H) of a hypergraph H is the smallest number of colors needed to color its edges so that no two adjacent edges share the same color. The chromatic index is trivially bounded below by the maximum degree Δ(H), and when χ'(H)= Δ(H), we say that H is Class 1. It is well known that almost every 2-graph is Class 1, and we extend this result to 3-graphs. We show for n^−2/3−1/200≤ p ≤ 0.99 that the $3$-uniform binomial random hypergraph H∼ H_n,p^(3) is Class 1 with high probability. We also show that this result doesn't hold for uniformities above $3$. For a broad range of p, when k ≥ 4 and k nmid n, the hypergraph H ∼ H_n,p^(k) is with high probability not Class 1.
ER  -