On zero-free regions for the anti-ferromagnetic Potts model on bounded-degree graphs
| Autor: | Ferenc Bencs, Viresh Patel, Guus Regts, Ewan Davies |
|---|---|
| Přispěvatelé: | Algebra, Geometry & Mathematical Physics (KDV, FNWI), Stochastics (KDV, FNWI) |
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
Statistics and Probability
FOS: Computer and information sciences Discrete Mathematics (cs.DM) FOS: Physical sciences Combinatorics Base (group theory) Computer Science - Data Structures and Algorithms FOS: Mathematics Discrete Mathematics and Combinatorics Mathematics - Combinatorics Data Structures and Algorithms (cs.DS) Mathematical Physics Physics Algebra and Number Theory Degree (graph theory) Zero (complex analysis) Statistical and Nonlinear Physics Mathematical Physics (math-ph) Partition function (mathematics) Bounded function Interval (graph theory) Geometry and Topology Combinatorics (math.CO) Complex plane Potts model Computer Science - Discrete Mathematics |
| Zdroj: | Annales de l'Institut Henri Poincaré D, 8(3), 459-489. European Mathematical Society Publishing House |
| ISSN: | 2308-5827 |
| Popis: | For a graph $G=(V,E)$, $k\in \mathbb{N}$, and a complex number $w$ the partition function of the univariate Potts model is defined as \[ {\bf Z}(G;k,w):=\sum_{\phi:V\to [k]}\prod_{\substack{uv\in E \\ \phi(u)=\phi(v)}}w, \] where $[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 $\Delta\in \mathbb{N}$ and any $k\geq e\Delta+1$, there exists an open set $U$ in the complex plane that contains the interval $[0,1)$ such that ${\bf Z}(G;k,w)\neq 0$ for any $w\in U$ and any graph $G$ of maximum degree at most $\Delta$. (Here $e$ 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 $k$ for the existence of deterministic approximation algorithms for counting the number of proper $k$-colourings of graphs of small maximum degree. Comment: Some minor changes based on referee comments. Accepted for publication in AIHPD. 22 pages; 2 figures |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|