Approximating the Partition Function of the Ferromagnetic Potts Model
DOI10.1007/978-3-642-14165-2_34zbMath1288.68091arXiv1002.0986MaRDI QIDQ3587394
Leslie Ann Goldberg, Mark R. Jerrum
Publication date: 7 September 2010
Published in: Journal of the ACM, Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1002.0986
phase transition; statistical physics; Potts model; Tutte polynomial; approximation algorithms; random cluster model; computation complexity
05C31: Graph polynomials
68R10: Graph theory (including graph drawing) in computer science
82B20: Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25: Approximation algorithms
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)