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).
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)
|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
|Look up in GoogleScholar|