Rapid mixing for the hardcore Glauber dynamics and other Markov chains in bounded-treewidth graphs

David Eppstein, Daniel Frishberg

We give a new rapid mixing result for a natural random walk on the independent sets of a graph $G$. We show that when $G$ has bounded treewidth, this random walk -- known as the Gl…