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

Bencs, Ferenc and Davies, E. and Patel, V. and Regts, G. (2019) On zero-free regions for the anti-ferromagnetic Potts model on bounded-degree graphs. Annales de l'Institut Henri Poincare (D) Combinatorics, Physics and their Interactions. ISSN 2308-5827

Preview

Text 1812.07532v2.pdf Download (290kB) | Preview

Abstract

For a graph G=(V,E), k∈N, and a complex number w the partition function of the univariate Potts model is defined as Z(G;k,w):=∑ϕ:V→[k]∏uv∈Eϕ(u)=ϕ(v)w, where [k]:={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 Δ∈N and any k≥eΔ+1, there exists an open set U in the complex plane that contains the interval [0,1) such that Z(G;k,w)≠0 for any w∈U and any graph G of maximum degree at most Δ. (Here e denotes the base of the natural logarithm.) For small values of Δ 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.

Actions (login required)

Edit Item