Bordewich, M. and Kang, R. (2014) 'Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width.', The electronic journal of combinatorics., 21 (4). P4.19.
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 dened 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 (R2-)polynomial and interlace polynomial. In particular Glauber dynamics for the R2-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 oer strong evidence towards rapid mixing on all graphs.
|Keywords:||Markov chain Monte Carlo, Graph polynomials, Tree-width, Canonical paths, Approximate counting.|
|Full text:||(VoR) Version of Record|
Download PDF (409Kb)
|Publisher Web site:||http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p19/pdf|
|Date accepted:||No date available|
|Date deposited:||23 July 2015|
|Date of first online publication:||October 2014|
|Date first made open access:||No date available|
Save or Share this output
|Look up in GoogleScholar|