Deterministic approximate counting of colorings with fewer than $2Δ$ colors via absence of zeros
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908876685705216 |
|---|---|
| author | Bencs, Ferenc Berrekkal, Khallil Regts, Guus |
| author_facet | Bencs, Ferenc Berrekkal, Khallil Regts, Guus |
| contents | Let $Δ,q\geq 3$ be integers. We prove that there exists $η\geq 0.002$ such that if $q\geq (2-η)Δ$, then there exists an open set $\mathcal{U}\subset \mathbb{C}$ that contains the interval $[0,1]$ such that for each $w\in \mathcal{U}$ and any graph $G=(V,E)$ of maximum degree at most $Δ$, the partition function of the anti-ferromagnetic $q$-state Potts model evaluated at $w$ does not vanish. This provides a (modest) improvement on a result of Liu, Sinclair, and Srivastava, and breaks the $q=2Δ$-barrier for this problem.
As a direct consequence we obtain via Barvinok's interpolation method a deterministic polynomial time algorithm to approximate the number of proper $q$-colorings of graphs of maximum degree at most $Δ$, provided $q\geq (2-η)Δ$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_04727 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Deterministic approximate counting of colorings with fewer than $2Δ$ colors via absence of zeros Bencs, Ferenc Berrekkal, Khallil Regts, Guus Combinatorics Discrete Mathematics Data Structures and Algorithms Let $Δ,q\geq 3$ be integers. We prove that there exists $η\geq 0.002$ such that if $q\geq (2-η)Δ$, then there exists an open set $\mathcal{U}\subset \mathbb{C}$ that contains the interval $[0,1]$ such that for each $w\in \mathcal{U}$ and any graph $G=(V,E)$ of maximum degree at most $Δ$, the partition function of the anti-ferromagnetic $q$-state Potts model evaluated at $w$ does not vanish. This provides a (modest) improvement on a result of Liu, Sinclair, and Srivastava, and breaks the $q=2Δ$-barrier for this problem. As a direct consequence we obtain via Barvinok's interpolation method a deterministic polynomial time algorithm to approximate the number of proper $q$-colorings of graphs of maximum degree at most $Δ$, provided $q\geq (2-η)Δ$. |
| title | Deterministic approximate counting of colorings with fewer than $2Δ$ colors via absence of zeros |
| topic | Combinatorics Discrete Mathematics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2408.04727 |