Combinatorics of tripartite boundary connections for trees and dimers (Q2380271): Difference between revisions

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 \textit{E. B. Curtis, D. Ingerman} and \textit{J. A. Morrow} [Linear Algebra Appl. 283, No. 1--3, 115--150 (1998; Zbl 0931.05051)], and by \textit{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.