2026-07-22T04:54:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24417 2025-12-12T15:01:41Z ddc:004 open_access

Improved Mixing of Critical Hardcore Model Chen, Zongchen Jiang, Tianhui Hardcore model Phase transition Glauber dynamics Spectral independence Online decision making Site percolation The hardcore model is one of the most classic and widely studied examples of undirected graphical models. Given a graph G, the hardcore model describes a Gibbs distribution of λ-weighted independent sets of G. In the last two decades, a beautiful computational phase transition has been established at a precise threshold λ_c(Δ) where Δ denotes the maximum degree, where the task of sampling independent sets transitions from polynomial-time solvable to computationally intractable. We study the critical hardcore model where λ = λ_c(Δ) and show that the Glauber dynamics, a simple yet popular Markov chain algorithm, mixes in Õ(n^{7.44 + O(1/Δ)}) time on any n-vertex graph of maximum degree Δ ≥ 3, significantly improving the previous upper bound Õ(n^{12.88 + O(1/Δ)}) by the recent work [Chen et al., 2024]. The core property we establish in this work is that the critical hardcore model is O(√n)-spectrally independent, improving the trivial bound of n and matching the critical behavior of the Ising model. Our proof approach utilizes an online decision-making framework to study a site percolation model on the infinite (Δ-1)-ary tree, which can be interesting by itself. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Zongchen Chen and Tianhui Jiang 2025 Is Part Of LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2025.51 urn:nbn:de:0030-drops-244176 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.51 eng https://creativecommons.org/licenses/by/4.0/legalcode