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

For a graph $G=(V,E)$, $kin mathbb{N}$, and a complex number $w$ the partition function of the univariate Potts model is defined as [ {bf Z}(G;k,w):=sum_{phi:Vto [k]}prod_{substack{uvin E phi(u)=phi(v)}}w, ] where $[k]:={1,ldots,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 $Deltain mathbb{N}$ and any $kgeq eDelta+1$, there exists an open set $U$ in the complex plane that contains the interval $[0,1)$ such that ${bf Z}(G;k,w) eq 0$ for any $win U$ and any graph $G$ of maximum degree at most $Delta$. (Here $e$ denotes the base of the natural logarithm.) For small values of $Delta$ 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.