On zero-free regions for the anti-ferromagnetic Potts model on bounded-degree graphs

For a graph G=(V,E), k∈N, and a complex number w the partition function of the univariate Potts model is defined as Z(G;k,w):=∑ϕ:V→[k]∏uv∈Eϕ(u)=ϕ(v)w, where [k]:={1,…,k}. In this paper we give zero-free regions for the partition function of the anti-ferromagnetic Potts model on bounded degree graphs. In particular we show that for any Δ∈N and any k≥eΔ+1, there exists an open set U in the complex plane that contains the interval [0,1) such that Z(G;k,w)≠0 for any w∈U and any graph G of maximum degree at most Δ. (Here e denotes the base of the natural logarithm.) For small values of Δ we are able to give better results. As an application of our results we obtain improved bounds on k for the existence of deterministic approximation algorithms for counting the number of proper k-colourings of graphs of small maximum degree