Approximating the number of monomer-dimer coverings of a lattice.

DOI10.1007/BF02183743zbMath1081.82523MaRDI QIDQ1593404

Alistair Sinclair, Dana Randall, Claire M. Kenyon

Publication date: 16 January 2001

Published in: Journal of Statistical Physics (Search for Journal in Brave)

zbMATH Keywords

relaxation timeapproximation algorithmMonte Carlo methodsmixing timeperfect matchingvertex-transitive graphsmonomer-dimer problemlattice statisticsdimer coveringsFisher-Kasteleyn-Temperley algorithmmonomer-dimer correlations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Sums of independent random variables; random walks (60G50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parallel algorithms in computer science (68W10) 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

A Pfaffian formula for monomer-dimer partition functions, Random path method with pivoting for computing permanents of matrices, Space saving by dynamic algebraization based on tree-depth, Site monotonicity and uniform positivity for interacting random walks and the spin \(O(N)\) model with arbitrary \(N\), The complexity of generalized domino tilings, Disordered monomer-dimer model on cylinder graphs, Tiling with bars under tomographic constraints., Macroscopic loops in the \(3 d\) double-dimer model, Exact solution of the 2d dimer model: corner free energy, correlation functions and combinatorics, Analyzing Glauber dynamics by comparison of Markov chains, Matchings in vertex-transitive bipartite graphs, Monomer-dimer problem on random planar honeycomb lattice, Random bichromatic matchings, A partially structure-preserving algorithm for the permanents of adjacency matrices of fullerenes, Clifford algebras and approximating the permanent, On the validations of the asymptotic matching conjectures, Approximating the permanent via importance sampling with application to the dimer covering problem, Sequential cavity method for computing free energy and surface pressure, Theory of computation of multidimensional entropy with an application to the monomer-dimer problem, Reconstruction of low degree domino tilings, A statistical model of current loops and magnetic monopoles

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• On defect-d matchings in graphs
• Theory of monomer-dimer systems
• The statistics of dimers on a lattice
• Polynomial-Time Approximation Algorithms for the Ising Model
• Approximating the Permanent
• Statistical Mechanics of Dimers on a Plane Lattice
• Monte-Carlo approximation algorithms for enumeration problems
• A Monte-Carlo Algorithm for Estimating the Permanent
• Approximating the permanent: A simple approach
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• Matchings in lattice graphs
• Dimer problem in statistical mechanics-an exact result
• Statistical Mechanics of Dimers on a Plane Lattice. II. Dimer Correlations and Monomers
• Negative Finding for the Three-Dimensional Dimer Problem
• A Lower Bound for the Monomer-Dimer Problem
• Antiferromagnetism. The Triangular Ising Net
• Statistical mechanics of regular mixtures
• A cell-cluster theory for the liquid state. II