Algorithms for the ferromagnetic Potts model on expanders
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2022
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866929596683780096 |
|---|---|
| author | Carlson, Charlie Davies, Ewan Fraiman, Nicolas Kolla, Alexandra Potukuchi, Aditya Yap, Corrine |
| author_facet | Carlson, Charlie Davies, Ewan Fraiman, Nicolas Kolla, Alexandra Potukuchi, Aditya Yap, Corrine |
| contents | We give algorithms for approximating the partition function of the ferromagnetic $q$-color Potts model on graphs of maximum degree $d$. Our primary contribution is a fully polynomial-time approximation scheme for $d$-regular graphs with an expansion condition at low temperatures (that is, bounded away from the order-disorder threshold). The expansion condition is much weaker than in previous works; for example, the expansion exhibited by the hypercube suffices. The main improvements come from a significantly sharper analysis of standard polymer models; we use extremal graph theory and applications of Karger's algorithm to count cuts that may be of independent interest. It is \#BIS-hard to approximate the partition function at low temperatures on bounded-degree graphs, so our algorithm can be seen as evidence that hard instances of \#BIS are rare. We also obtain efficient algorithms in the Gibbs uniqueness region for bounded-degree graphs. While our high temperature proof follows more standard polymer model analysis, our result holds in the largest known range of parameters $d$ and $q$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2204_01923 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Algorithms for the ferromagnetic Potts model on expanders Carlson, Charlie Davies, Ewan Fraiman, Nicolas Kolla, Alexandra Potukuchi, Aditya Yap, Corrine Data Structures and Algorithms Discrete Mathematics Combinatorics 82B20, 68W25, 05C30 We give algorithms for approximating the partition function of the ferromagnetic $q$-color Potts model on graphs of maximum degree $d$. Our primary contribution is a fully polynomial-time approximation scheme for $d$-regular graphs with an expansion condition at low temperatures (that is, bounded away from the order-disorder threshold). The expansion condition is much weaker than in previous works; for example, the expansion exhibited by the hypercube suffices. The main improvements come from a significantly sharper analysis of standard polymer models; we use extremal graph theory and applications of Karger's algorithm to count cuts that may be of independent interest. It is \#BIS-hard to approximate the partition function at low temperatures on bounded-degree graphs, so our algorithm can be seen as evidence that hard instances of \#BIS are rare. We also obtain efficient algorithms in the Gibbs uniqueness region for bounded-degree graphs. While our high temperature proof follows more standard polymer model analysis, our result holds in the largest known range of parameters $d$ and $q$. |
| title | Algorithms for the ferromagnetic Potts model on expanders |
| topic | Data Structures and Algorithms Discrete Mathematics Combinatorics 82B20, 68W25, 05C30 |
| url | https://arxiv.org/abs/2204.01923 |