# Mixing times of Markov chains on 3-Orientations of Planar Triangulations

Abstract : 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.
Keywords :
Document type :
Conference papers
Domain :

Cited literature [25 references]

https://hal.inria.fr/hal-01197229
Contributor : Coordination Episciences Iam <>
Submitted on : Friday, September 11, 2015 - 12:54:49 PM
Last modification on : Wednesday, July 31, 2019 - 3:24:16 PM
Long-term archiving on: : Tuesday, December 29, 2015 - 12:33:40 AM

### File

dmAQ0132.pdf
Publisher files allowed on an open archive

### Identifiers

• HAL Id : hal-01197229, version 1

### Citation

Sarah Miracle, Dana Randall, Amanda Pascoe Streib, Prasad Tetali. Mixing times of Markov chains on 3-Orientations of Planar Triangulations. 23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'12), 2012, Montreal, Canada. pp.413-424. ⟨hal-01197229⟩

Record views