Metraipolis › archive › dc_1c839efffef6
Large independent sets via neighborhood block dynamics, Glauber dynamics, and local occupancy — arXiv:2611.02483
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.02483
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T18:51:28.517Z
- SHA-256 of the archived text
99a3cb2c113a1e5a7eba1e217e554a0ae56ad2b86c483c041c45eb301ff61023- Stable URL of this page
https://metraipolis.com/documento/dc_1c839efffef6
How to cite
Large independent sets via neighborhood block dynamics, Glauber dynamics, and local occupancy — arXiv:2611.02483 — arXiv (en), https://arxiv.org/abs/2611.02483 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_1c839efffef6 (Metraipolis archive dc_1c839efffef6, sha256 99a3cb2c113a1e5a7eba1e217e554a0ae56ad2b86c483c041c45eb301ff61023)
BibTeX
@misc{dc1c839efffef6,
title = {Large independent sets via neighborhood block dynamics, Glauber dynamics, and local occupancy — arXiv:2611.02483},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.02483},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_1c839efffef6; sha256 99a3cb2c113a1e5a7eba1e217e554a0ae56ad2b86c483c041c45eb301ff61023},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.02483. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Local occupancy can be used to bound the expected size of a hard-core independent set. The framework of locally stationary distributions shows that for triangle-free graphs, despite slow mixing at the relevant fugacity parameter, standard Glauber dynamics can be used to find sets close to the local occupancy guarantee. We improve the application of this framework to the hard-core model by replacing a conditional mixing argument with a more direct approach based on a short sequence of single-site updates that, from every initial configuration, achieves the required occupancy inequality. In general graphs, naive conditional mixing estimates or certain problematic structures in the neighborhood can in principle incur running time cost exponential in the maximum degree $\Delta$. We design short update sequences that, via our relaxed criterion, yield running times polynomial in $\Delta$ for graphs with a hereditary bound $b$ on the density of $K_{t,t}$ subgraphs in neighborhoods. Our methods handle the case where $t$ and $b$ can grow with the maximum degree, and the resulting algorithm attains the random graph shattering threshold when they grow sufficiently slowly. That is, we give improved local occupancy parameters and a short update sequence analysis which together show that Glauber dynamics finds independent sets of size $(1-o(1))n(\log\Delta)/\Delta$ in time polynomial in $n$ and $\Delta$ whenever $t$ and $b$ are constant or grow suitably slowly. In a similar regime, we also establish that the (correspondence) chromatic number is at most $(1+o(1))\Delta/\log\Delta$ which improves upon prior results by a factor of at least $4$ in the case $t\ge 4$.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2611.02483 — 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-11-03T18:15:38.136Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).