Markov Chain Algorithms for Planar Lattice Structures
From MaRDI portal
Publication:2784446
DOI10.1137/S0097539799360355zbMath0992.82013OpenAlexW2152646636MaRDI QIDQ2784446
Alistair Sinclair, Michael Luby, Dana Randall
Publication date: 23 April 2002
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539799360355
Analysis of algorithms and problem complexity (68Q25) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics (82B41) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)
Related Items (69)
Markov chain decomposition for convergence rate analysis ⋮ Large deviation for dynamic model of three dimensional Young diagrams ⋮ GENERALIZED DOMINOES TILING'S MARKOV CHAIN MIXES FAST ⋮ Domino statistics of the two-periodic Aztec diamond ⋮ Hydrodynamic limit equation for a lozenge tiling Glauber dynamics ⋮ Fast domino tileability ⋮ An extension of the Lindström-Gessel-Viennot theorem ⋮ Sampling Edge Covers in 3-Regular Graphs ⋮ Randomly coloring planar graphs with fewer colors than the maximum degree ⋮ A note on the structure of spaces of domino tilings ⋮ Tilings of rectangles with T-tetrominoes ⋮ Tilings with trichromatic colored-edges triangles ⋮ Slow mixing of Markov chains using fault lines and fat contours ⋮ Sampling weighted perfect matchings on the square-octagon lattice ⋮ \(q\)-distributions on boxed plane partitions ⋮ Phase Transitions in Random Dyadic Tilings and Rectangular Dissections ⋮ Lozenge tiling dynamics and convergence to the hydrodynamic equation ⋮ On Sampling Simple Paths in Planar Graphs According to Their Lengths ⋮ A bijection proving the Aztec diamond theorem by combing lattice paths ⋮ The mixing time of the Lozenge tiling Glauber dynamics ⋮ Mixing times of monotone surfaces and SOS interfaces: a mean curvature approach ⋮ Off-diagonally symmetric domino tilings of the Aztec diamond ⋮ Tiling with bars under tomographic constraints. ⋮ T-tetrominoes Tiling's Markov chain mixes fast ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Convergence to equilibria in distributed, selfish reallocation processes with weighted tasks ⋮ Rapid Mixing of \({\boldsymbol{k}}\)-Class Biased Permutations ⋮ Irreducibility of recombination Markov chains in the triangular lattice ⋮ Beyond windability: approximability of the four-vertex model ⋮ Unnamed Item ⋮ Mixing time for the solid-on-solid model ⋮ Deducing a variational principle with minimal \textit{a priori} assumptions ⋮ Distances on rhombus tilings ⋮ Complexity classification of the six-vertex model ⋮ Approximating fixation probabilities in the generalized Moran process ⋮ Mixing times of lozenge tiling and card shuffling Markov chains ⋮ Path coupling without contraction ⋮ Cut-colorings in coloring graphs ⋮ Delocalization of uniform graph homomorphisms from \({\mathbb{Z}}^2\) to \({\mathbb{Z}} \) ⋮ Rejection sampling of bipartite graphs with given degree sequence ⋮ “Zero” temperature stochastic 3D ising model and dimer covering fluctuations: A first step towards interface mean curvature motion ⋮ An optimal algorithm to generate tilings ⋮ Uniform sampling ofk-hypertournaments ⋮ Factorization in the multirefined tangent method ⋮ Efficiency test of pseudorandom number generators using random walks ⋮ A bijection theorem for domino tilings with diagonal impurities ⋮ Systematic scan for sampling colorings ⋮ Gibbs ensembles of nonintersecting paths ⋮ An upper bound on the convergence time of the Gibbs sampler in Ising models ⋮ The mixing time of Glauber dynamics for coloring regular trees ⋮ A SYSTEMATIC SCAN FOR 7-COLOURINGS OF THE GRID ⋮ Random tilings with the GPU ⋮ Off-diagonally symmetric domino tilings of the Aztec diamond of odd order ⋮ Sampling and Counting 3-Orientations of Planar Triangulations ⋮ Shuffling algorithm for boxed plane partitions ⋮ Rapid mixing for lattice colourings with fewer colours ⋮ Polynomial Mixing of the Edge-Flip Markov Chain for Unbiased Dyadic Tilings ⋮ Sampling Eulerian orientations of triangular lattice graphs ⋮ Sampling biased monotonic surfaces using exponential metrics ⋮ Sampling \(k\)-partite graphs with a given degree sequence ⋮ Phase coexistence and torpid mixing in the 3-coloring model on ${\mathbb Z}^d$ ⋮ A variational principle for a non-integrable model ⋮ Improved Mixing Bounds for the Anti-Ferromagnetic Potts Model on Z2 ⋮ Unnamed Item ⋮ How quickly can we sample a uniform domino tiling of the \(2L\times 2L\) square via Glauber dynamics? ⋮ Asymptotic domino statistics in the Aztec diamond ⋮ Tacnode GUE-minor processes and double Aztec diamonds ⋮ Lozenge tilings, Glauber dynamics and macroscopic shape
This page was built for publication: Markov Chain Algorithms for Planar Lattice Structures
