Block coupling and rapidly mixing k-heights

Abstract

A $k$-height on a graph $G=(V,E)$ is an assignment $V\to \{0,\dots ,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.

31 pages, 8 figures. Supplemental code available at Zenodo, doi:10.5281/zenodo.13912818