The distribution of the number of small cuts in a random planar triangulation

Zhicheng Gao 1 Gilles Schaeffer 2
1 School of Mathematics and Statistics [Ottawa]
2 LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
Abstract : We enumerate rooted 3-connected (2-connected) planar triangulations with respect to the vertices and 3-cuts (2-cuts). Consequently, we show that the distribution of the number of 3-cuts in a random rooted 3-connected planar triangulation with $n+3$ vertices is asymptotically normal with mean $(10/27)n$ and variance $(320/729)n$, and the distribution of the number of 2-cuts in a random 2-connected planar triangulation with $n+2$ vertices is asymptotically normal with mean $(8/27)n$ and variance $(152/729)n$. We also show that the distribution of the number of 3-connected components in a random 2-connected triangulation with $n+2$ vertices is asymptotically normal with mean $n/3$ and variance $\frac{8}{ 27}n$ .
Keywords : cuts random triangulation normal distribution.
Type de document :
Communication dans un congrès
Drmota, Michael and Gittenberger, Bernhard. 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), 2010, Vienna, Austria. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), pp.277-288, 2010, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-01185596
Contributeur : Coordination Episciences Iam <>
Soumis le : jeudi 20 août 2015 - 16:33:47
Dernière modification le : jeudi 10 mai 2018 - 02:06:14
Document(s) archivé(s) le : mercredi 26 avril 2017 - 09:47:15

Fichier

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

Identifiants

  • HAL Id : hal-01185596, version 1

Collections

X | LIX | INSMI | X-LIX | PARISTECH | TDS-MACS | X-DEP-INFO

Citation

Zhicheng Gao, Gilles Schaeffer. The distribution of the number of small cuts in a random planar triangulation. Drmota, Michael and Gittenberger, Bernhard. 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), 2010, Vienna, Austria. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), pp.277-288, 2010, DMTCS Proceedings. 〈hal-01185596〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

205

Téléchargements de fichiers

164

Contact


archive-ouverte@inria.fr