On zero-free regions for the anti-ferromagnetic Potts model on bounded-degree graphs
Annales de l’Institut Henri Poincaré D, Tome 8 (2021) no. 3, pp. 459-489.
Le texte intégral des articles récents est réservé aux abonnés de la revue. Consultez l'article sur le site de la revue.

For a graph G=(V,E), k∈ℕ, and complex numbers w=(w e ) e∈E the partition function of the multivariate Potts model is defined as

$$

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 Δ∈ℕ and any k≥eΔ+1, there exists an open set U in the complex plane that contains the interval [0,1) such that 𝐙(G;k,w)≠0 for any graph G=(V,E) of maximum degree at most Δ and any w∈U E . (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.

Accepté le :
Publié le :
DOI : 10.4171/aihpd/108
Classification : 05-XX, 82-XX
Mots-clés : Anti-ferromagnetic Potts model, counting proper colourings, partition function, approximation algorithm, complex zeros 
@article{AIHPD_2021__8_3_459_0,
     author = {Bencs, Ferenc and Davies, Ewan and Patel, Viresh and Regts, Guus},
     title = {On zero-free regions for the anti-ferromagnetic {Potts} model on bounded-degree graphs},
     journal = {Annales de l{\textquoteright}Institut Henri Poincar\'e D},
     pages = {459--489},
     volume = {8},
     number = {3},
     year = {2021},
     doi = {10.4171/aihpd/108},
     mrnumber = {4321222},
     zbl = {1479.82007},
     language = {en},
     url = {http://www.numdam.org/articles/10.4171/aihpd/108/}
}
TY  - JOUR
AU  - Bencs, Ferenc
AU  - Davies, Ewan
AU  - Patel, Viresh
AU  - Regts, Guus
TI  - On zero-free regions for the anti-ferromagnetic Potts model on bounded-degree graphs
JO  - Annales de l’Institut Henri Poincaré D
PY  - 2021
SP  - 459
EP  - 489
VL  - 8
IS  - 3
UR  - http://www.numdam.org/articles/10.4171/aihpd/108/
DO  - 10.4171/aihpd/108
LA  - en
ID  - AIHPD_2021__8_3_459_0
ER  - 
%0 Journal Article
%A Bencs, Ferenc
%A Davies, Ewan
%A Patel, Viresh
%A Regts, Guus
%T On zero-free regions for the anti-ferromagnetic Potts model on bounded-degree graphs
%J Annales de l’Institut Henri Poincaré D
%D 2021
%P 459-489
%V 8
%N 3
%U http://www.numdam.org/articles/10.4171/aihpd/108/
%R 10.4171/aihpd/108
%G en
%F AIHPD_2021__8_3_459_0
Bencs, Ferenc; Davies, Ewan; Patel, Viresh; Regts, Guus. On zero-free regions for the anti-ferromagnetic Potts model on bounded-degree graphs. Annales de l’Institut Henri Poincaré D, Tome 8 (2021) no. 3, pp. 459-489. doi : 10.4171/aihpd/108. http://www.numdam.org/articles/10.4171/aihpd/108/

Cité par Sources :