Georgia Institute of Technology College of Sciences

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)