Concentration of maximum degree in random planar graphs (Q2673490)

This paper is a study of the concentration of the maximum degree in a random planar graph. The model that is considered in this paper is \(P(n,m)\) which is that of a uniformly selected (labelled) planar graph among the set of planar graphs with \(m\) edges on a given set of vertices of size \(n\). The paper identifies a distinction regarding the concentration of the maximum degree of \(P(n,m)\) within a bounded interval. The first theorem states that if \(m\leq n/2 + O(n^{2/3})\) that with probability \(\to 1\) as \(n\to \infty\) the maximum degree is concentrated in an interval of size 2. The values in this interval are given explicitly through the solution of a certain equation. Then the case where \(m\geq n/2 + \omega (n^{2/3})\) but \(m\leq n + n^{1-\delta}\), for some \(\delta >0\), is considered. In this regime, the maximum degree in the largest and the second largest component of \(P(n,m)\) is considered and it is shown that with probability \(\to 1\) as \(n\to \infty\) both are concentrated in an interval of size at most 2. This is also the case for the maximum degree of the entire \(P(n,m)\). A corollary of these results is that if \(\liminf_{n\to \infty} m/n>0\) but \(m\leq n + n^{1-\delta}\), then the maximum degree is asymptotically equal to \(\log n / \log \log n\). Finally, it is shown that if \(m = \mu n\) where \(\mu \in (1,3)\), then with probability \(\to 1\) as \(n\to \infty\) if the maximum degree is concentrated in an interval, then this has length that is bounded from below by a function tending to \(\infty\) as \(n\to \infty\). This dichotomy provides the counterpart of a classic result of \textit{B. Bollobas} [J. Graph Theory 6, 147--155 (1982; Zbl 0499.05056)] about the random graph \(G(n,m)\) when \(m\) crosses \(n\log n\).