Spanning trees of graphs on surfaces and the intensity of loop-erased random walk on planar graphs

DOI10.1090/S0894-0347-2014-00819-5MaRDI QIDQ5264116zbMATH OpenOpenAlexFDO

Authors Richard Kenyon, David B. Wilson

Publication date 20 July 2015

Published in Journal of the American Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

abelian sandpile modelloop-erased random walkuniform spanning treevector-bundle Laplacian

Mathematics Subject Classification ID

Trees (05C05) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Combinatorial probability (60C05) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)

Abstract: We show how to compute the probabilities of various connection topologies for uniformly random spanning trees on graphs embedded in surfaces. As an application, we show how to compute the "intensity" of the loop-erased random walk in ${mathbbZ}^2$, that is, the probability that the walk from (0,0) to infinity passes through a given vertex or edge. For example, the probability that it passes through (1,0) is 5/16; this confirms a conjecture from 1994 about the stationary sandpile density on ${mathbbZ}^2$. We do the analogous computation for the triangular lattice, honeycomb lattice and $mathbbZimesmathbbR$, for which the probabilities are 5/18, 13/36, and $1/4-1/p{i}^2$ respectively.

Recommendations

• scientific article; zbMATH DE number 953290
• Loop erased walks and uniform spanning trees
• scientific article; zbMATH DE number 1405906
• Loop-erased random walks, spanning trees and Hamiltonian cycles
• The probability that planar loop-erased random walk uses a given edge

Cites work

• A problem of arrangements
• An asymptotic expansion for the discrete harmonic potential
• Approximation of conformal mappings by circle patterns
• Boundary partitions in trees and dimers
• Choosing a spanning tree for the integer lattice uniformly
• Circular planar graphs and resistor networks
• Conformal invariance of planar loop-erased random walks and uniform spanning trees.
• Correlations between eigenvalues of a random matrix
• Determinants of Laplacians on graphs
• Double-dimer pairings and skew Young diagrams
• Dyck tilings, increasing trees, descents, and inversions
• Fully packed loops in a triangle: matchings, paths and puzzles
• scientific article; zbMATH DE number 3560403 (Why is no real title available?)
• scientific article; zbMATH DE number 1256746 (Why is no real title available?)
• Intersections of random walks.
• Inverse problem in cylindrical electrical networks
• Long-range properties of spanning trees
• Loop-erased walks and total positivity
• Moduli spaces of local systems and higher Teichmüller theory
• Path representation of maximal parabolic Kazhdan-Lusztig polynomials.
• Perplexing problems in probability. Festschrift in honor of Harry Kesten
• Planar electric networks. I
• Planar electric networks. II
• Potential kernel for two-dimensional random walk
• Proofs of two conjectures of Kenyon and Wilson on Dyck tilings
• Random walk: A modern introduction
• Self-organized criticality
• Spanning forests and the vector bundle Laplacian
• The asymptotic determinant of the discrete Laplacian
• The cube recurrence
• The cycle lemma and some applications
• The Laplacian and Dirac operators on critical planar graphs
• The looping constant of Z^d
• Uniform spanning forests
• Über einige lineare partielle Differenzengleichungen mit konstanten Koeffizienten

Cited in

(39)

• Strongly correlated random interacting processes. Abstracts from the workshop held January 28 -- February 3, 2018
• The bundle Laplacian on discrete tori
• Sandpile models
• Conformal invariance of planar loop-erased random walks and uniform spanning trees.
• Loop-erased random walks, spanning trees and Hamiltonian cycles
• Boundary correlations in planar LERW and UST
• Asymptotic height distribution in high-dimensional sandpiles
• The Green's function on the double cover of the grid and application to the uniform spanning tree trunk
• Threshold state and a conjecture of Poghosyan, Poghosyan, Priezzhev and Ruelle
• Dyck tilings, increasing trees, descents, and inversions
• Active spanning trees with bending energy on planar maps and SLE-decorated Liouville quantum gravity for \(\kappa>8\)
• Loop-erased random walk branch of uniform spanning tree in topological polygons
• Learning about critical phenomena from scribbles and sandpiles
• The looping rate and sandpile density of planar graphs
• The looping constant of Z^d
• The space of circular planar electrical networks
• Loop erased walks and uniform spanning trees
• Boundary partitions in trees and dimers
• Fundamental constants in the theory of two-dimensional uniform spanning trees
• Scaling limit of the loop-erased random walk Green's function
• Multipoint correlators in the abelian sandpile model
• Schramm's formula for multiple loop-erased random walks
• Some partial results on the convergence of loop-erased random walk to \(\mathrm{SLE}(2)\) in the natural parametrization
• The sandpile cellular automaton
• The probability that planar loop-erased random walk uses a given edge
• Sandpile probabilities on triangular and hexagonal lattices
• Laplacian growth, sandpiles, and scaling limits
• Toppling and height probabilities in sandpiles
• Pfaffian formulas for spanning tree probabilities
• Generalized loop-erased random walks and approximate reachability
• Laminations of a graph on a pair of pants
• Diffuse scattering on graphs
• Quantitative Russo-Seymour-Welsh for random walk on random graphs and decorrelation of uniform spanning trees
• Universality conjectures for activated random walk
• Correlations in uniform spanning trees: a fermionic approach
• Average height for abelian sandpiles and the looping constant on Sierpiński graphs
• Delaunay decompositions minimizing energy of weighted toroidal graphs
• Potentials in recurrent networks: a survey
• Transfer current and pattern fields in spanning trees

This page was built for publication: Spanning trees of graphs on surfaces and the intensity of loop-erased random walk on planar graphs

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