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

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$ .
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 11 janvier 2018 - 06:19:44
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

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〉

Partager

Métriques

Consultations de la notice

138

Téléchargements de fichiers

57