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

被引:167
作者
BURTON, R [1 ]
PEMANTLE, R [1 ]
机构
[1] UNIV WISCONSIN,DEPT MATH,MADISON,WI 53706
关键词
SPANNING TREE; TRANSFER-IMPEDANCE; DOMINO; DIMER; PERFECT MATCHING; ENTROPY;
D O I
10.1214/aop/1176989121
中图分类号
O21 [概率论与数理统计]; C8 [统计学];
学科分类号
020208 ; 070103 ; 0714 ;
摘要
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.
引用
收藏
页码:1329 / 1371
页数:43
相关论文
共 24 条
[1]   THE CONTINUUM RANDOM TREE .1. [J].
ALDOUS, D .
ANNALS OF PROBABILITY, 1991, 19 (01) :1-28
[2]  
ALDOUS D., 1991, ANN APPL PROBAB, V1, P228
[3]  
[Anonymous], 1966, PERTURBATION THEORY
[4]  
[Anonymous], 1964, PRINCIPLES RANDOM WA, DOI DOI 10.1007/978-1-4757-4229-9
[5]  
BRODER A, 1988, S F COMPUTER SCI, P442
[6]   DENSITY AND UNIQUENESS IN PERCOLATION [J].
BURTON, RM ;
KEANE, M .
COMMUNICATIONS IN MATHEMATICAL PHYSICS, 1989, 121 (03) :501-505
[7]   TOPOLOGICAL AND METRIC PROPERTIES OF INFINITE CLUSTERS IN STATIONARY 2-DIMENSIONAL SITE PERCOLATION [J].
BURTON, RM ;
KEANE, M .
ISRAEL JOURNAL OF MATHEMATICS, 1991, 76 (03) :299-316
[8]  
Cvetcovic D, 1980, SPECTRA GRAPHS THEOR
[9]  
DOYLE P., 1984, CARUS MATH MONOGRAPH, V22
[10]  
Durrett R., 1990, PROBABILITY THEORY E