Local Characteristics, Entropy and Limit Theorems for Spanning Trees and Domino Tilings Via Transfer-Impedances

By R. Burton, Robin Pemantle. 1993

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, known methods 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 tiling 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 whose 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.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Determinantal Point Processes for Machine Learning (2012, background): “Edges in random spanning trees [21] Let G be an arbitrary finite graph with N edges, and let T be a random spanning tree chosen uniformly from the set of all the spanning trees of G.”
Zeros of Random Analytic Functions (2006, background): “• Subset of edges of a finite graph present in a uniformly chosen spanning tree (Burton and Pemantle (4)).”
Probability on Trees and Networks (2017, background): “The following result is due to Campanino (1985), but our proof is modeled on that of Benjamini and Schramm (1996b).”
Zeros of Gaussian Analytic Functions and Determinantal Point Processes (2009, methodology): “The following result was proved by Burton and Pemantle (11), who represented K(e, f ) as the current flowing through f when a unit of current is sent from the tail to the head of e.”
Negative dependence and the geometry of polynomials (2007, background): “Indeed, the rank sequence of the measures obtained in this fashion (i.e., measures on 2[m+1] with a generating polynomial of the form zm+1 m∑ k=0 akek(z1, . . . , zm) + m∑ k=0 bk m ek(z1, . . . , zm), where m ≥ 19 and {ak}mk=0, {bk} m k=0 are the sequences constructed above with t = 10−4) is not eve”
Hyperuniform states of matter (2018, background): “Examples of determinantal point processes arise in uniform spanning trees [236], self-avoiding random walks [237] and random polynomials [238], and have been reported both on the real line [34,239–241] and in higher Euclidean space dimensions [34,141,241].”
Random Complexes and l^2-Betti Numbers (2008, background): “Note that if X is connected and k = 1, this shows that P1 is the uniform measure on spanning trees since 0-dimensional homology has no torsion; this gives a short proof of the Transfer Current Theorem of Burton and Pemantle (1993).”
Non-intersecting paths, random tilings and random matrices (2000, background): “There is a unique translation invariant measure μ of maximal entropy, the Burton-Pemantle measure, on the space of domino tilings of the plane, see [9] and [45].”
Determinantal probability measures (2002, background): “The fact that (1.1) holds for the uniform spanning tree is due to Burton and Pemantle (1993) and is called the Transfer Current Theorem.”