Annales de l’Institut Henri Poincaré D


Full-Text PDF (330 KB) | List online-first AIHPD articles | AIHPD summary
Online access to the full text of Annales de l’Institut Henri Poincaré D is restricted to the subscribers of the journal, who are encouraged to communicate their IP-address(es) to their agent or directly to the publisher at
subscriptions@ems-ph.org
Published online first: 2021-09-22
DOI: 10.4171/AIHPD/108

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

Ferenc Bencs[1], Ewan Davies[2], Viresh Patel[3] and Guus Regts[4]

(1) HAS Alfréd Rényi Institute of Mathematics, Budapest, Hungary; Central European University, Budapest, Hungary; University
(2) University of Amsterdam, Netherlands; University of Colorado Boulder, USA
(3) University of Amsterdam, Netherlands
(4) University of Amsterdam, Netherlands

For a graph $G=(V,E)$, $k\in \mathbb{N}$, and complex numbers $w=(w_e)_{e\in E}$ the partition function of the multivariate Potts model is defined as $$ \mathbf{Z}(G;k,w):=\sum_{\phi\colon V\to [k]} \prod_{\substack{e=uv\in E \\ \phi(u)=\phi(v)}}w_e, $$ 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 $\Delta\in \mathbb{N}$ and any $k\geq 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)\neq 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.

Keywords: Anti-ferromagnetic Potts model, counting proper colourings, partition function, approximation algorithm, complex zeros

Bencs Ferenc, Davies Ewan, Patel Viresh, Regts Guus: On zero-free regions for the anti-ferromagnetic Potts model on bounded-degree graphs. Ann. Inst. Henri Poincaré Comb. Phys. Interact. Electronically published on September 22, 2021. doi: 10.4171/AIHPD/108 (to appear in print)