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

Bencs, Ferenc; Davies, Ewan; Patel, Viresh; Regts, Guus

Annales de l’Institut Henri Poincaré D, Tome 8 (2021) no. 3, pp. 459-489.

For a graph $G=(V,E)$, $k\in \mathbb{N}$, and complex numbers $w={\left(w_e\right)}_{e\in E}$ the partition function of the multivariate Potts model is defined as

$$

where $\left[k\right]:=\{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 $\Delta \in \mathbb{N}$ and any $k\ge e\Delta +1$, there exists an open set $U$ in the complex plane that contains the interval $[0,1)$ such that $𝐙(G;k,w)\ne 0$ for any graph $G=(V,E)$ of maximum degree at most $\Delta$ and any $w\in U^E$. (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.

Classification : 05-XX, 82-XX
Mots-clés : Anti-ferromagnetic Potts model, counting proper colourings, partition function, approximation algorithm, complex zeros