Ferromagnetic Potts Model: Refined #BIS-hardness and Related ResultsReport as inadecuate

Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results - Download this document for free, or read online. Document in PDF available to download.

Reference: Galanis, A, Štefankovič, D, Vigoda, E et al., (2016). Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results. SIAM Journal on Computing, 45 (6), 2004-2065.Citable link to this page:


Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results

Abstract: Recent results establish for the hard-core model (and more generally for 2-spin antiferromagnetic systems) that the computational complexity of approximating the partition function on graphs of maximum degree $\Delta$ undergoes a phase transition that coincides with the uniqueness/non-uniqueness phase transition on the infinite $\Delta$-regular tree. For the ferromagnetic Potts model we investigate whether analogous hardness results hold. Goldberg and Jerrum showed that approximating the partition function of the ferromagnetic Potts model is at least as hard as approximating the number of independent sets in bipartite graphs, so-called #BIS-hardness. We improve this hardness result by establishing it for bipartite graphs of maximum degree $\Delta$. To this end, we first present a detailed picture for the phase diagram for the infinite $\Delta$-regular tree, giving a refined picture of its first-order phase transition and establishing the critical temperature for the coexistence of the disordered and ordered phases. We then prove for all temperatures below this critical temperature (corresponding to the region where the ordered phase “dominates'') that it is #BIS-hard to approximate the partition function on bipartite graphs of maximum degree $\Delta$. As a simple corollary of this result, we obtain that it is #BIS-hard to approximate the number of $k$-colorings on bipartite graphs of maximum degree $\Delta$ whenever $k\leq \Delta/(2\ln \Delta)$. The #BIS-hardness result for the ferromagnetic Potts model uses random bipartite regular graphs as a gadget in the reduction. The analysis of these random graphs relies on recent results establishing connections between the maxima of the expectation of their partition function, attractive fixpoints of the associated tree recursions, and induced matrix norms. In this paper we extend these connections to random regular graphs for all ferromagnetic models. Using these connections, we establish the Bethe prediction for every ferromagnetic spin system on random regular graphs, which says roughly that the expectation of the log of the partition function $Z$ is the same as the log of the expectation of $Z$. As a further consequence of our results, we prove for the ferromagnetic Potts model that the Swendsen--Wang algorithm is torpidly mixing (i.e., exponentially slow convergence to its stationary distribution) on random $\Delta$-regular graphs at the critical temperature for sufficiently large $q$.

Publication status:PublishedPeer Review status:Peer reviewedVersion:Publisher's versionDate of acceptance:2016-08-15 Funder: European Research Council   Funder: /National Science Foundation   Notes:© 2016 Society for Industrial and Applied Mathematics.

Bibliographic Details

Publisher: Society for Industrial and Applied Mathematics

Publisher Website: http://www.siam.org/

Journal: SIAM Journal on Computingsee more from them

Publication Website: http://epubs.siam.org/loi/smjcat

Volume: 45

Issue: 6

Extent: 2004-2065

Issue Date: 2016-11-15


Doi: https://doi.org/10.1137/140997580

Eissn: 1095-7111

Issn: 0097-5397

Uuid: uuid:c0013d59-2f27-4a6f-95a3-13524c4af8e4

Urn: uri:c0013d59-2f27-4a6f-95a3-13524c4af8e4

Pubs-id: pubs:668731 Item Description

Type: journal-article;

Version: Publisher's versionKeywords: ferromagnetic Potts model approximate counting spin systems phase transitions random regular graphs


Author: Galanis, A - Oxford, MPLS, Computer Science - - - Štefankovič, D - - - Vigoda, E - - - Yang, L - - - - Bibliographic Details Pu

Source: https://ora.ox.ac.uk/objects/uuid:c0013d59-2f27-4a6f-95a3-13524c4af8e4


Related documents