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

  • Ferenc Bencs

    HAS Alfréd Rényi Institute of Mathematics, Budapest, Hungary; Central European University, Budapest, Hungary; University of Amsterdam, Netherlands
  • Ewan Davies

    University of Amsterdam, Netherlands; University of Colorado Boulder, USA
  • Viresh Patel

    University of Amsterdam, Netherlands
  • Guus Regts

    University of Amsterdam, Netherlands
On zero-free regions for the anti-ferromagnetic Potts model on bounded-degree graphs cover
Download PDF

A subscription is required to access this article.

Abstract

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

Z(G;k,w):=ϕ ⁣:V[k]e=uvEϕ(u)=ϕ(v)we,\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,,k}[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 ΔN\Delta\in \mathbb{N} and any keΔ+1k\geq e \Delta+1, there exists an open set UU in the complex plane that contains the interval [0,1)[0,1) such that Z(G;k,w)0\mathbf{Z}(G;k,w)\neq 0 for any graph G=(V,E)G=(V,E) of maximum degree at most Δ\Delta and any wUEw\in U^E. (Here ee 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 kk for the existence of deterministic approximation algorithms for counting the number of proper kk-colourings of graphs of small maximum degree.

Cite this article

Ferenc Bencs, Ewan Davies, Viresh Patel, Guus Regts, On zero-free regions for the anti-ferromagnetic Potts model on bounded-degree graphs. Ann. Inst. Henri Poincaré Comb. Phys. Interact. 8 (2021), no. 3, pp. 459–489

DOI 10.4171/AIHPD/108