Today's Events:
Theory Seminar: Approximability of the Six-vertex Model [1]
Friday, December 1, 2017 - 2:30pm
CS 4310
Tianyu Liu
UW-Madison
Six-vertex models originate in statistical mechanics, as a family of vertex
models for crystal lattices with hydrogen bonds. In the language of graph
theory and theory of computing, it is a sum-of-product computation, where on
a 4-regular graph, we compute a partition function which is a weighted sum of
Eulerian orientations, where at every vertex, the orientation must be
two-in-two-out (called ice rule). There are thousands of papers on the
six-vertex model, making it one of the three most studied models in
statistical physics, together with ferromagnetic Ising and monomer-dimer
models.
In joint work with Jin-Yi Cai and Pinyan Lu, we take the first step toward a
classification of the approximation complexity of the six-vertex model. 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). In this talk, I will outline our main results
and techniques in this work.
--
[1]
http://www.cs.wisc.edu/events/3658
![[Computer Systems Lab]](http://www.cs.wisc.edu/pics/csl_logo.gif){kind=logo}