Geodesic
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.

Voir la notice de l'article provenant de la source Numdam

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
Keywords: 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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/articles/10.4171/aihpd/108/

Cité par Sources :