Generalized domino-shuffling

The problem of counting filings of a plane region using specified tiles can often be recast as the problem of counting (perfect) matchings of some subgraph of an Aztec diamond graph A(n), or more generally calculating the sum of the weights of all the matchings, where the weight of a matching is equal to the product of the (pre-assigned) weights of the constituent edges (assumed to be non-negative). This article presents efficient algorithms that work in this context to solve three problems: finding the sum of the weights of the matchings of a weighted Aztec diamond graph A(n); computing the probability that a randomly-chosen matching of A(n) will include a particular edge (where the probability of a matching is proportional to its weight); and generating a matching of A(n) at random. The first of these algorithms is equivalent to a special case of Mihai Ciucu's cellular complementation algorithm (J. Combin. Theory Ser. A 81 (1998) 34) and can be used to solve many of the same problems. The second of the three algorithms is a generalization of not-yet-published work of Alexandru lonescu, and can be employed to prove an identity governing a three-variable generating function whose coefficients are all the edge-inclusion probabilities; this formula has been used (Duke Math. J. 85 (1996) 117) as the basis for asymptotic formulas for these probabilities, but a proof of the generating function identity has not hitherto been published. The third of the three algorithms is a generalization of the domino-shuffling algorithm presented in (J. Algebraic Combin. I (1992) 111); it enables one to generate random diabolo-tilings of fortresses and thereby to make intriguing inferences about their asymptotic behavior. (C) 2002 Elsevier B.V. All rights reserved.