Metraipolis › archive › dc_5ceff9da3723
Random independent sets and local sparsity — arXiv:2609.04654
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.04654
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T23:20:47.631Z
- SHA-256 of the archived text
2fc640745a3ce80d41661a784448eda2db6510f5a25962bf0d4ead79e90ec413- Stable URL of this page
https://metraipolis.com/documento/dc_5ceff9da3723
How to cite
Random independent sets and local sparsity — arXiv:2609.04654 — arXiv (en), https://arxiv.org/abs/2609.04654 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_5ceff9da3723 (Metraipolis archive dc_5ceff9da3723, sha256 2fc640745a3ce80d41661a784448eda2db6510f5a25962bf0d4ead79e90ec413)
BibTeX
@misc{dc5ceff9da3723,
title = {Random independent sets and local sparsity — arXiv:2609.04654},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.04654},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_5ceff9da3723; sha256 2fc640745a3ce80d41661a784448eda2db6510f5a25962bf0d4ead79e90ec413},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.04654. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We analyze random constructions of independent sets in locally sparse graphs, specifically graphs with bounded maximum average degree in neighborhoods or with fractionally $r$-colorable neighborhoods. Specializing our methods to finding large independent sets and low-weight fractional colorings, we focus on optimizing for marginals, but we also derive results that find many independent sets (i.e.\ give lower bounds on the independence polynomial) by optimizing for entropy. Our main results generalize the local Shearer bound of Martinsson and Steiner for triangle-free graphs to graphs with few triangles and to graphs with fractionally $r$-colorable neighborhoods, in the latter case improving upon a result of Dhawan. We also extend independence polynomial bounds obtained via induction to such graphs, improving upon known bounds obtained by local occupancy by relaxing the necessary hypotheses from a maximum degree condition to an average degree condition. Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-07 in math.CO). Categorie arXiv: Combinatorics (math.CO). Pagina del lavoro: https://arxiv.org/abs/2609.04654 — 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-16T23:03:13.236Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-07?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).