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) 6= 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.