Skip to content
DraconiticResearch
Search Sources API
188,932 studies31 sourcesUpdated 23 min ago
PreprintCC BY 4.0arXiv

Property B for random non-uniform hypergraphs

  • Grzegorz Ryn
  • Jakub Kozik
Open at sourcePDFDOICite

Abstract

We show that, in random hypergraphs with several permitted edge sizes, non-uniformity affects existential and algorithmic bounds for 2-colorability (Property B) in fundamentally different ways. Assigning weight 2−k to each k-edge, we obtain upper and lower bounds in terms of the total edge weight that asymptotically match the uniform bounds as the minimum permitted edge size grows, regardless of how edges are distributed among sizes. We also extend the best-known algorithm for 2-coloring random uniform hypergraphs to the non-uniform setting. With weight k/2k assigned to each k-edge, we construct non-uniform instances whose expected total edge weight per vertex is arbitrarily large, yet the algorithm finds a proper coloring asymptotically almost surely. In the uniform setting, the algorithm fails with high probability once this quantity exceeds a constant. Our construction uses sufficiently separated edge sizes, so that edges of different sizes become relevant at well-separated stages of the execution and their effects are essentially independent.

Related

  1. Phase transition of random non-uniform hypergraphs
    Élie de Panafieu
    Journal of Discrete AlgorithmsPeer-reviewedLicence not statedFull text17 citedCombinatorics & discrete mathematicsHAL
  2. Rainbow Berge Hamiltonicity in edge-colored random k-uniform hypergraphs
    Liping Zhang, Ailian Chen
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. A Pittel-type limit law for the largest component of random d-uniform hypergraphs: enumeration and excursions
    Youssouf Wirdane
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsProbabilityarXiv
  4. Irregular Triads in 3-Uniform Hypergraphs
    C. Terry, J. Wolf
    Memoirs of the American Mathematical SocietyPeer-reviewedLicence not statedFull text7 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{ryn2026property,
  title = {{Property B for random non-uniform hypergraphs}},
  author = {Grzegorz Ryn and Jakub Kozik},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.07379},
  eprint = {2610.07379},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.07379},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Property B for random non-uniform hypergraphs
AU  - Grzegorz Ryn
AU  - Jakub Kozik
PY  - 2026
DA  - 2026/10/05
PB  - arXiv
DO  - 10.48550/arxiv.2610.07379
UR  - https://arxiv.org/abs/2610.07379
AB  - We show that, in random hypergraphs with several permitted edge sizes, non-uniformity affects existential and algorithmic bounds for 2-colorability (Property B) in fundamentally different ways. Assigning weight 2^−k to each k-edge, we obtain upper and lower bounds in terms of the total edge weight that asymptotically match the uniform bounds as the minimum permitted edge size grows, regardless of how edges are distributed among sizes. We also extend the best-known algorithm for 2-coloring random uniform hypergraphs to the non-uniform setting. With weight k/2^k assigned to each k-edge, we construct non-uniform instances whose expected total edge weight per vertex is arbitrarily large, yet the algorithm finds a proper coloring asymptotically almost surely. In the uniform setting, the algorithm fails with high probability once this quantity exceeds a constant. Our construction uses sufficiently separated edge sizes, so that edges of different sizes become relevant at well-separated stages of the execution and their effects are essentially independent.
ER  -