Document Open Access Logo

Glauber Dynamics for Ising Model on Convergent Dense Graph Sequences

Authors Rupam Acharyya, Daniel Stefankovic

PDF
Thumbnail PDF

File

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

Document Identifiers

Author Details

Rupam Acharyya
Daniel Stefankovic

Cite As Get BibTex

Rupam Acharyya and Daniel Stefankovic. Glauber Dynamics for Ising Model on Convergent Dense Graph Sequences. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 23:1-23:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.23

Abstract

We study the Glauber dynamics for Ising model on (sequences of) dense graphs. We view the dense graphs through the lens of graphons. For the ferromagnetic Ising model with inverse temperature beta on a convergent sequence of graphs G_n with limit graphon W we show fast mixing of the Glauber dynamics if beta * lambda_1(W) < 1$ and slow (torpid) mixing if beta * lambda_1(W) > 1 (where lambda_1(W)is the largest eigenvalue of the graphon). We also show that in the case beta * lambda_1(W) = 1 there is insufficient information to determine the mixing time (it can be either fast or slow).

Subject Classification

Keywords
  • Spin systems
  • Glauber dynamics
  • Ising model
  • graphons

Metrics

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

References

  1. Noam Berger, Claire Kenyon, Elchanan Mossel, and Yuval Peres. Glauber dynamics on trees and hyperbolic graphs. Probability Theory and Related Fields, 131(3):311-340, 2005. Google Scholar
  2. Antonio Blanca and Alistair Sinclair. Dynamics for the Mean-field Random-cluster Model. In Naveen Garg, Klaus Jansen, Anup Rao, and José D. P. Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015), volume 40 of Leibniz International Proceedings in Informatics (LIPIcs), pages 528-543, Dagstuhl, Germany, 2015. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.528.
  3. Christian Borgs, Jennifer T. Chayes, László Lovász, Vera T. Sós, and Katalin Vesztergombi. Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testing. Advances in Mathematics, 219(6):1801-1851, 2008. Google Scholar
  4. Christian Borgs, Jennifer T. Chayes, László Lovász, Vera T. Sós, and Katalin Vesztergombi. Convergent sequences of dense graphs II. Multiway cuts and statistical physics. Annals of Mathematics, 176(1):151-219, 2012. Google Scholar
  5. Russ Bubley and Martin E. Dyer. Path coupling: A technique for proving rapid mixing in Markov chains. In 38th Annual Symposium on Foundations of Computer Science, FOCS'97, Miami Beach, Florida, USA, October 19-22, 1997, pages 223-231, 1997. URL: http://dx.doi.org/10.1109/SFCS.1997.646111.
  6. Paul Cuff, Jian Ding, Oren Louidor, Eyal Lubetzky, Yuval Peres, and Allan Sly. Glauber dynamics for the mean-field Potts model. Journal of Statistical Physics, 149(3):432-477, 2012. Google Scholar
  7. Martin Dyer, Alan Frieze, and Mark Jerrum. On counting independent sets in sparse graphs. SIAM Journal on Computing, 31(5):1527-1541, 2002. Google Scholar
  8. Andreas Galanis, Daniel Štefankovic, and Eric Vigoda. Swendsen-Wang Algorithm on the Mean-Field Potts Model. In Naveen Garg, Klaus Jansen, Anup Rao, and José D. P. Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015), volume 40 of Leibniz International Proceedings in Informatics (LIPIcs), pages 815-828, Dagstuhl, Germany, 2015. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. URL: http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.815.
  9. Andreas Galanis, Daniel Štefankovič, and Eric Vigoda. Inapproximability of the partition function for the antiferromagnetic Ising and hard-core models. Combinatorics, Probability and Computing, 25(04):500-559, 2016. Google Scholar
  10. Andreas Galanis, Daniel Štefankovič, Eric Vigoda, and Linji Yang. Ferromagnetic Potts model: Refined #BIS-hardness and related results. SIAM Journal on Computing, 45(6):2004-2065, 2016. Google Scholar
  11. Roy J. Glauber. Time-dependent statistics of the Ising model. Journal of mathematical physics, 4(2):294-307, 1963. Google Scholar
  12. Ernst Ising. Beitrag zur Theorie des Ferromagnetismus. Zeitschrift für Physik, 31(1):253-258, 1925. Google Scholar
  13. Mark Jerrum and Alistair Sinclair. Polynomial-time approximation algorithms for the Ising model. SIAM Journal on computing, 22(5):1087-1116, 1993. Google Scholar
  14. Wilhelm Lenz. Beitrag zum Verständnis der magnetischen Erscheinungen in festen Körpern. Z. Phys., 21:613-615, 1920. Google Scholar
  15. David A. Levin, Malwina J. Luczak, and Yuval Peres. Glauber dynamics for the mean-field Ising model: cut-off, critical power law, and metastability. Probability Theory and Related Fields, 146(1):223-265, 2010. Google Scholar
  16. David Asher Levin, Yuval Peres, and Elizabeth Lee Wilmer. Markov chains and mixing times. American Mathematical Soc., 2009. Google Scholar
  17. László Lovász. Large networks and graph limits, volume 60. American Mathematical Soc., 2012. Google Scholar
  18. László Lovász and Vera T. Sós. Generalized quasirandom graphs. Journal of Combinatorial Theory, Series B, 98(1):146-163, 2008. Google Scholar
  19. László Lovász and Balázs Szegedy. Limits of dense graph sequences. Journal of Combinatorial Theory, Series B, 96(6):933-957, 2006. Google Scholar
  20. Fabio Martinelli. Lectures on Glauber dynamics for discrete spin models. Lectures on probability theory and statistics, pages 93-191, 2004. Google Scholar
  21. Fabio Martinelli, Alistair Sinclair, and Dror Weitz. Glauber dynamics on trees: boundary conditions and mixing time. Communications in Mathematical Physics, 250(2):301-334, 2004. Google Scholar
  22. Elchanan Mossel and Allan Sly. Exact thresholds for Ising-Gibbs samplers on general graphs. The Annals of Probability, 41(1):294-328, 2013. Google Scholar
  23. Elchanan Mossel, Dror Weitz, and Nicholas Wormald. On the hardness of sampling independent sets beyond the tree threshold. Probability Theory and Related Fields, 143(3-4):401-439, 2009. Google Scholar
  24. Kevin P. Murphy. Machine learning: a probabilistic perspective. MIT press, 2012. Google Scholar
  25. Wolfgang Paul and Jörg Baschnagel. Stochastic processes. Springer, 1999. Google Scholar
  26. Alistair Sinclair, Piyush Srivastava, Daniel Štefankovič, and Yitong Yin. Spatial mixing and the connective constant: Optimal bounds. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1549-1563. Society for Industrial and Applied Mathematics, 2015. Google Scholar
  27. Alistair Sinclair, Piyush Srivastava, and Yitong Yin. Spatial mixing and approximation algorithms for graphs with bounded connective constant. In 54th Annual Symposium on Foundations of Computer Science (FOCS), pages 300-309, 2013. Google Scholar
  28. Allan Sly and Nike Sun. The computational hardness of counting in two-spin models on d-regular graphs. In 53rd Annual Symposium on Foundations of Computer Science (FOCS), pages 361-369. IEEE, 2012. 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