The Library
On the mixing time of Glauber dynamics for the hard-core and related models on G(n,d/n)
Tools
Efthymiou, Charilaos and Feng, Weiming (2023) On the mixing time of Glauber dynamics for the hard-core and related models on G(n,d/n). In: 50th EATCS International Colloquium on Automata, Languages and Programming, ICALP 2023, Paderborn, Germany, 10-14 Jul 2023. Published in: Leibniz International Proceedings in Informatics (LIPIcs) 54:1-54:17. doi:10.4230/LIPIcs.ICALP.2023.54 ISSN 1868-8969.
|
PDF
LIPIcs-ICALP-2023-54.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (718Kb) | Preview |
|
PDF
Submission01.pdf - Accepted Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (546Kb) |
Official URL: https://doi.org/10.4230/LIPIcs.ICALP.2023.54
Abstract
We study the single-site Glauber dynamics for the fugacity \lambda, Hard-core model on the random graph G(n, d/n). We show that for the typical instances of the random graph G(n,d/n) and for fugacity \lambda < \frac{d^d}{(d-1)^{d+1}}, the mixing time of Glauber dynamics is n^{1 + O(1/\log \log n)}.
Our result improves on the recent elegant algorithm in [Bezakova, Galanis, Goldberg Stefankovic:2022]. The algorithm there is a MCMC based sampling algorithm, but it is not the Glauber dynamics. Our algorithm here is simpler, as we use the classic Glauber dynamics. Furthermore, the bounds on mixing time we prove are smaller than those in Bezakovs et al. paper, hence our algorithm is also faster.
The main challenge in our proof is handling vertices with unbounded degrees. We provide stronger results with regard the spectral independence via branching values and show that the our Gibbs distributions satisfy the approximate tensorisation of the entropy. We conjecture that the bounds we have here are optimal for G(n,d/n).
As corollary of our analysis for the Hard-core model, we also get bounds on the mixing time of the Glauber dynamics for the Monomer-dimer model on G(n,d/n). The bounds we get for this model are slightly better than those we have for the Hard-core model.
Item Type: | Conference Item (Paper) | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||||||
Library of Congress Subject Headings (LCSH): | Random graphs, Sampling (Statistics), Computer algorithms, Ising model | ||||||||||||
Journal or Publication Title: | Leibniz International Proceedings in Informatics (LIPIcs) | ||||||||||||
Publisher: | Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik | ||||||||||||
ISSN: | 1868-8969 | ||||||||||||
Official Date: | 5 July 2023 | ||||||||||||
Dates: |
|
||||||||||||
Page Range: | 54:1-54:17 | ||||||||||||
DOI: | 10.4230/LIPIcs.ICALP.2023.54 | ||||||||||||
Status: | Peer Reviewed | ||||||||||||
Publication Status: | Published | ||||||||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||||||||
Date of first compliant deposit: | 25 April 2023 | ||||||||||||
Date of first compliant Open Access: | 14 July 2023 | ||||||||||||
RIOXX Funder/Project Grant: |
|
||||||||||||
Conference Paper Type: | Paper | ||||||||||||
Title of Event: | 50th EATCS International Colloquium on Automata, Languages and Programming, ICALP 2023 | ||||||||||||
Type of Event: | Conference | ||||||||||||
Location of Event: | Paderborn, Germany | ||||||||||||
Date(s) of Event: | 10-14 Jul 2023 | ||||||||||||
Related URLs: | |||||||||||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year