The University of Michigan Combinatorics Seminar
Winter 2007
March 23, 4:10-5:00, 3866 East Hall

Boundary partitions in trees and dimers

David B. Wilson

Microsoft Research


We study groves on planar graphs, which are forests in which every tree contains one or more of a special set of vertices on the outer face, referred to as nodes. Each grove partitions the set of nodes. When a random grove is selected, we show how to compute the various partition probabilities as functions of the electrical properties of the graph when viewed as a resistor network. We prove that for any partition sigma, Pr[grove has type sigma] / Pr[grove is a tree] is a dyadic-coefficient polynomial in the pairwise resistances between the nodes, and Pr[grove has type sigma] / Pr[grove has maximal number of trees] is an integer-coefficient polynomial in the entries of the Dirichlet-to-Neumann matrix. We give analogous integer-coefficient polynomial formulas for the pairings of chains in the double-dimer model. These polynomials include Pfaffian formulas for tripartite pairings for groves and double dimer configurations, which generalize the determinant formulas given by Curtis, Ingerman, and Morrow, and by Fomin, for bipartite pairings. We show that the distribution of pairings of contour lines in the Gaussian free field with certain natural boundary conditions is identical to the distribution of pairings in the scaling limit of the double-dimer model. These partition probabilities are relevant to multichordal SLE_2, SLE_4, and SLE_8.

Joint work with Richard Kenyon.