On sampling two spin models using the local connective constant
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912348413886464 |
|---|---|
| author | Efthymiou, Charilaos |
| author_facet | Efthymiou, Charilaos |
| contents | This work establishes novel optimum mixing bounds for the Glauber dynamics on the Hard-core and Ising models. These bounds are expressed in terms of the local connective constant of the underlying graph $G$. This is a notion of effective degree for $G$.
Our results have some interesting consequences for bounded degree graphs:
(a) They include the max-degree bounds as a special case
(b) They improve on the running time of the FPTAS considered in [Sinclair, Srivastava, \v Stefankoni\v c and Yin: PTRF 2017] for general graphs
(c) They allow us to obtain mixing bounds in terms of the spectral radius of the adjacency matrix and improve on [Hayes: FOCS 2006].
We obtain our results using tools from the theory of high-dimensional expanders and, in particular, the Spectral Independence method [Anari, Liu, Oveis-Gharan: FOCS 2020]. We explore a new direction by utilising the notion of the $k$-non-backtracking matrix $H_{G,k}$ in our analysis with the Spectral Independence. The results with $H_{G,k}$ are interesting in their own right. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_08179 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On sampling two spin models using the local connective constant Efthymiou, Charilaos Discrete Mathematics Mathematical Physics 68R99, 68W25, 68W20 This work establishes novel optimum mixing bounds for the Glauber dynamics on the Hard-core and Ising models. These bounds are expressed in terms of the local connective constant of the underlying graph $G$. This is a notion of effective degree for $G$. Our results have some interesting consequences for bounded degree graphs: (a) They include the max-degree bounds as a special case (b) They improve on the running time of the FPTAS considered in [Sinclair, Srivastava, \v Stefankoni\v c and Yin: PTRF 2017] for general graphs (c) They allow us to obtain mixing bounds in terms of the spectral radius of the adjacency matrix and improve on [Hayes: FOCS 2006]. We obtain our results using tools from the theory of high-dimensional expanders and, in particular, the Spectral Independence method [Anari, Liu, Oveis-Gharan: FOCS 2020]. We explore a new direction by utilising the notion of the $k$-non-backtracking matrix $H_{G,k}$ in our analysis with the Spectral Independence. The results with $H_{G,k}$ are interesting in their own right. |
| title | On sampling two spin models using the local connective constant |
| topic | Discrete Mathematics Mathematical Physics 68R99, 68W25, 68W20 |
| url | https://arxiv.org/abs/2411.08179 |