Sampling from the low temperature Potts model through a Markov chain on flows. Issue 1 (16th April 2022)

• Record Type: Journal Article
• Authors: Huijben, Jeroen; Patel, Viresh; Regts, Guus
• Is Part Of: Random structures & algorithms. Volume 62:Issue 1(2023)
• Page Start: 219
• Page End: 239
• Publication Date: 2022-04-16
• Subjects: ferromagnetic Potts model -- flows -- Glauber dynamics -- partition function; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21089
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: In this article, we consider the algorithmic problem of sampling from the Potts model and computing its partition function at low temperatures. Instead of directly working with spin configurations, we consider the equivalent problem of sampling flows. We show, using path coupling, that a simple and natural Markov chain on the set of flows is rapidly mixing. As a result, we find a δ $$ \delta $$ ‐approximate sampling algorithm for the Potts model at low enough temperatures, whose running time is bounded by O ( m 2 log ( m δ − 1 ) ) $$ O\left({m}^2\log \left(m{\delta}^{-1}\right)\right) $$ for graphs G $$ G $$ with m $$ m $$ edges.