Subset Glauber Dynamics on Graphs, Hypergraphs and Matroids of Bounded Tree-Width

Bordewich, M.; Kang, R.

Abstract

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.

Citation

Bordewich, M., & Kang, R. (2014). Subset Glauber Dynamics on Graphs, Hypergraphs and Matroids of Bounded Tree-Width. Electronic Journal of Combinatorics, 21(4), Article 19

• Journal Article Type: Article
• Publication Date: Oct 23, 2014
• Deposit Date: Apr 28, 2015
• Publicly Available Date: Jul 23, 2015
• Journal: Electronic Journal of Combinatorics
• Electronic ISSN: 1077-8926
• Publisher: Electronic Journal of Combinatorics
• Peer Reviewed: Peer Reviewed
• Volume: 21
• Issue: 4
• Article Number: 19
• Keywords: Markov chain Monte Carlo, Graph polynomials, Tree-width, Canonical paths, Approximate counting.
• Public URL: https://durham-repository.worktribe.com/output/1409548
• Publisher URL: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p19/pdf