Skip to main content

Research Repository

Advanced Search

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

Bordewich, M.; Kang, R.

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


Authors

R. Kang



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 Mar 29, 2024
Journal Electronic Journal of Combinatorics
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.
Publisher URL http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p19/pdf

Files





You might also like



Downloadable Citations