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

Abstract

For a graph $G=(V,E)$, $k\in \mathbb{N}$, and a complex number $w$ the partition function of the univariate Potts model is defined as \[ {\bf Z}(G;k,w):=\sum_{ϕ:V\to [k]}\prod_{\substack{uv\in E \\ ϕ(u)=ϕ(v)}}w, \] where $[k]:=\{1,\dots ,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 $\mathbf{Z}(G;k,w)\ne 0$ for any $w\in 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.

Some minor changes based on referee comments. Accepted for publication in AIHPD. 22 pages; 2 figures

References in corpus (3)

• Fisher zeros and correlation decay in the Ising model
• Location of zeros for the partition function of the Ising model on bounded degree graphs
• Two-dimensional Potts antiferromagnets with a phase transition at arbitrarily large q

Cited by in corpus (2)

• Statistical physics approaches to Unique Games
• Efficient sampling and counting algorithms for the Potts model on ${\mathbb{Z}}^d$ at all temperatures