A New Kempe Invariant and the (non)-Ergodicity of the Wang-Swendsen-Kotecky Algorithm

Abstract

We prove that for the class of three-colorable triangulations of a closed-oriented surface, the degree of a four-coloring modulo 12 is an invariant under Kempe changes. We use this general result to prove that for all triangulations T(3L, 3M) of the torus with 3 ≤ L ≤ M, there are at least two Kempe equivalence classes. This result implies, in particular, that the Wang–Swendsen–Kotecký algorithm for the zero-temperature 4-state Potts antiferromagnet on these triangulations T(3L, 3M) of the torus is not ergodic.