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 triangulationArticle
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$ .
Volume: DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)