Concentration of maximum degree in random planar graphs

Vertex degrees (05C07) Planar graphs; geometric and topological aspects of graph theory (05C10) Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80)

Abstract: Let

P (n, m)

be a graph chosen uniformly at random from the class of all planar graphs on vertex set

[n] := l e f t 1, l d o t s, n i g h t

with

m = m (n)

edges. We show that in the sparse regime, when

m / n l e q 1

, with high probability the maximum degree of

P (n, m)

takes at most two different values. In contrast, this is not true anymore in the dense regime, when

m / n > 1

, where the maximum degree of

P (n, m)

is not concentrated on any subset of

[n]

with bounded size.

Review text

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\).

Recommendations

Cites work

Cited in

(8)

This page was built for publication: Concentration of maximum degree in random planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2673490)