Publication:688045

DOI10.1214/AOP/1176989121zbMATH Open0785.60007arXivmath/0404048OpenAlexW2037685751MaRDI QIDQ688045FDOQ688045

Robert Burton, Robin Pemantle

Publication date: 17 April 1994

Published in: The Annals of Probability (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/math/0404048

zbMATH Keywords

spanning treesGreen's functiondomino tilingsinfinite graphsuniform measures on spanning trees

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Combinatorial probability (60C05)

Cited In (only showing first 100 items - show all)

• The number and degree distribution of spanning trees in the Tower of Hanoi graph
• Title not available (Why is that?)
• Geometrically and diagrammatically maximal knots
• On minors of the compound matrix of a Laplacian
• A proof of the transfer-current theorem in absence of reversibility
• Transfer matrix for spanning trees, webs and colored forests
• Gibbs ensembles of nonintersecting paths
• The evaluation of the number and the entropy of spanning trees on generalized small-world networks
• Dimers, tilings and trees
• Sandpile models
• Interlacements and the wired uniform spanning forest
• Combinatorial bandits
• Kauffman's clock lattice as a graph of perfect matchings: a formula for its height
• Non-uniqueness of measures of maximal entropy for subshifts of finite type
• Scaling limits of loop-erased random walks and uniform spanning trees
• The triangular kagomé lattices revisited
• Approaching criticality via the zero dissipation limit in the abelian avalanche model
• On adding a list of numbers (and other one-dependent determinantal processes)
• Recurrence or transience of random walks on random graphs generated by point processes in \(\mathbb{R}^d\)
• Harmonic models and spanning forests of residually finite groups
• Dominos and the Gaussian free field.
• Determinantal probability measures
• COUNTING SPANNING TREES IN PRISM AND ANTI-PRISM GRAPHS
• RANDOM COMPLEXES AND ℓ²-BETTI NUMBERS
• Fundamental constants in the theory of two-dimensional uniform spanning trees
• The spectrum and Laplacian spectrum of the dice lattice
• Regularized limit of determinants for discrete tori
• Hyperuniform states of matter
• Invariant coupling of determinantal measures on sofic groups
• Minimal configurations and sandpile measures
• The energy and spanning trees of the Aztec diamonds
• Transfer current and pattern fields in spanning trees
• Spanning trees on the Sierpinski gasket
• Uniqueness of maximal entropy measure on essential spanning forests
• New directions in algebraic dynamical systems
• Enumeration of spanning trees on Apollonian networks
• The arctic circle boundary and the Airy process
• The asymptotic determinant of the discrete Laplacian
• Point processes in arbitrary dimension from fermionic gases, random matrix theory, and number theory
• Random two-component spanning forests
• High-performance sampling of generic determinantal point processes
• A variational principle for domino tilings
• Local statistics for random domino tilings of the Aztec diamond
• Solvable and algebraic systems on infinite ladder
• Conformal invariance of domino tiling.
• Stationary determinantal processes: phase multiplicity, Bernoullicity, entropy, and domination
• The \(Z\)-invariant massive Laplacian on isoradial graphs
• Abelian sandpiles and the harmonic model
• Indistinguishability of trees in uniform spanning forests
• Enumeration of spanning trees on contact graphs of disk packings
• Two applications of random spanning forests
• Some physical and chemical indices of the Union Jack lattice
• New method for counting the number of spanning trees in a two-tree network
• Zeta functions, heat kernels, and spectral asymptotics on degenerating families of discrete tori
• Spanning forests and the vector bundle Laplacian
• Negative dependence and the geometry of polynomials
• Diffraction and Palm measure of point processes
• Random forests and networks analysis
• Determinant-Preserving Sparsification of SDDM Matrices
• UNIFORM SPANNING FORESTS OF PLANAR GRAPHS
• A bijection theorem for domino tilings with diagonal impurities
• Enumeration of spanning trees of graphs with rotational symmetry
• Long-range properties of spanning trees
• A subshift of finite type that is equivalent to the Ising model
• Random-cluster measures and uniform spanning trees
• Counting spanning trees in self-similar networks by evaluating determinants
• Concentration of Lipschitz Functionals of Determinantal and Other Strong Rayleigh Measures
• Correlation function of Schur process with application to local geometry of a random 3-dimensional Young diagram
• Maximum matchings in scale-free networks with identical degree distribution
• Limiting entropy of determinantal processes
• A new class of the planar networks with high clustering and high entropy
• Topological properties of a 3-regular small world network
• Spectral decimation of the magnetic Laplacian on the Sierpinski gasket: solving the Hofstadter-Sierpinski butterfly
• Spanning trees and dimer problem on the Cairo pentagonal lattice
• The Green's function on the double cover of the grid and application to the uniform spanning tree trunk
• The \(Z\)-Dirac and massive Laplacian operators in the \(Z\)-invariant Ising model
• Extended L-ensembles: a new representation for determinantal point processes
• A heuristic independent particle approximation to determinantal point processes
• A note related to the CS decomposition and the BK inequality for discrete determinantal processes
• Loop-erased partitioning of a graph: mean-field analysis
• Correct proof of the main result in ``The number of spanning trees of a class of self-similar fractal models by Ma and Yao
• Janossy densities of coupled random matrices
• Enumeration of spanning trees with a perfect matching of hexagonal lattices on the cylinder and Möbius strip
• Loop-erased partitioning via parametric spanning trees: monotonicities \& 1D-scaling
• Universality of high-dimensional spanning forests and sandpiles
• Determinantal probability measures on Grassmannians
• Stationary determinantal processes on \({\mathbb{Z}}^d\) with \(N\) labeled objects per site. I: Basic properties and full domination
• Some remarks on associated random fields, random measures and point processes
• Spanning tree bounds for grid graphs
• Matchings on trees and the adjacency matrix: A determinantal viewpoint
• Percolation on Triangulations: A Bijective Path to Liouville Quantum Gravity
• Entropy and enumeration of spanning connected unicyclic subgraphs in self-similar network
• A transient equivalence between Aldous-Broder and Wilson's algorithms and a two-stage framework for generating uniform spanning trees
• Weighted graphs, spanning tree generating functions and anisotropic lattice systems: illustrative results for the Ising and dimer models
• Torsion-weighted spanning acycle entropy in cubical lattices and Mahler measures
• Uniqueness of the infinite tree in low-dimensional random forests
• The cosine-sine decomposition and conditional negative correlation inequalities for determinantal processes
• Metric graphs, cross ratios, and Rayleigh's laws
• Spanning tree generating functions for infinite periodic graphs L and connections with simple closed random walks on L
• Random bichromatic matchings

This page was built for publication: Local characteristics, entropy and limit theorems for spanning trees and domino tilings via transfer-impedances

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q688045)