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

Sarah Miracle 1 Dana Randall 1 Amanda Pascoe Streib 2 Prasad Tetali 1, 2
1 GATECH - College of Computing
2 School of Mathematics - School of Mathematics, School of Computer Science
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 : Schnyder woods Markov chains 3-orientations Planar triangulations
Type de document :
Communication dans un congrès
Broutin, Nicolas and Devroye, Luc. 23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'12), 2012, Montreal, Canada. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12), pp.413-424, 2012, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [25 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-01197229
Contributeur : Coordination Episciences Iam <>
Soumis le : vendredi 11 septembre 2015 - 12:54:49
Dernière modification le : mardi 7 mars 2017 - 15:18:44
Document(s) archivé(s) le : mardi 29 décembre 2015 - 00:33:40

Fichier

dmAQ0132.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01197229, version 1

Collections

INSMI | TDS-MACS

Citation

Sarah Miracle, Dana Randall, Amanda Pascoe Streib, Prasad Tetali. Mixing times of Markov chains on 3-Orientations of Planar Triangulations. Broutin, Nicolas and Devroye, Luc. 23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'12), 2012, Montreal, Canada. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12), pp.413-424, 2012, DMTCS Proceedings. 〈hal-01197229〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

205

Téléchargements de fichiers

178

Contact


archive-ouverte@inria.fr