The distribution of the maximum vertex degree in random planar maps (Q1971616): Difference between revisions

Let \(\Delta_n\) denote the maximum vertex degree of a random rooted planar triangulation of an \(n\)-gon. The authors prove: Theorem 1. For rooted triangulations of an \(n\)-gon: \hskip 17mm \(\bullet\quad \text{E}(\Delta_n)= {\log n+\log\log n\over \log 2}+ O(1)\); \hskip 17mm \(\bullet\quad\text{V}(\Delta_n)= O(\log n)\); \hskip 17mm \(\bullet\quad\text{P}\left(\left|\Delta_n- {\log n+ \log\log n\over \log 2} \right|\leq \Omega_n\right)= 1-O\left({1\over\log n}+\left({1\over 2}\right)^{\Omega_n}\right)\), \hskip 17mm for any functions \(\Omega_n\to \infty\). Here P, E and V are used to denote the probability, expectation and variance of a random variable, respectively. The authors prove several other results including: Corollary 2. The probability that a random rooted map has a unique vertex with maximum degree is asymptotic to \hskip 17mm \(\bullet\quad \sum^\infty_{m= -\infty} 2^{m+ y_P(n)}\exp(-2^{m+ y_P(n)+ 1})\approx 0.7215\), for triangulations of an \hskip 17mm \(n\)-gon, \hskip 17mm \(\bullet\quad \sum^\infty_{m= -\infty} \left({6\over 5}\right)^{m+ y_M(n)} \exp\left(-6\left({6\over 5}\right)^{m+ y_M(n)}\right)\approx 0.9141\), for all maps, where \(y_P(n)\) and \(y_M(n)\) are the fractional parts of the solutions to \[ ny\left({1\over 2}\right)^y= 1\quad\text{and}\quad n(10\pi y)^{-{1\over 2}}\left({5\over 6}\right)^y= 1, \] respectively.