Sarah Miracle ; Dana Randall ; Amanda Pascoe Streib ; Prasad Tetali - Mixing times of Markov chains on 3-Orientations of Planar Triangulations

dmtcs:3010 - Discrete Mathematics & Theoretical Computer Science, January 1, 2012, DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12) - https://doi.org/10.46298/dmtcs.3010
Mixing times of Markov chains on 3-Orientations of Planar Triangulations

Authors: Sarah Miracle ; Dana Randall ; Amanda Pascoe Streib ; Prasad Tetali

Given a planar triangulation, a 3-orientation is an orientation of the internal edges so all internal vertices have out-degree three. Each 3-orientation gives rise to a unique edge coloring known as a $\textit{Schnyder wood}$ that has proven useful for various computing and combinatorics applications. We consider natural Markov chains for sampling uniformly from the set of 3-orientations. First, we study a "triangle-reversing'' chain on the space of 3-orientations of a fixed triangulation that reverses the orientation of the edges around a triangle in each move. We show that (i) when restricted to planar triangulations of maximum degree six, the Markov chain is rapidly mixing, and (ii) there exists a triangulation with high degree on which this Markov chain mixes slowly. Next, we consider an "edge-flipping'' chain on the larger state space consisting of 3-orientations of all planar triangulations on a fixed number of vertices. It was also shown previously that this chain connects the state space and we prove that the chain is always rapidly mixing.

Volume: DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)
Section: Proceedings
Published on: January 1, 2012
Imported on: January 31, 2017
Keywords: Schnyder woods,Markov chains,3-orientations,Planar triangulations,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG]
Fundings :
Source : OpenAIRE Research Graph
• Markov Chain Algorithms for Problems from Computer Science and Statistical Physics; Funder: National Science Foundation; Code: 0830367
• AF: Large: Collaborative Research: Random Processes and Randomized Algorithms; Funder: National Science Foundation; Code: 0910584
• Random graph interpolation, Sumset inequalities and Submodular problems; Funder: National Science Foundation; Code: 1101447