Fast mixing via polymers for random graphs with unbounded degree

DOI10.1016/j.ic.2022.104894zbMath1504.68285arXiv2105.00524OpenAlexW4220831871MaRDI QIDQ2672271

Yanyan Li

Publication date: 8 June 2022

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2105.00524

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Approximation algorithms (68W25) Statistical mechanics of magnetic materials (82D40)

Related Items (3)

Approximately counting independent sets in bipartite graphs via graph containers ⋮ Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs ⋮ Sampling from Potts on random graphs of unbounded degree via random-cluster dynamics

Cites Work

• Unnamed Item
• Unnamed Item
• Combinatorics and complexity of partition functions
• Cluster expansion for abstract polymer models
• Algorithmic Pirogov-Sinai theory
• Random Graphs and Complex Networks
• Algorithms for #BIS-Hard Problems on Expander Graphs
• The evolution of the mixing rate of a simple random walk on the giant component of a random graph
• Approximating the Partition Function of the Ferromagnetic Potts Model
• Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials
• Fast Algorithms for General Spin Systems on Bipartite Expanders
• Efficient sampling and counting algorithms for the Potts model on ℤᵈ at all temperatures
• Counting independent sets in unbalanced bipartite graphs
• Weighted counting of solutions to sparse systems of equations
• The probability that a random multigraph is simple. II
• Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
• Counting Independent Sets and Colorings on Random Regular Bipartite Graphs
• Fast algorithms at low temperatures via Markov chains†

This page was built for publication: Fast mixing via polymers for random graphs with unbounded degree