|
Abstract:
Given a finite planar graph, a grove is a spanning forest in which every
component tree contains one or more of a
specified set of vertices (called nodes) on the outer face. For the uniform
measure on groves, we compute the probabilities
of the different possible node connections in a grove. These probabilities
only depend on boundary measurements of the graph
and not on the actual graph structure, i.e., the probabilities can be
expressed as functions of the pairwise electrical
resistances between the nodes, or equivalently, as functions of the
Dirichlet-to-Neumann operator (or response matrix) on the
nodes. These formulae can be likened to generalizations (for spanning
forests) of Cardy's percolation crossing probabilities,
and generalize Kirchhoff's formula for the electrical resistance.
Remarkably, when appropriately normalized, the connection
probabilities are in fact integer-coefficient polynomials in the matrix
entries, where the coefficients have a natural
algebraic interpretation and can be computed combinatorially. A similar
phenomenon holds in the so-called double-dimer model:
connection probabilities of boundary nodes are polynomial functions of
certain boundary measurements, and as formal
polynomials, they are specializations of the grove polynomials.
Joint work with Richard Kenyon.
|