LOCAL CHARACTERISTICS, ENTROPY AND LIMIT-THEOREMS FOR SPANNING-TREES AND DOMINO TILINGS VIA TRANSFER-IMPEDANCES

• 成果类型: Article
• 署名作者: BURTON, R; PEMANTLE, R
• 署名单位: University of Wisconsin System; University of Wisconsin Madison
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/aop/1176989121
• 发表日期: 1993
• 页码: 1329-1371
• 关键词: random-walk; percolation

摘要

Let G be a finite graph or an infinite graph on which Z(d) acts with finite fundamental domain. If G is finite, let T be a random spanning tree chosen uniformly from all spanning trees of G; if G is infinite, methods from Pemantle show that this still makes sense, producing a random essential spanning forest of G. A method for calculating local characteristics (i.e., finite-dimensional marginals) of T from the transfer-impedance matrix is presented. This differs from the classical matrix-tree theorem in that only small pieces of the matrix (n-dimensional minors) are needed to compute small (n-dimensional) marginals. Calculation of the matrix entries relies on the calculation of the Green's function for G, which is not a local calculation. However, it is shown how the calculation of the Green's function may be reduced to a finite computation in the case when G is an infinite graph admitting a Z(d)-action with finite quotient. The same computation also gives the entropy of the law of T. These results are applied to the problem of tilting certain lattices by dominos-the so-called dimer problem. Another application of these results is to prove modified versions of conjectures of Aldous on the limiting distribution of degrees of a vertex and on the local structure near a vertex of a uniform random spanning tree in a lattice whore dimension is going to infinity. Included is a generalization of moments to tree-valued random variables and criteria for these generalized moments to determine a distribution.