| HAL-Inria | Publications, software ... of Inria's scientists |
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.
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
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