Paper Info
Title
Sampling Weighted Perfect Matchings on the Square-Octagon Lattice.
Abstract
Perfect matchings of the square-octagon lattice, also known as “fortresses” [19], have been shown to have a rich combinatorial structure. We are interested in a natural local Markov chain for sampling from the set of perfect matchings that is known to be ergodic and has been used in practice to discover properties of random fortresses. However, unlike related Markov chains used for sampling domino and lozenge tilings, this Markov chain on the square-octagon lattice appears to converge slowly. To understand why, we introduce a weighted version of the chain and prove that this chain can converge in polynomial time or exponential time depending on the settings of the parameters.
Year
DOI
Venue
2017
10.1016/j.tcs.2017.01.014
Theoretical Computer Science
Keywords
DocType
Volume
Markov chains,Sampling,Perfect matchings,Probability,Fortress model
Journal
699
ISSN
Citations 
PageRank 
0304-3975
0
0.34
References 
Authors
10
2
Name
Order
Citations
PageRank
Prateek Bhakta142.27
Dana Randall2298.15