Sampling weighted perfect matchings on the square-octagon lattice

DOI10.1016/j.tcs.2017.01.014zbMath1380.05157OpenAlexW2583329447MaRDI QIDQ1675927

Prateek Bhakta, Dana Randall

Publication date: 3 November 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2017.01.014

zbMATH Keywords

samplingMarkov chainsprobabilityperfect matchingsfortress model

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorial aspects of tessellation and tiling problems (05B45)

Cites Work

• Unnamed Item
• Unnamed Item
• Critical Ising on the square lattice mixes in polynomial time
• The complexity of computing the permanent
• Slow mixing of Markov chains using fault lines and fat contours
• Binomial determinants, paths, and hook length formulae
• Approximate counting, uniform generation and rapidly mixing Markov chains
• Alternating-sign matrices and domino tilings. I
• Mixing times of lozenge tiling and card shuffling Markov chains
• Analyzing Glauber dynamics by comparison of Markov chains
• Markov Chain Algorithms for Planar Lattice Structures
• Phase Coexistence and Slow Mixing for the Hard-Core Model on ℤ2
• Improved Bounds on the Phase Transition for the Hard-Core Model in 2-Dimensions
• The statistics of dimers on a lattice
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• Polynomial-Time Approximation Algorithms for the Ising Model
• The Effect of Boundary Conditions on Mixing Rates of Markov Chains
• Sampling on Lattices with Free Boundary Conditions Using Randomized Extensions
• Random sampling of 3‐colorings in ℤ²
• Exact sampling with coupled Markov chains and applications to statistical mechanics
• Dimer problem in statistical mechanics-an exact result
• Paths, Trees, and Flowers
• Phase Transitions in Random Dyadic Tilings and Rectangular Dissections
• Random lattice triangulations
• On the Vector Representations of Induced Matroids
• On Ising's model of ferromagnetism

This page was built for publication: Sampling weighted perfect matchings on the square-octagon lattice