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

Bordewich, M.; Kang, R.

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
• Public URL: https://durham-repository.worktribe.com/output/1642917