Counting and Sampling Anti-Ferromagnetic Potts Models on Random Regular Bipartite Graphs in the Non-uniqueness Regime (opens in new tab)

The anti-ferromagnetic multi-state Potts model, a generalization of the Ising model, is one of the most fundamental models in statistical physics. It was conjectured by Koteck\'{y} (Phys.~Rev.~B, 1985) that the model undergoes a phase transition from a disordered phase at infinite temperature to an ordered phase at sufficiently low temperature on lattices. Such phase transitions are believed to play an important role in computational complexity ...