2017/12/16 by Cai, Jin-Yi, Liu, Tianyu, Lu, Pinyan
#Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1712.05880
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).