Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

Cited literature [25 references]  Display  Hide  Download

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

Collections

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⟩

Share

Metrics

Record views

259

Files downloads

783