Block coupling and rapidly mixing k-heights
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913542075056128 |
|---|---|
| author | Felsner, Stefan Heldt, Daniel Roch, Sandro Winkler, Peter |
| author_facet | Felsner, Stefan Heldt, Daniel Roch, Sandro Winkler, Peter |
| contents | A $k$-height on a graph $G=(V, E)$ is an assignment $V\to\{0, \ldots, k\}$ such that the value on ajacent vertices differs by at most $1$. We study the Markov chain on $k$-heights that in each step selects a vertex at random, and, if admissible, increases or decreases the value at this vertex by one. In the cases of $2$-heights and $3$-heights we show that this Markov chain is rapidly mixing on certain families of grid-like graphs and on planar cubic $3$-connected graphs.
The result is based on a novel technique called block coupling, which is derived from the well-established monotone coupling approach. This technique may also be effective when analyzing other Markov chains that operate on configurations of spin systems that form a distributive lattice. It is therefore of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_08992 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Block coupling and rapidly mixing k-heights Felsner, Stefan Heldt, Daniel Roch, Sandro Winkler, Peter Discrete Mathematics Combinatorics 60J10 (Primary) 05C99 (Secondary) G.3; G.2.2 A $k$-height on a graph $G=(V, E)$ is an assignment $V\to\{0, \ldots, k\}$ such that the value on ajacent vertices differs by at most $1$. We study the Markov chain on $k$-heights that in each step selects a vertex at random, and, if admissible, increases or decreases the value at this vertex by one. In the cases of $2$-heights and $3$-heights we show that this Markov chain is rapidly mixing on certain families of grid-like graphs and on planar cubic $3$-connected graphs. The result is based on a novel technique called block coupling, which is derived from the well-established monotone coupling approach. This technique may also be effective when analyzing other Markov chains that operate on configurations of spin systems that form a distributive lattice. It is therefore of independent interest. |
| title | Block coupling and rapidly mixing k-heights |
| topic | Discrete Mathematics Combinatorics 60J10 (Primary) 05C99 (Secondary) G.3; G.2.2 |
| url | https://arxiv.org/abs/2410.08992 |