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

Bencs, Ferenc; Davies, Ewan; Patel, Viresh; Regts, Guus

doi:10.4171/aihpd/108

Bencs, Ferenc ; Davies, Ewan ; Patel, Viresh ; Regts, Guus

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.

Résumé

For a graph $G = (V, E)$ , $k \in ℕ$ , and complex numbers $w = {(w_{e})}_{e \in 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 $Δ \in ℕ$ and any $k \geq e Δ + 1$ , there exists an open set $U$ in the complex plane that contains the interval $[0, 1)$ such that $𝐙 (G; k, w) \neq 0$ for any graph $G = (V, E)$ of maximum degree at most $Δ$ and any $w \in 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 : 2021-03-30
Publié le : 2021-09-22

MR Zbl

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 = {https://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  - https://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 https://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. https://www.numdam.org/articles/10.4171/aihpd/108/

Bibliographie
Cité par

Galvin, David; McKinley, Gwen; Perkins, Will; Sarantis, Michail; Tetali, Prasad On the zeroes of hypergraph independence polynomials, Combinatorics, Probability and Computing, Volume 33 (2024) no. 1, p. 65 | DOI:10.1017/s0963548323000330
de Boer, David; Buys, Pjotr; Regts, Guus Uniqueness of the Gibbs measure for the 4-state anti-ferromagnetic Potts model on the regular tree, Combinatorics, Probability and Computing, Volume 32 (2023) no. 1, p. 158 | DOI:10.1017/s0963548322000207
Bencs, Ferenc; Boer, David de; Buys, Pjotr; Regts, Guus Uniqueness of the Gibbs Measure for the Anti-ferromagnetic Potts Model on the Infinite $Δ$ -Regular Tree for Large $Δ$ , Journal of Statistical Physics, Volume 190 (2023) no. 8 | DOI:10.1007/s10955-023-03145-z
Borgs, Christian; Chayes, Jennifer; Helmuth, Tyler; Perkins, Will; Tetali, Prasad Efficient sampling and counting algorithms for the Potts model on ℤd at all temperatures, Random Structures Algorithms, Volume 63 (2023) no. 1, p. 130 | DOI:10.1002/rsa.21131
Buys, Pjotr; Galanis, Andreas; Patel, Viresh; Regts, Guus Lee–Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs, Forum of Mathematics, Sigma, Volume 10 (2022) | DOI:10.1017/fms.2022.4
Liu, Jingcheng; Sinclair, Alistair; Srivastava, Piyush Correlation Decay and Partition Function Zeros: Algorithms and Phase Transitions, SIAM Journal on Computing (2022), p. FOCS19-200 | DOI:10.1137/20m1317384

Cité par 6 documents. Sources : Crossref