Spanning forests and the vector bundle Laplacian
arXiv:1001.4028 · doi:10.1214/10-AOP596
Abstract
The classical matrix-tree theorem relates the determinant of the combinatorial Laplacian on a graph to the number of spanning trees. We generalize this result to Laplacians on one- and two-dimensional vector bundles, giving a combinatorial interpretation of their determinants in terms of so-called cycle rooted spanning forests (CRSFs). We construct natural measures on CRSFs for which the edges form a determinantal process. This theory gives a natural generalization of the spanning tree process adapted to graphs embedded on surfaces. We give a number of other applications, for example, we compute the probability that a loop-erased random walk on a planar graph between two vertices on the outer boundary passes left of two given faces. This probability cannot be computed using the standard Laplacian alone.
Published in at http://dx.doi.org/10.1214/10-AOP596 the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)
References in corpus (1)
Cited by in corpus (48)
- Toward a Spectral Theory of Cellular Sheaves
- Magnetic eigenmaps for community detection in directed networks
- Revisiting the combinatorics of the 2D Ising model
- Spanning trees of graphs on surfaces and the intensity of loop-erased random walk on planar graphs
- Random curves on surfaces induced from the Laplacian determinant
- Magnetic Eigenmaps for the Visualization of Directed Networks
- Tree formulas, mean first passage times and Kemeny's constant of a Markov chain
- Dimers and cluster integrable systems
- The -invariant massive Laplacian on isoradial graphs
- Random Forests and Networks Analysis
- Numerical Study of the Correspondence Between the Dissipative and Fixed Energy Abelian Sandpile Models
- Covariant Symanzik identities
- The Laplacian on planar graphs and graphs on surfaces
- Asymptotics of height change on toroidal Temperleyan dimer models
- Semiclassical limits of quantum partition functions on infinite graphs
- Asymptotics of the determinant of discrete Laplacians on triangulated and quadrangulated surfaces
- Determinantal probability measures on Grassmannians
- The Geometry of Synchronization Problems and Learning Group Actions
- Deformed Laplacians and spectral ranking in directed networks
- Transfer current and pattern fields in spanning trees
- Random two-component spanning forests
- Schramm's formula for multiple loop-erased random walks
- Transfer matrix for spanning trees, webs and colored forests
- Discrete and zeta-regularized determinants of the Laplacian on polygonal domains with Dirichlet boundary conditions
- Heat kernel estimates and the relative compactness of perturbations by potentials
- Toroidal Dimer Model and Temperley's Bijection
- Relationships between cycle spaces, gain graphs, graph coverings, fundamental groups, path homology, and graph curvature
- Abelian networks IV. Dynamics of nonhalting networks
- Holomorphic Spinor Observables in the Critical Ising Model
- Sandpile probabilities on triangular and hexagonal lattices
- Gauge field marginal of an Abelian Higgs model
- Determinantal spanning forests on planar graphs
- Pfaffian formulas for spanning tree probabilities
- Dimers on Riemann surfaces II: conformal invariance and scaling limit
- Generalized Schrödinger semigroups on infinite graphs
- The looping constant of Z^d
- The singularity probability of random diagonally-dominant Hermitian matrices
- Layering -Graphs and Networks
- Spectral decimation of the magnetic Laplacian on the Sierpinski gasket: Solving the Hofstadter-Sierpinski butterfly
- Graph coverings and twisted operators
- Multipoint correlators in the Abelian sandpile model
- A generalization of Cardy's and Schramm's formulae
- Winding number and Cutting number of Harmonic cycle
- An equivalence between gauge-twisted and topologically conditioned scalar Gaussian free fields
- Laminations of a graph on a pair of pants
- Graph Complexity and Link Colorings
- Maximal accretive extensions of Schrödinger operators on vector bundles over infinite graphs
- A combinatorial interpretation of harmonic cycles