## Spanning forests and the vector bundle Laplacian.(English)Zbl 1252.82029

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

### MSC:

 82B20 Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics 82B41 Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics

### Keywords:

discrete Laplacian; quaternion; spanning tree; resistor network
Full Text:

### References:

 [1] Boutillier, C. and de Tilière, B. (2009). Loop statistics in the toroidal honeycomb dimer model. Ann. Probab. 37 1747-1777. · Zbl 1179.60065 · doi:10.1214/09-AOP453 [2] Brooks, R. L., Smith, C. A. B., Stone, A. H. and Tutte, W. T. (1940). The dissection of rectangles into squares. Duke Math. J. 7 312-340. · Zbl 0024.16501 · doi:10.1215/S0012-7094-40-00718-9 [3] Burton, R. and Pemantle, R. (1993). Local characteristics, entropy and limit theorems for spanning trees and domino tilings via transfer-impedances. Ann. Probab. 21 1329-1371. · Zbl 0785.60007 · doi:10.1214/aop/1176989121 [4] Fock, V. and Goncharov, A. (2006). Moduli spaces of local systems and higher Teichmüller theory. Publ. Math. Inst. Hautes Études Sci. 103 1-211. · Zbl 1099.14025 · doi:10.1007/s10240-006-0039-4 [5] Forman, R. (1993). Determinants of Laplacians on graphs. Topology 32 35-46. · Zbl 0780.05041 · doi:10.1016/0040-9383(93)90035-T [6] Goncharov, A. and Kenyon, R. (2010). Dimers and cluster varieties. Unpublished manuscript, Brown Univ. · Zbl 1288.37025 [7] Hammond, A. and Kenyon, R. (2011). Monotone loops models and rational resonance. Probab. Theory Related Fields 150 613-633. · Zbl 1232.60010 · doi:10.1007/s00440-010-0285-8 [8] Hough, J. B., Krishnapur, M., Peres, Y. and Virág, B. (2006). Determinantal processes and independence. Probab. Surv. 3 206-229 (electronic). · Zbl 1189.60101 · doi:10.1214/154957806000000078 [9] Kenyon, R. (2010). Loops in the double-dimer model. Unpublished manuscript, Brown Univ. · Zbl 1202.82004 [10] Kenyon, R. (2000). The asymptotic determinant of the discrete Laplacian. Acta Math. 185 239-286. · Zbl 0982.05013 · doi:10.1007/BF02392811 [11] Kenyon, R. (2000). Long-range properties of spanning trees. J. Math. Phys. 41 1338-1363. · Zbl 0977.82011 · doi:10.1063/1.533190 [12] Kenyon, R. (2001). Dominos and the Gaussian free field. Ann. Probab. 29 1128-1137. · Zbl 1034.82021 · doi:10.1214/aop/1015345599 [13] Kenyon, R. and Wilson, D. (2010). Laplacians on surface graphs. Unpublished manuscript, Brown Univ. [14] Kenyon, R. W. and Wilson, D. B. (2004). Critical resonance in the non-intersecting lattice path model. Probab. Theory Related Fields 130 289-318. · Zbl 1071.82016 · doi:10.1007/s00440-003-0293-z [15] Kirchhoff, F. (1847). Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme geführt wird. Ann. Phys. Chem. 72 497-508. [16] Lawler, G. F., Schramm, O. and Werner, W. (2004). Conformal invariance of planar loop-erased random walks and uniform spanning trees. Ann. Probab. 32 939-995. · Zbl 1126.82011 · doi:10.1214/aop/1079021469 [17] Majumdar, S. (1992). Exact fractal dimension of the loop-erased self-avoiding walk in two dimensions. Phys. Rev. Lett. 68 2329-2331. [18] Mehta, M. L. (2004). Random Matrices , 3rd ed. Pure and Applied Mathematics ( Amsterdam ) 142 . Elsevier, Amsterdam. · Zbl 1107.15019 [19] Pemantle, R. (1991). Choosing a spanning tree for the integer lattice uniformly. Ann. Probab. 19 1559-1574. · Zbl 0758.60010 · doi:10.1214/aop/1176990223 [20] Wilson, D. B. (1996). Generating random spanning trees more quickly than the cover time. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing ( Philadelphia , PA , 1996) 296-303. ACM, New York. · Zbl 0946.60070
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.