Hostname: page-component-74656f9884-j7cmm Total loading time: 0 Render date: 2026-11-06T02:08:33.161Z Has data issue: false hasContentIssue false
  • English
  • Français

Pfaffian Formulas for Spanning Tree Probabilities

Part of: Graph theory Equilibrium statistical mechanics Combinatorial probability

Published online by Cambridge University Press:  30 May 2016

GRETA PANOVA  and
DAVID B. WILSON
GRETA PANOVA
Affiliation:
Mathematics Department, University of Pennsylvania, Philadelphia, PA 19104, USA (e-mail: panova@math.upenn.edu), http://www.math.upenn.edu/~panova/
DAVID B. WILSON
Affiliation:
Microsoft Research, One Microsoft Way, Redmond, WA 98052, USA (e-mail: David.Wilson@microsoft.com), http://dbwilson.com
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We show that certain topologically defined uniform spanning tree probabilities for graphs embedded in an annulus can be computed as linear combinations of Pfaffians of matrices involving the line-bundle Green's function, where the coefficients count cover-inclusive Dyck tilings of skew Young diagrams.

MSC classification

Primary: 82B20: Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs 05C05: Trees
Secondary: 05C50: Graphs and linear algebra (matrices, eigenvalues, etc.) 05C10: Planar graphs; geometric and topological aspects of graph theory 60C05: Combinatorial probability

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 26 , Issue 1 , January 2017 , pp. 118 - 137
Copyright
Copyright © Cambridge University Press 2016 

References

[1] Carroll, G. D. and Speyer, D. (2004) The cube recurrence. Electron. J. Combin. 11 R73.CrossRefGoogle Scholar
[2] Curtis, E. B., Ingerman, D. and Morrow, J. A. (1998) Circular planar graphs and resistor networks. Linear Algebra Appl. 283 115–150.Google Scholar
[3] Forman, R. (1993) Determinants of Laplacians on graphs. Topology, 32 35–46.Google Scholar
[4] Josuat-Vergés, M. and Kim, J. S. (2014) Generalized Dyck tilings (extended abstract). In 26th Formal Power Series and Algebraic Combinatorics: FPSAC, Discrete Math. Theor. Comput. Sci. Proc. pp. 181–192.Google Scholar
[5] Kenyon, R. (2011) Spanning forests and the vector bundle Laplacian. Ann. Probab. 39 1983–2017.Google Scholar
[6] Kenyon, R. W. and Wilson, D. B. (2009) Combinatorics of tripartite boundary connections for trees and dimers. Electron. J. Combin. 16 R112.CrossRefGoogle Scholar
[7] Kenyon, R. W. and Wilson, D. B. (2011) Boundary partitions in trees and dimers. Trans. Amer. Math. Soc. 363 1325–1364.Google Scholar
[8] Kenyon, R. W. and Wilson, D. B. (2011) Double-dimer pairings and skew Young diagrams. Electron. J. Combin. 18 130.Google Scholar
[9] Kenyon, R. W. and Wilson, D. B. (2014) The space of circular planar electrical networks. arXiv:1411.7425 Google Scholar
[10] Kenyon, R. W. and Wilson, D. B. (2015) Spanning trees of graphs on surfaces and the intensity of loop-erased random walk on planar graphs. J. Amer. Math. Soc. 28 985–1030.CrossRefGoogle Scholar
[11] Kim, J. S. (2012) Proofs of two conjectures of Kenyon and Wilson on Dyck tilings. J. Combin. Theory Ser. A, 119 1692–1710.CrossRefGoogle Scholar
[12] Kim, J. S., Mészáros, K., Panova, G. and Wilson, D. B. (2014) Dyck tilings, increasing trees, descents, and inversions. J. Combin. Theory Ser. A, 122 9–27.Google Scholar
[13] Shigechi, K. and Zinn-Justin, P. (2012) Path representation of maximal parabolic Kazhdan–Lusztig polynomials. J. Pure Appl. Algebra 216 2533–2548.CrossRefGoogle Scholar
[14] Wilson, D. B. (2014) Local statistics of the abelian sandpile model. Manuscript.Google Scholar