Groundstates of the Ising Model on antiferromagnetic triangulations

Graph Theory Seminar
Thursday, January 8, 2015 - 12:05pm
1 hour (actually 50 minutes)
Skiles 005
GT and University of São Paulo
We discuss a dual version of a problem about perfect matchings in cubic graphs posed by Lovász and Plummer. The dual version is formulated as follows: "Every triangulation of an orientable surface has exponentially many groundstates"; we consider groundstates of the antiferromagnetic Ising Model. According to physicist, the dual formulation holds. In this talk, I plan to show a counterexample to the dual formulation (**), a method to count groundstates which gives a better bound (for the original problem) on the class of Klee-graphs, the complexity of the related problems and if time allows, some open problems. (**): After that physicists came up with an explanation to such an unexpected behaviour!! We are able to construct triangulations where their explanation fails again. I plan to show you this too. (This is joint work with Marcos Kiwi)