Large independent sets via neighborhood block dynamics, Glauber dynamics, and local occupancy
Abstract
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 Δ. We design short update sequences that, via our relaxed criterion, yield running times polynomial in Δ for graphs with a hereditary bound b on the density of Kt,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Δ)/Δ in time polynomial in n and Δ 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))Δ/logΔ which improves upon prior results by a factor of at least $4$ in the case t≥ 4.
Related
- Glauber Dynamics for Sampling Colorings: Rapid Mixing above (1+1/e)Δ via Hidden Hard-Core Models
- Mixing profile for Glauber dynamics of the discrete Gaussian Free Field starting from super-harmonic functions
- Optimal Mixing of Glauber Dynamics for the Sherrington-Kirkpatrick Model at β< 1/2
- Averaged Annealed Markov Chains Achieve the Algorithmic Threshold for Tensor PCA, Part I: Glauber Dynamics
- Linear Fluctuation of Interfaces in Glauber–Kawasaki Dynamics
BibTeX
@misc{davies2026large,
title = {{Large independent sets via neighborhood block dynamics, Glauber dynamics, and local occupancy}},
author = {Ewan Davies and Brian Tan},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.02483},
eprint = {2611.02483},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.02483},
}
RIS
TY - UNPB
TI - Large independent sets via neighborhood block dynamics, Glauber dynamics, and local occupancy
AU - Ewan Davies
AU - Brian Tan
PY - 2026
DA - 2026/11/02
PB - arXiv
DO - 10.48550/arxiv.2611.02483
UR - https://arxiv.org/abs/2611.02483
AB - 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 Δ. We design short update sequences that, via our relaxed criterion, yield running times polynomial in Δ 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Δ)/Δ in time polynomial in n and Δ 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))Δ/logΔ which improves upon prior results by a factor of at least $4$ in the case t≥ 4.
ER -