Document Open Access Logo

Fast Mixing via Polymers for Random Graphs with Unbounded Degree

Authors Andreas Galanis, Leslie Ann Goldberg, James Stewart

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2021.36.pdf
  • Filesize: 0.63 MB
  • 13 pages

Document Identifiers

Author Details

Andreas Galanis
  • Department of Computer Science, University of Oxford, UK
Leslie Ann Goldberg
  • Department of Computer Science, University of Oxford, UK
James Stewart
  • Department of Computer Science, University of Oxford, UK

Cite As Get BibTex

Andreas Galanis, Leslie Ann Goldberg, and James Stewart. Fast Mixing via Polymers for Random Graphs with Unbounded Degree. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 36:1-36:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.36

Abstract

The polymer model framework is a classical tool from statistical mechanics that has recently been used to obtain approximation algorithms for spin systems on classes of bounded-degree graphs; examples include the ferromagnetic Potts model on expanders and on the grid. One of the key ingredients in the analysis of polymer models is controlling the growth rate of the number of polymers, which has been typically achieved so far by invoking the bounded-degree assumption. Nevertheless, this assumption is often restrictive and obstructs the applicability of the method to more general graphs. For example, sparse random graphs typically have bounded average degree and good expansion properties, but they include vertices with unbounded degree, and therefore are excluded from the current polymer-model framework.
We develop a less restrictive framework for polymer models that relaxes the standard bounded-degree assumption, by reworking the relevant polymer models from the edge perspective. The edge perspective allows us to bound the growth rate of the number of polymers in terms of the total degree of polymers, which in turn can be related more easily to the expansion properties of the underlying graph. To apply our methods, we consider random graphs with unbounded degrees from a fixed degree sequence (with minimum degree at least 3) and obtain approximation algorithms for the ferromagnetic Potts model, which is a standard benchmark for polymer models. Our techniques also extend to more general spin systems.

Subject Classification

ACM Subject Classification
  • Theory of computation → Generating random combinatorial structures
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Markov chains
  • approximate counting
  • Potts model
  • expander graphs
  • random graphs

Metrics

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

Related Versions

References

  1. Alexander Barvinok. Combinatorics and complexity of partition functions, volume 9. Springer, 2016. Google Scholar
  2. Alexander Barvinok and Guus Regts. Weighted counting of solutions to sparse systems of equations. Combinatorics, Probability and Computing, 28(5):696-719, 2019. Google Scholar
  3. Béla Bollobás. The art of mathematics: Coffee time in Memphis. Cambridge University Press, 2006. Google Scholar
  4. Christian Borgs, Jennifer Chayes, Tyler Helmuth, Will Perkins, and Prasad Tetali. Efficient sampling and counting algorithms for the Potts model on ℤ^d at all temperatures. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 738-751, 2020. Google Scholar
  5. Sarah Cannon and Will Perkins. Counting independent sets in unbalanced bipartite graphs. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1456-1466, 2020. Google Scholar
  6. Charles Carlson, Ewan Davies, and Alexandra Kolla. Efficient algorithms for the potts model on small-set expanders. arXiv preprint arXiv:2003.01154, 2020. Google Scholar
  7. Zongchen Chen, Andreas Galanis, Leslie Ann Goldberg, Will Perkins, James Stewart, and Eric Vigoda. Fast algorithms at low temperatures via Markov chains. Random Struct. Algorithms, 58(2):294-321, 2021. Theorems 5 and 6 from arxiv.org/abs/1901.0665. Google Scholar
  8. Nikolaos Fountoulakis and Bruce A Reed. The evolution of the mixing rate of a simple random walk on the giant component of a random graph. Random Structures & Algorithms, 33(1):68-86, 2008. Google Scholar
  9. Tobias Friedrich, Andreas Göbel, Martin S. Krejca, and Marcus Pappik. A spectral independence view on hard-spheres via block dynamics, 2021. URL: http://arxiv.org/abs/2102.07443.
  10. Andreas Galanis, Leslie Ann Goldberg, and James Stewart. Fast Algorithms for General Spin Systems on Bipartite Expanders. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), pages 37:1-37:14, 2020. Google Scholar
  11. Andreas Galanis, Leslie Ann Goldberg, and James Stewart. Fast mixing via polymers for random graphs with unbounded degree. CoRR, abs/2105.00524, 2021. URL: http://arxiv.org/abs/2105.00524.
  12. Andreas Galanis, Daniel Stefankovic, 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
  13. Leslie Ann Goldberg and Mark Jerrum. Approximating the partition function of the ferromagnetic Potts model. Journal of the ACM, 59(5):1-31, 2012. Google Scholar
  14. Christian Gruber and Hervé Kunz. General properties of polymer systems. Communications in Mathematical Physics, 22(2):133-161, 1971. Google Scholar
  15. Tyler Helmuth, Matthew Jenssen, and Will Perkins. Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs. arXiv preprint arXiv:2006.11580, 2020. Google Scholar
  16. Tyler Helmuth, Will Perkins, and Guus Regts. Algorithmic Pirogov-Sinai theory. Probability Theory and Related Fields, 176(3):851-895, 2020. Google Scholar
  17. Jeroen Huijben, Viresh Patel, and Guus Regts. Sampling from the low temperature Potts model through a Markov chain on flows. CoRR, abs/2103.07360, 2021. URL: http://arxiv.org/abs/2103.07360.
  18. Svante Janson. The probability that a random multigraph is simple. II. Journal of Applied Probability, 51(A):123-137, 2014. Google Scholar
  19. Matthew Jenssen and Peter Keevash. Homomorphisms from the torus, 2020. URL: http://arxiv.org/abs/2009.08315.
  20. Matthew Jenssen, Peter Keevash, and Will Perkins. Algorithms for #BIS-hard problems on expander graphs. SIAM Journal on Computing, 49(4):681-710, 2020. Google Scholar
  21. Roman Kotecky and David Preiss. Cluster expansion for abstract polymer models. Communications in Mathematical Physics, 103(3):491-498, 1986. Google Scholar
  22. Chao Liao, Jiabao Lin, Pinyan Lu, and Zhenyu Mao. Counting independent sets and colorings on random regular bipartite graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019), pages 34:1-34:12, 2019. 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