Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: Combinatorics of Tripartite Boundary Connections for Trees and Dimers. | Combinatorics of Tripartite Boundary Connections for Trees and Dimers Richard W. Kenyon David B. Wilson Brown University Microsoft Research Providence RI Redmond WA http rkenyon http Submitted Mar 10 2009 Accepted Aug 29 2009 Published Sep 11 2009 2010 Mathematics Subject Classification 60C05 82B20 05C05 05C50 Abstract A grove is a spanning forest of a planar graph in which every component tree contains at least one of a special subset of vertices on the outer face called nodes. For the natural probability measure on groves we compute various connection probabilities for the nodes in a random grove. In particular for tripartite pairings of the nodes the probability can be computed as a Pfaffian in the entries of the Dirichlet-to-Neumann matrix discrete Hilbert transform of the graph. These formulas generalize the determinant formulas given by Curtis Ingerman and Morrow and by Fomin for parallel pairings. These Pfaffian formulas are used to give exact expressions for reconstruction reconstructing the conductances of a planar graph from boundary measurements. We prove similar theorems for the double-dimer model on bipartite planar graphs. 1 Introduction In a companion paper KW06 we studied two probability models on finite planar graphs groves and the double-dimer model. Groves Given a finite planar graph and a set of vertices on the outer face referred to as nodes a grove is a spanning forest in which every component tree contains at least one of the nodes. A grove defines a partition of the nodes two nodes are in the same part if and only if they are in the same component tree of the grove. See Figure 1. 2000 Mathematics Subject Classification. 60C05 82B20 05C05 05C50. Key words and phrases. Tree grove double-dimer model Dirichlet-to-Neumann matrix Pfaffian. THE ELECTRONIC JOURNAL OF COMBINATORICS 16 2009 R112 1 6 2 5 6 Wy5 3W b4 1Q--0- 3 1 3 Figure 1 A random grove left of a rectangular grid with 8 nodes on the outer face. In .
