The distribution of the maximum vertex degree in random planar maps (Q1971616)

From MaRDI portal
Revision as of 16:38, 1 February 2024 by Import240129110113 (talk | contribs) (Added link to MaRDI item.)
scientific article
Language Label Description Also known as
English
The distribution of the maximum vertex degree in random planar maps
scientific article

    Statements

    The distribution of the maximum vertex degree in random planar maps (English)
    0 references
    0 references
    0 references
    24 September 2000
    0 references
    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.
    0 references
    rooted triangulations
    0 references
    probability
    0 references
    expectation
    0 references
    variance
    0 references
    random variable
    0 references
    random rooted map
    0 references

    Identifiers