Type: Article
Publication Date: 2000-03-01
Citations: 20
DOI: https://doi.org/10.1063/1.533198
In the monomer–dimer model on a graph, each matching (collection of nonoverlapping edges) M has a probability proportional to λ|M|, where λ>0 is the model parameter, and |M| denotes the number of edges in M. An approximate random sample from the monomer–dimer distribution can be obtained by running an appropriate Markov chain (each step of which involves an elementary local change in the configuration) sufficiently long. Jerrum and Sinclair have shown (roughly speaking) that for an arbitrary graph and fixed λ and ε (the maximal allowed variational distance from the desired distribution), O(|Λ|2|E|) steps suffice, where |E| is the number of edges and |Λ| the number of vertices of the graph. For sufficiently nice subgraphs (e.g., cubes) of the d-dimensional cubic lattice we give an explicit recipe to generate approximate random samples in (asymptotically) significantly fewer steps, namely (for fixed λ and ε) O(|Λ|(ln|Λ|)2).