2003/10/13 by Richard Kenyon, Scott Sheffield, Scott Sheffield⋆ +2 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · Physics and Astronomy · #Cellular Automata and Applications #Combinatorics (math.CO) #Diffusion and Search Dynamics #FOS: Mathematics #FOS: Physical sciences #Mathematical Physics (math-ph) #Probability (math.PR) #Stochastic processes and statistical mechanics #math-ph #math.CO #math.MP #math.PR
paper · pdf · doi:10.48550/arxiv.math/0310195
23 pages, 5 figures
arxiv created 2003/10/13 · openalex publication_date 2003/10/13 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Generalizing results of Temperley, Brooks, Smith, Stone and Tutte and others we describe a natural equivalence between three planar objects: weighted bipartite planar graphs; planar Markov chains; and tilings with convex polygons. This equivalence provides a measure-preserving bijection between dimer coverings of a weighted bipartite planar graph and spanning trees on the corresponding Markov chain. The tilings correspond to harmonic functions on the Markov chain and to ``discrete analytic functions'' on the bipartite graph. The equivalence is extended to infinite periodic graphs, and we classify the resulting ``almost periodic'' tilings and harmonic functions.