Skip to main content

Research Repository

Advanced Search

Rapid Mixing of Subset Glauber Dynamics on Graphs of Bounded Tree-Width

Bordewich, M.; Kang, R.

Rapid Mixing of Subset Glauber Dynamics on Graphs of Bounded Tree-Width Thumbnail


Authors

R. Kang



Contributors

Luca Aceto
Editor

Monika Henzinger
Editor

J. Sgall
Editor

Abstract

Motivated by the ‘subgraphs world’ view of the ferromagnetic Ising model, we develop a general approach to studying mixing times of Glauber dynamics based on subset expansion expressions for a class of graph polynomials. With a canonical paths argument, we demonstrate that the chains defined within this framework mix rapidly upon graphs of bounded tree-width. This extends known results on rapid mixing for the Tutte polynomial, the adjacency-rank (R 2-)polynomial and the interlace polynomial.

Citation

Bordewich, M., & Kang, R. (2011). Rapid Mixing of Subset Glauber Dynamics on Graphs of Bounded Tree-Width. In L. Aceto, M. Henzinger, & J. Sgall (Eds.), Automata, languages and programming (533-544). Springer Verlag. https://doi.org/10.1007/978-3-642-22006-7_45

Publication Date Jan 1, 2011
Deposit Date Apr 20, 2016
Publicly Available Date May 19, 2016
Publisher Springer Verlag
Pages 533-544
Series Title Lecture notes in computer science
Book Title Automata, languages and programming.
ISBN 9783642220050
DOI https://doi.org/10.1007/978-3-642-22006-7_45

Files





You might also like



Downloadable Citations