Bordewich, M. and Kang, R. (2011) 'Rapid mixing of subset glauber dynamics on graphs of bounded tree-width.', in Automata, languages and programming. Piscataway, NJ: Springer, pp. 533-544. Lecture notes in computer science. (6755).
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.
| Item Type: | Book chapter |
|---|---|
| Full text: | (AM) Accepted Manuscript Download PDF (291Kb) |
| Status: | Peer-reviewed |
| Publisher Web site: | http://dx.doi.org/10.1007/978-3-642-22006-7_45 |
| Publisher statement: | The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-642-22006-7_45 |
| Date accepted: | No date available |
| Date deposited: | 19 May 2016 |
| Date of first online publication: | 2011 |
| Date first made open access: | No date available |
Save or Share this output
| Export: | |
| Look up in GoogleScholar |
