Approximability of the Six-vertex Model

DOI10.1137/1.9781611975482.136MaRDI QIDQ5236323zbMATH OpenOpenAlexFDO

Authors Jin-Yi Cai, Tianyu Liu, Pinyan Lu

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27) Approximation algorithms (68W25) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)

Abstract: In this paper we take the first step toward a classification of the approximation complexity of the six-vertex model, an object of extensive research in statistical physics. Our complexity results conform to the phase transition phenomenon from physics. We show that the approximation complexity of the six-vertex model behaves dramatically differently on the two sides separated by the phase transition threshold. Furthermore, we present structural properties of the six-vertex model on planar graphs for parameter settings that have known relations to the Tutte polynomial $T(G,x,y)$.

Recommendations

• Complexity classification of the six-vertex model
• On the six-vertex Model's free energy
• Limit shapes of the stochastic six vertex model
• The six-vertex model on random planar maps revisited
• Stochastic six-vertex model
• Exact solution of the six-vertex model on a random lattice.
• Six-vertex Models and the GUE-corners Process
• Integrability of limit shapes of the six vertex model
• Some algebraic aspects of the inhomogeneous six-vertex model
• Approximability of the eight-vertex model

Cited in

(14)

• Convergence of the stochastic six-vertex model to the ASEP, stochastic six-vertex model and ASEP
• Complexity classification of the six-vertex model
• Zeros and approximations of holant polynomials on the complex plane
• Markov duality for stochastic six vertex model
• Two-point convergence of the stochastic six-vertex model to the Airy process
• Torpid mixing of Markov chains for the six-vertex model on \(\mathbb{Z}^2\)
• Approximability of the eight-vertex model
• Six-vertex Models and the GUE-corners Process
• scientific article; zbMATH DE number 7650104 (Why is no real title available?)
• Exact solution of the six-vertex model on a random lattice.
• Approximability of the complementarily symmetric Holant problems on cubic graphs
• Beyond windability: approximability of the four-vertex model
• Counting perfect matchings and the eight-vertex model
• Counting 2-factors of 4-regular bipartite graphs is \(\#P\)-complete

This page was built for publication: Approximability of the Six-vertex Model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236323)