Document Open Access Logo

Sampling in Potts Model on Sparse Random Graphs

Authors Yitong Yin, Chihao Zhang

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2016.47.pdf
  • Filesize: 0.59 MB
  • 22 pages

Document Identifiers

Author Details

Yitong Yin
Chihao Zhang

Cite As Get BibTex

Yitong Yin and Chihao Zhang. Sampling in Potts Model on Sparse Random Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 47:1-47:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2016.47

Abstract

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.

Subject Classification

Keywords
  • Potts model
  • Sampling
  • Random Graph
  • Approximation Algorithm

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Russ Bubley and Martin Dyer. Path coupling: A technique for proving rapid mixing in Markov chains. In Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science (FOCS'97), pages 223-231. IEEE, 1997. Google Scholar
  2. Martin Dyer, Abraham Flaxman, Alan Frieze, and Eric Vigoda. Randomly coloring sparse random graphs with fewer colors than the maximum degree. Random Structures &Algorithms, 29(4):450-465, 2006. Google Scholar
  3. Martin Dyer and Alan Frieze. Randomly coloring graphs with lower bounds on girth and maximum degree. Random Structures &Algorithms, 23(2):167-179, 2003. Google Scholar
  4. Martin Dyer, Alan Frieze, Thomas Hayes, and Eric Vigoda. Randomly coloring constant degree graphs. Random Structures &Algorithms, 43(2):181-200, 2013. Google Scholar
  5. Charilaos Efthymiou. A simple algorithm for random colouring G(n,d/n) using (2+ε)d colours. In Proceedings of the 23th Annual ACM-SIAM symposium on Discrete Algorithms (SODA'12), pages 272-280. SIAM, 2012. Google Scholar
  6. Charilaos Efthymiou. Mcmc sampling colourings and independent sets of G(n,d/n) near uniqueness threshold. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'14), pages 305-316. SIAM, 2014. Google Scholar
  7. Charilaos Efthymiou. Switching colouring of G(n,d/n) for sampling up to Gibbs uniqueness threshold. In In Proceedings of the 22nd European Symposium on Algorithms (ESA'14), pages 371-381. Springer, 2014. Google Scholar
  8. Charilaos Efthymiou and Paul Spirakis. Random sampling of colourings of sparse random graphs with a constant number of colours. Theoretical Computer Science, 407(1):134-154, 2008. Google Scholar
  9. Andreas Galanis, Daniel Štefankovič, and Eric Vigoda. Inapproximability for antiferromagnetic spin systems in the tree nonuniqueness region. Journal of the ACM (JACM), 62(6):50, 2015. Google Scholar
  10. David Gamarnik and Dmitriy Katz. Correlation decay and deterministic FPTAS for counting colorings of a graph. Journal of Discrete Algorithms, 12:29-47, 2012. Google Scholar
  11. David Gamarnik, Dmitriy Katz, and Sidhant Misra. Strong spatial mixing of list coloring of graphs. Random Structures &Algorithms, 46(4):599-613, 2015. Google Scholar
  12. Geoffrey Grimmett and Colin McDiarmid. On colouring random graphs. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 77, pages 313-324. Cambridge Univ Press, 1975. Google Scholar
  13. Thomas Hayes. Randomly coloring graphs of girth at least five. In Proceedings of the 35th Annual ACM Symposium on Symposium on Theory of Computing (STOC'03), pages 269-278. ACM, 2003. Google Scholar
  14. Thomas Hayes and Eric Vigoda. A non-markovian coupling for randomly sampling colorings. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03), pages 618-627. IEEE, 2003. Google Scholar
  15. Thomas Hayes and Eric Vigoda. Coupling with the stationary distribution and improved sampling for colorings and independent sets. The Annals of Applied Probability, 16(3):1297-1318, 2006. Google Scholar
  16. Mark Jerrum. A very simple algorithm for estimating the number of k-colorings of a low-degree graph. Random Structures and Algorithms, 7(2):157-166, 1995. Google Scholar
  17. Mark Jerrum, Leslie Valiant, and Vijay Vazirani. Random generation of combinatorial structures from a uniform distribution. Theoretical Computer Science, 43:169-188, 1986. Google Scholar
  18. Johan Jonasson. Uniqueness of uniform random colorings of regular trees. Statistics &Probability Letters, 57(3):243-248, 2002. Google Scholar
  19. Pinyan Lu and Yitong Yin. Improved FPTAS for multi-spin systems. In Proceedings of APPROX-RANDOM, pages 639-654. Springer, 2013. Google Scholar
  20. Michael Molloy. The Glauber dynamics on colorings of a graph with high girth and maximum degree. SIAM Journal on Computing, 33(3):721-737, 2004. Google Scholar
  21. Elchanan Mossel and Allan Sly. Gibbs rapidly samples colorings of G(n, d/n). Probability theory and related fields, 148(1-2):37-69, 2010. Google Scholar
  22. Alistair Sinclair and Mark Jerrum. Approximate counting, uniform generation and rapidly mixing Markov chains. Information and Computation, 82(1):93-133, 1989. Google Scholar
  23. Alistair Sinclair, Piyush Srivastava, Daniel Štefankovič, and Yitong Yin. Spatial mixing and the connective constant: Optimal bounds. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'15), pages 1549-1563. SIAM, 2015. Google Scholar
  24. Alistair Sinclair, Piyush Srivastava, and Yitong Yin. Spatial mixing and approximation algorithms for graphs with bounded connective constant. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS'13), pages 300-309. IEEE, 2013. Google Scholar
  25. Eric Vigoda. Improved bounds for sampling colorings. Journal of Mathematical Physics, 41(3):1555-1569, 2000. Google Scholar
  26. Yitong Yin. Spatial mixing of coloring random graphs. In Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP'14, Track A), pages 1075-1086. Springer, 2014. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact