Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width (Q463068): Difference between revisions

Summary: Motivated by the `subgraphs world' view of the ferromagnetic Ising model, we analyse the mixing times of Glauber dynamics based on subset expansion expressions for classes of graph, hypergraph and matroid polynomials. With a canonical paths argument, we demonstrate that the chains defined within this framework mix rapidly upon graphs, hypergraphs and matroids of bounded tree-width.{ }This extends known results on rapid mixing for the Tutte polynomial, adjacency-rank (\(R_2\)-)polynomial and interlace polynomial. In particular Glauber dynamics for the \(R_2\)-polynomial was known to mix rapidly on trees, which led to hope of rapid mixing on a wider class of graphs. We show that Glauber dynamics for a very wide class of polynomials mixes rapidly on graphs of bounded tree-width, including many cases in which the Glauber dynamics does not mix rapidly for all graphs. This demonstrates that rapid mixing on trees or bounded tree-width graphs does not offer strong evidence towards rapid mixing on all graphs.