×

zbMATH — the first resource for mathematics

Combinatorics of tripartite boundary connections for trees and dimers. (English) Zbl 1225.60020
A grove is defined as a spanning forest of a planar graph such that every component tree contains at least one of a special subset of vertices on the outer face called nodes. Endowing the set of groves with its natural probability measure, the authors compute various connection probabilities for the nodes in a random grove. In particular, for tripartite pairings of the nodes, the authors prove that the probability may be computed as a Pfaffian in the entries of the Dirichlet-to-Neumann matrix (also known as the response matrix or discrete Hilbert transform) of the graph, thereby generalizing the determinant formulas given by E. B. Curtis, D. Ingerman and J. A. Morrow [Linear Algebra Appl. 283, No. 1–3, 115–150 (1998; Zbl 0931.05051)], and by S. Fomin [Trans. Am. Math. Soc. 353, No. 9, 3563–3583 (2001; Zbl 0973.15014)], for parallel pairings. These Pfaffian formulas enable them to give exact expressions for reconstruction, that is, to determine the conductances on the edges of a planar graph from boundary measurements. The authors also obtain similar results for the double-dimer model on bipartite planar graphs.

MSC:
60C05 Combinatorial probability
82B20 Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics
05C05 Trees
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
PDF BibTeX XML Cite
Full Text: EMIS EuDML arXiv