Improved Mixing of Critical Hardcore Model

Zongchen Chen, Tianhui Jiang · 2025

Read Improved Mixing of Critical Hardcore Model by Zongchen Chen, Tianhui Jiang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-07515.txt.

Description

Zongchen Chen and Tianhui Jiang speed up a classic sampling algorithm exactly at the point where theory says it should be hardest. The hardcore model assigns weights to the independent sets of a graph, no two chosen vertices adjacent, and a sharp threshold separates easy sampling from intractable sampling. At that critical threshold, the simple Glauber dynamics, which flips one vertex at a time, was known to mix, but very slowly.

The authors prove it actually mixes in time close to the fourth power of the graph's size, a dramatic improvement over the previous bound near the thirteenth power. The engine of the proof is a tight bound on a spectral independence quantity that holds across the whole subcritical range, not just at the threshold. The paper sharpens the map of the famous phase transition.

Catalog record

CREATORZongchen Chen, Tianhui Jiang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE40 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-07515

Browse the full library · About the Tower of Babel