Metraipolis › archive › dc_a8bf8a1fc1ec
Property B for random non-uniform hypergraphs — arXiv:2610.07379
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.07379
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T11:51:12.862Z
- SHA-256 of the archived text
193311d14369fad9b12ad6f1b1d0fde7ee967769535a6df6578081fc85a2b94a- Stable URL of this page
https://metraipolis.com/documento/dc_a8bf8a1fc1ec
How to cite
Property B for random non-uniform hypergraphs — arXiv:2610.07379 — arXiv (en), https://arxiv.org/abs/2610.07379 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_a8bf8a1fc1ec (Metraipolis archive dc_a8bf8a1fc1ec, sha256 193311d14369fad9b12ad6f1b1d0fde7ee967769535a6df6578081fc85a2b94a)
BibTeX
@misc{dca8bf8a1fc1ec,
title = {Property B for random non-uniform hypergraphs — arXiv:2610.07379},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.07379},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_a8bf8a1fc1ec; sha256 193311d14369fad9b12ad6f1b1d0fde7ee967769535a6df6578081fc85a2b94a},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.07379. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 $\frac{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.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.PR, nuovi lavori del giorno).
Categorie arXiv: Discrete Mathematics (cs.DM) ; Combinatorics (math.CO); Probability (math.PR).
Pagina del lavoro: https://arxiv.org/abs/2610.07379 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T11:21:39.657Z dalla pagina https://arxiv.org/list/math.PR/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).