2026-07-23T18:33:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6670 2024-03-06T10:38:39Z ddc:004 open_access

Sampling in Potts Model on Sparse Random Graphs Yin, Yitong Zhang, Chihao Potts model Sampling Random Graph Approximation Algorithm We study the problem of sampling almost uniform proper q-colorings in sparse Erdos-Renyi random graphs G(n,d/n), a research initiated by Dyer, Flaxman, Frieze and Vigoda [Dyer et al., RANDOM STRUCT ALGOR, 2006]. We obtain a fully polynomial time almost uniform sampler (FPAUS) for the problem provided q>3d+4, improving the current best bound q>5.5d [Efthymiou, SODA, 2014]. Our sampling algorithm works for more generalized models and broader family of sparse graphs. It is an efficient sampler (in the same sense of FPAUS) for anti-ferromagnetic Potts model with activity 0<=b<1 on G(n,d/n) provided q>3(1-b)d+4. We further identify a family of sparse graphs to which all these results can be extended. This family of graphs is characterized by the notion of contraction function, which is a new measure of the average degree in graphs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yitong Yin and Chihao Zhang 2016 Is Part Of LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2016.47 urn:nbn:de:0030-drops-66706 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.47 eng https://creativecommons.org/licenses/by/3.0/legalcode