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.
@article{10_37236_4195,
author = {Magnus Bordewich and Ross J. Kang},
title = {Subset {Glauber} dynamics on graphs, hypergraphs and matroids of bounded tree-width},
journal = {The electronic journal of combinatorics},
year = {2014},
volume = {21},
number = {4},
doi = {10.37236/4195},
zbl = {1298.05284},
url = {http://geodesic.mathdoc.fr/articles/10.37236/4195/}
}
TY - JOUR
AU - Magnus Bordewich
AU - Ross J. Kang
TI - Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width
JO - The electronic journal of combinatorics
PY - 2014
VL - 21
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/4195/
DO - 10.37236/4195
ID - 10_37236_4195
ER -
%0 Journal Article
%A Magnus Bordewich
%A Ross J. Kang
%T Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width
%J The electronic journal of combinatorics
%D 2014
%V 21
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/4195/
%R 10.37236/4195
%F 10_37236_4195
Magnus Bordewich; Ross J. Kang. Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width. The electronic journal of combinatorics, Tome 21 (2014) no. 4. doi: 10.37236/4195
