Zhicheng Gao ; Gilles Schaeffer

The distribution of the number of small cuts in a random planar triangulation
dmtcs:2797 
Discrete Mathematics & Theoretical Computer Science,
January 1, 2010,
DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)

https://doi.org/10.46298/dmtcs.2797
The distribution of the number of small cuts in a random planar triangulation
Authors: Zhicheng Gao ^{1}; Gilles Schaeffer ^{2}
NULL##0000000160738574
Zhicheng Gao;Gilles Schaeffer
1 School of Mathematics and Statistics [Ottawa]
2 Laboratoire d'informatique de l'École polytechnique [Palaiseau]
We enumerate rooted 3connected (2connected) planar triangulations with respect to the vertices and 3cuts (2cuts). Consequently, we show that the distribution of the number of 3cuts in a random rooted 3connected 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 2cuts in a random 2connected 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 3connected components in a random 2connected triangulation with $n+2$ vertices is asymptotically normal with mean $n/3$ and variance $\frac{8}{ 27}n$ .
Volume: DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)