The thermodynamic properties of a film of diatomic molecules accumulated through adsorption on a surface can be studied through a lattice of dimers. Abstractly, this is a grid graph of horizontal and vertical edges, usually on a torus.

The properties of interest in statistical physics depend upon the number of matchings in this graph. If the graph has ℓ edges, the number of matchings with exactly k horizontal edges, the (k, ℓ)-matchings, is a quantity of particular relevance. The main result of this paper is a fully polynomial randomized approximation scheme estimating the number of (k, ℓ)-matchings: the number can be approximated within a factor of (1 ± &egr;) for any &egr; ∈ (0,1) with high probability in polynomial time.

The result is obtained by sampling via a Markov chain, a random walk from matching to matching that rapidly mixes and so quickly provides an accurate estimate.

The random walk is defined so that transitions tend toward (k, ℓ)-matchings. It is then not hard to establish that the chain tends toward the desired stationary distribution, which provides the counting estimate.

The challenging aspect of this work is to prove the walk is rapidly mixing. The authors follow the canonical paths approach pioneered by Jerrum and Sinclair, which requires bounding the congestion of edges to establish that no edge is so overloaded as to become a bottleneck to rapid mixing. The proof is long, technical, and intricate, but clearly described for experts. Rapid mixing is then enough to establish that accurate estimation of the number of (k, ℓ)-matchings is achieved in time polynomial in all relevant parameters.