Concentration of maximum degree in random planar graphs

Mihyun Kang, Michael Missethan Institute of Discrete Mathematics, Graz University of Technology, Steyrergasse 30, 8010 Graz, Austria {kang,missethan}@math.tugraz.at

Abstract.

Let $P(n,m)$ be a graph chosen uniformly at random from the class of all planar graphs on vertex set $[n]:=\left\{1,\ldots,n\right\}$ with $m=m(n)$ edges. We show that in the sparse regime, when $m/n\leq 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.

Key words and phrases:

Random graphs, random planar graphs, maximum degree, balls into bins, Prüfer sequence

Supported by Austrian Science Fund (FWF): I3747 and W1230

1. Introduction and results

1.1. Motivation

The Erdős-Rényi random graph $G(n,m$ ), introduced by Erdős and Rényi [16, 17], is a graph chosen uniformly at random from the class $\mathcal{G}(n,m)$ of all vertex-labelled graphs on vertex set $[n]:=\left\{1,\ldots,n\right\}$ with $m=m(n)$ edges, denoted by $G(n,m)\in_{R}\mathcal{G}(n,m)$ . Since its introduction $G(n,m)$ , together with the closely related binomial random graph $G(n,p)$ , has been intensively studied (see e.g. [20, 30, 5]). A remarkable feature of this model is the ‘concentration’ of many graph parameters. That is, with high probability (meaning with probability tending to 1 as $n$ tends to infinity, whp for short) certain graph parameters in $G(n,m)$ lie in ‘small’ intervals, which only depend on $n$ and $m$ .

The graph parameter we will focus on in this paper is the maximum degree of a graph $H$ , denoted by $\Delta\left(H\right)$ . Erdős and Rényi [16] were the first to consider $\Delta\left(G(n,m)\right)$ and since then, many results on $\Delta\left(G(n,m)\right)$ and, more generally, the degree sequence of $G(n,m)$ were obtained (see e.g. [2, 48, 18, 3, 40, 28, 4]). A particularly interesting result by Bollobás [4] is that $m\sim n\log n$ is a ‘threshold’ for the concentration of $\Delta\left(G(n,m)\right)$ . More formally, whp $\Delta\left(G(n,m)\right)$ takes one of two values when $m=o\left(n\log n\right)$ , while $\Delta\left(G(n,m)\right)$ is not concentrated on any subset of $[n]$ with bounded size when $m=\omega\left(n\log n\right)$ and $m=o\left(n^{2}\right)$ .

Theorem 1.1 ([4]).

Let $m=m(n)=o\left(n\log n\right)$ and $G=G(n,m)\in_{R}\mathcal{G}(n,m)$ . Then there exists a $D=D(n)\in\mathbb{N}$ such that whp $\Delta\left(G\right)\in\left\{D,D+1\right\}$ .

Theorem 1.2 ([4]).

Let $m=m(n)=\omega\left(n\log n\right)$ , $m=o\left(n^{2}\right)$ , and $G=G(n,m)\in_{R}\mathcal{G}(n,m)$ . If $I=I(n)\subseteq[n]$ is such that whp $\Delta\left(G\right)\in I$ , then $\left|I\right|=\omega\left(1\right)$ .

We note that Bollobás [4] actually considered the binomial random graph $G(n,p)$ . But by using standard tools relating $G(n,m)$ and $G(n,p)$ (see e.g. [20, Section 1.1]) one can translate his results as stated in Theorems 1.1 and 1.2.

In recent decades various models of random graphs have been introduced by imposing additional constraints to $G(n,m)$ , e.g. degree restrictions or topological constraints. In particular, random planar graphs and related structures, like random graphs on surfaces and random planar maps, have attained considerable attention [8, 11, 34, 37, 9, 26, 32, 39, 38, 13, 10, 15, 14, 12, 21, 44, 46, 19, 45, 23, 22, 25, 24]. McDiarmid and Reed [38] considered the so-called $n$ -vertex model for random planar graphs, that is, a graph $P(n)$ chosen uniformly at random from the class of all vertex-labelled planar graphs on vertex set $[n]$ . They proved that whp $\Delta\left(P(n)\right)=\Theta\left(\log n\right)$ . Later Drmota, Giménez, Noy, Panagiotou, and Steger [13] used tools from analytic combinatorics and Boltzmann sampling techniques to show that whp $\Delta\left(P(n)\right)$ is concentrated in an interval of length $O\left(\log\log n\right)$ .

A more natural generalisation of $G(n,m)$ seems to be the random planar graph $P(n,m)$ , which is a graph chosen uniformly at random from the class $\mathcal{P}(n,m)$ of all vertex-labelled planar graphs on vertex set $[n]$ with $m=m(n)$ edges, denoted by $P(n,m)\in_{R}\mathcal{P}(n,m)$ . The random planar graph $P(n,m)$ has been studied separately for the ‘sparse’ regime where $m\leq n+o\left(n\right)$ (see [32, 34]) and the ‘dense’ regime where $m=\left\lfloor\mu n\right\rfloor$ for a constant $\mu\in(1,3)$ (see e.g. [26]). In this paper we show, in the flavour of Theorems 1.1 and 1.2, that in the sparse regime whp $\Delta\left(P(n,m)\right)$ takes one of two values (see Theorems 1.6 and 1.4), while in the dense regime $\Delta\left(P(n,m)\right)$ is not concentrated on any subset of $[n]$ with bounded size (see Theorem 1.10).

1.2. Main results

In order to state our main results, we need the following definition, where we denote by $\log$ the natural logarithm.

Definition 1.3.

Let $\nu:\mathbb{N}^{2}\to\mathbb{R}^{+}$ be a function such that $\nu\left(n,k\right)$ is the unique positive zero of

\displaystyle f(x)=f_{n,k}(x)\hskip 1.70709pt:=\hskip 1.70709ptx\log k+x-(x+1/2)\log x-(x-1)\log n.

In case of $n=k$ , we write $\nu\left(n\right):=\nu\left(n,n\right)$ .

In Section 9.1 we will prove that the function $\nu$ is well defined, i.e. $f$ has a unique positive zero. In Lemma 2.11 we will provide some important properties of $\nu$ and in Section 4 we motivate the definition of $\nu$ in the context of the balls-into-bins model.

We distinguish different cases according to which ‘region’ the edge density falls into. The first regime which we consider is when $m\leq n/2+O\left(n^{2/3}\right)$ .

Theorem 1.4.

Let $P=P(n,m)\in_{R}\mathcal{P}(n,m)$ , $m=m(n)\leq n/2+O\left(n^{2/3}\right)$ , and $\varepsilon>0$ . Then we have whp $\left\lfloor\nu\left(n,2m\right)-\varepsilon\right\rfloor\hskip 1.70709pt\leq\hskip 1.70709pt\Delta\left(P\right)\hskip 1.70709pt\leq\hskip 1.70709pt\left\lfloor\nu\left(n,2m\right)+\varepsilon\right\rfloor$ . In particular, whp $\Delta\left(P\right)\in\left\{D,D+1\right\}$ , where $D=D(n):=\left\lfloor\nu\left(n,2m\right)-1/3\right\rfloor$ .

Next, we consider the case where $m\geq n/2+\omega\left(n^{2/3}\right)$ is such that $m\leq n+n^{1-\delta}$ for some $\delta>0$ . Kang and Łuczak [32] and Kang, Moßhammer, and Sprüssel [34] showed that, in contrast to the case when $m\leq n/2+O\left(n^{2/3}\right)$ , in this regime whp the largest component of $P=P(n,m)$ contains significantly more vertices than the second largest component. Therefore, we provide a concentration result on the maximum degree not only for $P$ , but also for the largest component $L\left(P\right)$ of $P$ and the ‘rest’ $R\left(P\right):=P\setminus L\left(P\right)$ . We will see that $\Delta\left(L\left(P\right)\right)$ and $\Delta\left(R\left(P\right)\right)$ are strongly concentrated around $\nu\left(\ell\right)$ and $\nu\left(r\right)$ for suitable $\ell=\ell(n)$ and $r=r(n)$ , respectively.

Definition 1.5.

Let $m=m(n)\geq n/2+\omega\left(n^{2/3}\right)$ be such that $m\leq n+n^{1-\delta}$ for some $\delta>0$ . Then we define $\ell=\ell(n)$ and $r=r(n)$ as follows.

ranges of $m$	$\leavevmode\nobreak\ \leavevmode\nobreak\ \ell\leavevmode\nobreak\ \leavevmode\nobreak\$	$r$
(a) $m=n/2+s$ for $s=s(n)>0$ such that $s=o\left(n\right)$ and $s^{3}n^{-2}\to\infty$	$s$	$n$
(b) $m=dn/2$ where $d=d(n)$ tends to a constant in $\left(1,2\right)$	$n$	$n$
(c) $m=n+t$ for $t=t(n)<0$ such that $t=o\left(n\right)$ and $t^{5}n^{-3}\to-\infty$	$n$	$\left\|t\right\|$
(d) $m=n+t$ for $t=t(n)$ such that $t^{5}n^{-3}$ tends to a constant in $\mathbb{R}$	$n$	$n^{3/5}$
(e) $m=n+t$ for $t=t(n)>0$ such that $t=o\left(n\right)$ and $t^{5}n^{-3}\to\infty$	$n$	$n^{3/2}t^{-3/2}$

We note that $\ell$ and $r$ are chosen such that whp the number of vertices in $L\left(P\right)$ and $R\left(P\right)$ are $\Theta\left(\ell\right)$ and $\Theta\left(r\right)$ , respectively, according to results in [34, 32]. Throughout the paper, we will assume that if $m=m(n)\geq n/2+\omega\left(n^{2/3}\right)$ is such that $m\leq n+n^{1-\delta}$ for some $\delta>0$ , then $m=m(n)$ lies in one of the five regimes considered in Definition 1.5, which is due to the critical phenomena observed in random planar graphs. Our next result states that in all these cases $\Delta\left(P\right)$ , $\Delta\left(L\left(P\right)\right)$ , and $\Delta\left(R\left(P\right)\right)$ are strongly concentrated.

Theorem 1.6.

Let $P=P(n,m)\in_{R}\mathcal{P}(n,m)$ , $L=L\left(P\right)$ be the largest component of $P$ , and $R=P\setminus L$ . Assume $m=m(n)\geq n/2+\omega\left(n^{2/3}\right)$ is such that $m\leq n+n^{1-\delta}$ for some $\delta>0$ . Let $\ell=\ell(n)$ and $r=r(n)$ be as in Definition 1.5 and $\varepsilon>0$ . Then whp

(a)

$\left\lfloor\nu\left(\ell\right)-\varepsilon\right\rfloor+1\hskip 1.70709pt\leq\hskip 1.70709pt\Delta\left(L\right)\hskip 1.70709pt\leq\hskip 1.70709pt\left\lfloor\nu\left(\ell\right)+\varepsilon\right\rfloor+1$ ;
(b)

$\left\lfloor\nu\left(r\right)-\varepsilon\right\rfloor\hskip 1.70709pt\leq\hskip 1.70709pt\Delta\left(R\right)\hskip 1.70709pt\leq\hskip 1.70709pt\left\lfloor\nu\left(r\right)+\varepsilon\right\rfloor$ .

In particular, whp $\Delta\left(P\right)\in\left\{D,D+1\right\}$ , where $D=D(n):=\max\left\{\left\lfloor\nu\left(\ell\right)+2/3\right\rfloor,\left\lfloor\nu\left(r\right)-1/3\right\rfloor\right\}$ .

For example, Theorem 1.6 says that if $m=n/2+s$ for $s=s(n)>0$ such that $s=o\left(n\right)$ and $s^{3}n^{-2}\to\infty$ , known as the weakly supercritical regime, then whp $\left\lfloor\nu\left(s\right)-\varepsilon\right\rfloor+1\hskip 1.70709pt\leq\hskip 1.70709pt\Delta\left(L\right)\hskip 1.70709pt\leq\hskip 1.70709pt\left\lfloor\nu\left(s\right)+\varepsilon\right\rfloor+1$ . In contrast, if $m=dn/2$ where $d=d(n)$ tends to a constant in $\left(1,2\right)$ , which is the so-called intermediate regime, then whp $\left\lfloor\nu\left(n\right)-\varepsilon\right\rfloor+1\hskip 1.70709pt\leq\hskip 1.70709pt\Delta\left(L\right)\hskip 1.70709pt\leq\hskip 1.70709pt\left\lfloor\nu\left(n\right)+\varepsilon\right\rfloor+1$ .

Combining Theorems 1.6 and 1.4 we can determine the asymptotic order of $\Delta\left(P\right)$ in the sparse regime.

Corollary 1.7.

Let $P=P(n,m)\in_{R}\mathcal{P}(n,m)$ and assume $m=m(n)$ is such that $\liminf_{n\to\infty}m/n>0$ and $m\leq n+n^{1-\delta}$ for some $\delta>0$ . Then whp

\displaystyle\Delta\left(P\right)=\left(1+o\left(1\right)\right)\frac{\log n}{\log\log n}.

It is well known that when $m\leq n/2+O\left(n^{2/3}\right)$ , the probability that $G(n,m)$ is planar is bounded away from 0 (see e.g. Theorem 5.2 and [29, 35, 43]) and therefore, $P(n,m)$ ‘behaves’ asymptotically like $G(n,m)$ . However, this is not the case anymore when $m\geq n/2+\omega\left(n^{2/3}\right)$ , since then whp $G(n,m)$ is not planar (see [35, 43]). Theorem 1.6 reveals the following, perhaps surprising, difference between $P=P(n,m)$ and $G=G(n,m)$ in the case that $m=m(n)=dn/2$ where $d=d(n)$ tends to a constant in $\left(1,2\right)$ . Roughly speaking, the maximum degrees $\Delta\left(P\right)$ , $\Delta\left(L\left(P\right)\right)$ , and $\Delta\left(R\left(P\right)\right)$ are independent of $d=d(n)$ . Furthermore, $\Delta\left(L\left(P\right)\right)$ and $\Delta\left(R\left(P\right)\right)$ typically differ at most by two.

Corollary 1.8.

Let $P=P(n,m)\in_{R}\mathcal{P}(n,m)$ , $L=L\left(P\right)$ be the largest component of $P$ , and $R=P\setminus L$ . There exists a $D=D(n)$ such that for all $m=m(n)=dn/2$ where $d=d(n)$ tends to a constant in $\left(1,2\right)$ , we have whp

	$\displaystyle\Delta\left(L\right)$	$\displaystyle\in\left\{D,D+1\right\};$
	$\displaystyle\Delta\left(R\right)$	$\displaystyle\in\left\{D-1,D\right\};$
	$\displaystyle\Delta\left(P\right)$	$\displaystyle\in\left\{D,D+1\right\}.$

In particular, whp $\Delta\left(R\right)\leq\Delta\left(L\right)\leq\Delta\left(R\right)+2$ .

In contrast to Corollary 1.8, $G=G(n,m)$ exhibits a perhaps more intuitive behaviour. If the average degree $d=2m/n$ is growing, then $\Delta\left(G\right)$ and $\Delta\left(L\left(G\right)\right)$ are increasing, while $\Delta\left(R\left(G\right)\right)$ is decreasing. As a consequence, $\Delta\left(L\left(G\right)\right)$ is typically much larger than $\Delta\left(R\left(G\right)\right)$ .

Proposition 1.9.

For $i=1,2$ , let $m_{i}=m_{i}(n)=d_{i}n/2$ where $d_{i}=d_{i}(n)$ tends to a constant $c_{i}>1$ and $G_{i}=G(n,m_{i})\in_{R}\mathcal{G}(n,m_{i})$ . If $c_{1}<c_{2}$ and $G_{1}$ and $G_{2}$ are chosen independently from each other, then whp $\Delta\left(G_{2}\right)-\Delta\left(G_{1}\right)$ , $\Delta\left(L\left(G_{2}\right)\right)-\Delta\left(L\left(G_{1}\right)\right)$ , $\Delta\left(R\left(G_{1}\right)\right)-\Delta\left(R\left(G_{2}\right)\right)$ , and $\Delta\left(L\left(G_{1}\right)\right)-\Delta\left(R\left(G_{1}\right)\right)$ are strictly positive and of order $\Theta\left(\log n/\left(\log\log n\right)^{2}\right)$ .

Proposition 1.9 follows by a generalised version of Theorem 1.1 (see Theorem 5.1 (b)) and classical results on the Erdős-Rényi random graph $G(n,m)$ . (For the sake of completeness, we provide a sketch of the proof of Proposition 1.9 in Appendix A.)

Finally, we consider the dense case when $m=m(n)=\left\lfloor\mu n\right\rfloor$ for $\mu\in(1,3)$ and show that in this regime $\Delta\left(P\right)$ is not concentrated on any subset of $[n]$ with bounded size.

Theorem 1.10.

Let $P=P(n,m)\in_{R}\mathcal{P}(n,m)$ and assume $m=m(n)=\left\lfloor\mu n\right\rfloor$ for $\mu\in(1,3)$ . If $I=I(n)\subseteq[n]$ is such that whp $\Delta\left(P\right)\in I$ , then $\left|I\right|=\omega\left(1\right)$ .

We note that in a planar graph on $n\geq 3$ vertices there are at most $3n-6$ edges, while a general (not necessarily planar) graph can have up to $\binom{n}{2}$ edges. In view of this fact, it seems natural that the ‘transition’ from the two-point concentration to the non-concentration of the maximum degree occurs much earlier in $P(n,m)$ than in $G(n,m)$ , namely at $m\sim n$ in $P(n,m)$ (cf. Theorems 1.4, 1.6 and 1.10) instead of $m\sim n\log n$ in $G(n,m)$ (cf. Theorems 1.1 and 1.2). It is worth noting that the ‘threshold’ where the number of vertices outside the largest component drops from linear to sublinear is $m\sim n$ for the random planar graph $P(n,m)$ , while it is $m\sim n\log n$ in the case of $G(n,m)$ .

1.3. Outline of the paper

The rest of the paper is structured as follows. After giving the necessary definitions, notations, and concepts in Section 2, we provide our proof strategy in Section 3. Section 4 is devoted to the balls-into-bins model, which we use in Sections 5 and 6 to show concentration of the maximum degree in the Erdős-Rényi random graph, in a random graph without complex components, and in a random forest with specified roots, respectively. In Sections 7 and 8 we provide the proofs of our main results. Subsequently in Section 9, we consider the function $\nu\left(n,k\right)$ introduced in Definition 1.3 in more detail. Finally in Section 10, we discuss a possible generalisation of our results and various questions that remain unanswered.

2. Preliminaries

2.1. Notations for graphs

We consider only undirected graphs or multigraphs and we always assume that the graphs are vertex-labelled.

Definition 2.1.

Given a (simple or multi) graph $H$ we denote by

•

$V\left(H\right)$ the vertex set of $H$ and
$v\left({H}\right)$ the order of $H$ , i.e. the number of vertices in $H$ ;
•

$E\left(H\right)$ the edge set of $H$ and
$e\left({H}\right)$ the size of $H$ , i.e. the number of edges in $H$ ;
•

$L\left(H\right)$ the largest component of $H$ (if there are more than one largest component, we pick that which contains the vertex with smallest label);
•

$R\left(H\right):=H\setminus L\left(H\right)$ the graph obtained from $H$ by deleting the largest component;
•

$d_{H}\left(v\right)$ the degree of a vertex $v\in V\left(H\right)$ . If $V\left(H\right)=[n]$ , then we call $\left(d_{H}\left(1\right),\ldots,d_{H}\left(n\right)\right)$ the degree sequence of $H$ .

Definition 2.2.

Given a class $\mathcal{A}$ of graphs (e.g. the class of planar graphs), we denote by $\mathcal{A}(n)$ the subclass of $\mathcal{A}$ containing the graphs on vertex set $[n]$ and by $\mathcal{A}(n,m)$ the subclass of $\mathcal{A}$ containing the graphs on vertex set $[n]$ with $m$ edges, respectively. We write $A(n)\in_{R}\mathcal{A}(n)$ for a graph chosen uniformly at random from $\mathcal{A}(n)$ and $A(n,m)\in_{R}\mathcal{A}(n,m)$ for a graph chosen uniformly at random from $\mathcal{A}(n,m)$ , respectively.

2.2. Random variables and asymptotic notation

Definition 2.3.

Let $S$ be a finite set and let $Y$ and $Z$ be random variables with values in $S$ . Then we say that $Y$ is distributed like $Z$ , denoted by $Y\sim Z$ , if for all $x\in S$ we have $\mathbb{P}\left[Y=x\right]=\mathbb{P}\left[Z=x\right]$ .

Throughout this paper, we use the standard Landau notation and all asymptotics are taken with respect to $n$ , i.e. when $n\to\infty$ . In order to express that two random variables have asymptotically a ‘similar’ distribution, we use the notion of contiguity.

Definition 2.4.

For each $n\in\mathbb{N}$ , let $S=S(n)$ be a finite set and let $Y=Y(n)$ and $Z=Z(n)$ be random variables with values in $S$ . We say that $Z$ is contiguous with respect to $Y$ , denoted by $Z\triangleleft Y$ , if for all sequences $I=I(n)\subseteq S(n)$

\displaystyle\left(\lim\limits_{n\to\infty}\mathbb{P}\left[Y\in I\right]=1\right)\leavevmode\nobreak\ \implies\leavevmode\nobreak\ \left(\lim\limits_{n\to\infty}\mathbb{P}\left[Z\in I\right]=1\right).

2.3. Complex part and core

We say that a component of a graph $H$ is complex if it has at least two cycles. The union of all complex components is called the complex part $Q\left(H\right)$ . We call the graph $H$ complex if all its components are complex. The union of all non-complex components is the non-complex part $U\left(H\right):=H\setminus Q\left(H\right)$ . The core $C\left(H\right)$ , also known as the 2-core, is the maximal subgraph of $Q\left(H\right)$ of minimum degree at least two. We observe that the core $C\left(H\right)$ can be obtained from $H$ by first removing vertices of degree one recursively and then deleting isolated cycles. We emphasise that the core $C\left(H\right)$ is not necessarily connected. We denote by $Q_{L}\left(H\right)$ the component of $Q\left(H\right)$ containing the largest component of the core $L\left(C\left(H\right)\right)$ . The rest of the complex part is denoted by $Q_{S}\left(H\right):=Q\left(H\right)\setminus Q_{L}\left(H\right)$ . We call $Q_{L}\left(H\right)$ and $Q_{S}\left(H\right)$ the large complex part and the small complex part, respectively. We note that the number of vertices in $Q_{L}\left(H\right)$ is not necessarily larger than in $Q_{S}\left(H\right)$ , but it will be true in most cases we consider. Using this decomposition we can split $H$ into the three disjoint parts $Q_{L}\left(H\right)$ , $Q_{S}\left(H\right)$ , and $U\left(H\right)$ . Moreover, we have the relations $C\left(Q_{L}\left(H\right)\right)=L\left(C\left(H\right)\right)$ and $C\left(Q_{S}\left(H\right)\right)=R\left(C\left(H\right)\right)$ .

Later we will construct the large complex part, the small complex part, and the non-complex part of a random planar graph independently of each other. To that end, we will use the following two graph classes.

Definition 2.5.

Let $C$ be a core, i.e. a graph with minimum degree at least two containing no isolated cycles, and $q\in\mathbb{N}$ . Then we denote by $\mathcal{Q}(C,q)$ the class consisting of complex graphs having core $C$ and vertex set $[q]$ . We let $Q(C,q)\in_{R}\mathcal{Q}(C,q)$ be a graph chosen uniformly at random from this class.

Definition 2.6.

We denote by $\mathcal{U}$ the class consisting of all graphs without complex components. For $n,m\in\mathbb{N}$ we let $\mathcal{U}(n,m)\subseteq\mathcal{U}$ be the subclass of all graphs on vertex set $[n]$ with $m$ edges and we write $U(n,m)\in_{R}\mathcal{U}(n,m)$ for a graph chosen uniformly at random from $\mathcal{U}(n,m)$ .

Remark 2.7.

Let $C$ be a core, $q,n,m\in\mathbb{N}$ , and $H\in\mathcal{Q}(C,q)$ be a fixed graph. Then there are precisely $\left|\mathcal{U}(u,w)\right|$ many graphs $H^{\prime}\in\mathcal{P}(n,m)$ whose complex part is $H$ , where $u:=n-q$ and $w:=m-e\left({C}\right)+v\left({C}\right)-q$ . As this number is independent of $H\in\mathcal{Q}(C,q)$ , there is a nice relation between the complex part $Q\left(P\right)$ of the random planar graph $P=P(n,m)$ and $Q(C,q)\in_{R}\mathcal{Q}(C,q)$ , the latter being as in Definition 2.5: Conditioned on the event that the core $C\left(P\right)$ is $C$ and $v\left({Q\left(P\right)}\right)=q$ , the complex part $Q\left(P\right)$ is distributed like $Q(C,q)$ . Similarly, for fixed $\tilde{n},\tilde{m},n,m\in\mathbb{N}$ let $U\left(P\right)$ be the non-complex part of $P$ and $U(\tilde{n},\tilde{m})\in_{R}\mathcal{U}(\tilde{n},\tilde{m})$ be as in Definition 2.6. Then, conditioned on the event that $v\left({U\left(P\right)}\right)=\tilde{n}$ and $e\left({U\left(P\right)}\right)=\tilde{m}$ , the non-complex part $U\left(P\right)$ is distributed like $U(\tilde{n},\tilde{m})$ .

2.4. Conditional random graphs

Given a class $\mathcal{A}$ of graphs it is sometimes quite difficult to directly analyse the random graph $A=A(n)\in_{R}\mathcal{A}(n)$ . In such cases we will use the idea of conditional random graphs. Loosely speaking, we split $\mathcal{A}$ into disjoint subclasses and consider for each subclass $\tilde{\mathcal{A}}$ the random graph $\tilde{A}=\tilde{A}(n)\in_{R}\tilde{\mathcal{A}}(n)$ , in other words, the random graph $A$ conditioned on the event that $A\in\tilde{\mathcal{A}}$ . If we can show that some graph property holds in all these ‘conditional’ random graphs whp, then whp this property holds also in $A$ . The following definition and lemma make that idea more precise.

Definition 2.8.

Given a class $\mathcal{A}$ of graphs, a set $S$ , and a function $\Phi:\mathcal{A}\to S$ , we call a sequence $\mathbf{a}=(a_{n})_{n\in\mathbb{N}}$ feasible for $\left(\mathcal{A},\Phi\right)$ if for each $n\in\mathbb{N}$ there exists a graph $H\in\mathcal{A}(n)$ such that $\Phi(H)=a_{n}$ . Moreover, for each $n\in\mathbb{N}$ we denote by $\left(A\mid\mathbf{a}\right)(n)$ a graph chosen uniformly at random from the set $\left\{H\in\mathcal{A}(n):\Phi(H)=a_{n}\right\}$ . We will often omit the dependence on $n$ and write just $A\mid\mathbf{a}$ (i.e. ‘ $A$ conditioned on $\mathbf{a}$ ’) instead of $\left(A\mid\mathbf{a}\right)(n)$ .

Lemma 2.9 ([33, Lemma 3.2]).

Let $\mathcal{A}$ be a class of graphs, $S$ a set, $\Phi:\mathcal{A}\to S$ a function, $\mathcal{R}$ a graph property, and $A=A(n)\in_{R}\mathcal{A}(n)$ . If for every sequence $\mathbf{a}=(a_{n})_{n\in\mathbb{N}}$ that is feasible for $\left(\mathcal{A},\Phi\right)$ we have whp $A\mid\mathbf{a}\in\mathcal{R}$ , then we have whp $A\in\mathcal{R}$ .

2.5. Internal structure of a random planar graph

In the proofs of our main results we will use some results from [32, 34] on the internal structure of a random planar graph $P(n,m)$ , e.g. asymptotic order of the core, which are reformulated to simplify asymptotic notation.

Theorem 2.10 ([32, 34]).

Let $P=P(n,m)\in_{R}\mathcal{P}(n,m)$ , $C=C\left(P\right)$ be the core, $Q_{L}=Q_{L}\left(P\right)$ the large complex part, $Q_{S}=Q_{S}\left(P\right)$ the small complex part, $U=U\left(P\right)$ the non-complex part, and $L=L\left(P\right)$ the largest component of $P$ . In addition, let $h=h(n)=\omega\left(1\right)$ be a function tending to $\infty$ arbitrarily slowly and $\ell=\ell(n)$ and $r=r(n)$ be as in Definition 1.5. We assume that $m=m(n)\geq n/2+\omega\left(n^{2/3}\right)$ is such that $m\leq n+n^{1-\delta}$ for some $\delta>0$ and let $\beta:=\min\left\{\delta/2,1/5\right\}$ . Then whp the following hold.

(a)

$\Delta\left(C\right)=\Theta\left(1\right)$ ;
(b)

$v\left({L\left(C\right)}\right)=O\left(\ell^{1-\beta}\right)$ ;
(c)

$Q_{L}=L$ ;
(d)

$v\left({Q_{L}}\right)=\Theta\left(\ell\right)$ ;
(e)

$v\left({Q_{S}}\right)=O\left(hr^{2/3}\right)$ ;
(f)

$v\left({U}\right)=\Theta\left(r\right)$ ;
(g)

$e\left({U}\right)=v\left({U}\right)/2+O\left(hv\left({U}\right)^{2/3}\right)$ .

2.6. Properties of $\nu\left(n,k\right)$

We will use the following basic properties of $\nu\left(n,k\right)$ introduced in Definition 1.3.

Lemma 2.11.

Let the function $\nu\left(n,k\right)$ be defined as in Definition 1.3 and $\nu\left(n\right)=\nu\left(n,n\right)$ . Then we have

(a)

$\nu\left(n,k\right)>1$ for all $n,k\in\mathbb{N}$ ;
(b)

if $k=k(n)=O\left(n^{1/3}\right)$ , then $\nu\left(n,k\right)\leq 5/3+o\left(1\right)$ ;
(c)

if $k=k(n)=\Theta\left(n\right)$ , then $\nu\left(n,k\right)=\left(1+o\left(1\right)\right)\log n/\log\log n$ ;
(d)

$\nu\left(n,k\right)$ is strictly increasing in the argument $k$ ;
(e)

if $k=k(n)=O\left(n\right)$ , then $\nu\left(n,k\right)=\omega\left(k/n\right)$ ;
(f)

if $k=k(n)=\Theta\left(n\right)$ and $d=d(n)=o\left(n\left(\log\log n\right)^{2}/\log n\right)$ , then $\nu\left(n,k+d\right)-\nu\left(n,k\right)=o\left(1\right)$ ;
(g)

$\nu\left(n\right)$ is strictly increasing;
(h)

if $c=c(n)=\Theta\left(1\right)$ and $k=k(n)=\Theta\left(n\right)$ , then $\nu\left(cn,ck\right)=\nu\left(n,k\right)+o\left(1\right)$ ;
(i)

if $c=c(n)=\Theta\left(1\right)$ , then $\nu\left(n,cn\right)-\nu\left(n\right)=\left(\log c+o\left(1\right)\right)\log n/\left(\log\log n\right)^{2}$ .

We provide a proof of Lemma 2.11 in Section 9.2.

3. Proof strategy

In order to prove Theorem 1.4 on the two-point concentration of $\Delta\left(P(n,m)\right)$ when $m\leq n/2+O\left(n^{2/3}\right)$ , we will use the known fact that with positive probability the Erdős-Rényi random graph $G(n,m)$ is planar in this regime (see Theorem 5.2). Thus, it suffices to determine $\Delta\left(G(n,m)\right)$ instead of $\Delta\left(P(n,m)\right)$ , which we will do by proving that $\Delta\left(G(n,m)\right)$ ‘behaves’ like the maximum load of an appropriate ball-into-bins model (see Section 3.3 for details).

The proof of Theorem 1.6 will be based on the following result on the typical structure of $P=P(n,m)$ , which can be derived by using statements from [32, 34]: Informally speaking, the largest component $L=L\left(P\right)$ consists of a family $F$ of rooted tree components, which are connected via ‘few’ edges between the roots of the tree components that are exactly the vertices of $L\left(C\left(P\right)\right)$ , i.e. the largest component of the core. The number of tree components in $F$ is much smaller than $v\left({F}\right)$ , because the order of the core is typically much smaller than the order of the largest component (see Theorem 2.10 (b) and (d)). In addition, the remaining part $R=R\left(P\right)=P\setminus L$ ‘behaves’ like an Erdős-Rényi random graph $G(\tilde{n},\tilde{n}/2)$ for a suitable $\tilde{n}=\tilde{n}(n)$ . We refer to Figure 1 for an illustration of this structure.

Then we will derive the two-point concentration of $\Delta\left(R\right)$ by studying $G(\tilde{n},\tilde{n}/2)$ . Using the property that the number of tree components in $F$ , and therefore also the number of roots, is small compared to $v\left({F}\right)$ , we will show that the degrees of the roots are typically much smaller than $\Delta\left(F\right)$ (see Theorem 6.3 (b)). Together with the fact that the number of ‘additional’ edges connecting the roots is ‘small’, this will yield $\Delta\left(L\right)=\Delta\left(F\right)$ . Then the two-point concentration of $\Delta\left(L\right)$ will follow by analysing $\Delta\left(F\right)$ via the balls-into-bins model and Prüfer sequences (see Section 6). In the following sections we will describe these ideas in more detail. In Section 3.1 we will use a graph decomposition and conditional random graphs to make the aforementioned structural result on $P$ more formal. Subsequently, we determine the maximum degrees of $F$ and $G(n,m)$ in Sections 3.2 and 3.3, respectively.

Figure 1. Typical structure of

P=P(n,m)

when

m

is as in Theorem 1.6: The largest component

L=L\left(P\right)

consists of a family of rooted tree components, which are connected via ‘few’ edges (drawn with thin lines) between the roots (square boxes). The remaining part

R=P\setminus L

‘behaves’ like an Erdős-Rényi random graph

G(\tilde{n},\tilde{n}/2)

for a suitable

\tilde{n}=\tilde{n}(n)

3.1. Decomposition and conditional random graphs

Instead of considering $L$ and $R$ directly, we will actually split the random planar graph $P$ into the large complex part $Q_{L}=Q_{L}\left(P\right)$ , the small complex part $Q_{S}=Q_{S}\left(P\right)$ , and the non-complex part $U=U\left(P\right)$ (see Section 2.3 for a formal definition of $Q_{L}$ , $Q_{S}$ , and $U$ ). We then use the fact that by Theorem 2.10 (c) we have whp

\displaystyle L=Q_{L},

(1)

which also implies that whp $R=Q_{S}\cup U$ . In order to analyse $Q_{L}$ , $Q_{S}$ , and $U$ , we will use the concept of conditional random graphs (see Section 2.4): For given $\lambda,\sigma\in\mathbb{N}$ and a core $C$ , we denote by $\tilde{P}$ the random planar graph $P$ conditioned on the event that $C\left(P\right)=C$ , $v\left({Q_{L}\left(P\right)}\right)=\lambda$ , and $v\left({Q_{S}\left(P\right)}\right)=\sigma$ . By Remark 2.7 we have

$\displaystyle Q_{L}\left(\tilde{P}\right)$	$\displaystyle\sim Q\left(L\left(C\right),\lambda\right),$	(2)
$\displaystyle Q_{S}\left(\tilde{P}\right)$	$\displaystyle\sim Q\left(R\left(C\right),\sigma\right),$	(3)
$\displaystyle U\left(\tilde{P}\right)$	$\displaystyle\sim U(u,w),$	(4)

where the random graphs on the right hand side are as defined in Definitions 2.5 and 2.6, $L\left(C\right)$ the largest component of $C$ , $R\left(C\right)=C\setminus L\left(C\right)$ , $u:=n-\lambda-\sigma$ , and $w:=m-e\left({C}\right)+v\left({C}\right)-\lambda-\sigma$ .

Roughly speaking, there is the following elementary but useful relation between the ‘conditional’ random graph $\tilde{P}$ and the original random planar graph $P$ (see Lemma 2.9): If for all ‘typical’ choices of $C$ , $\lambda$ , and $\sigma$ whp a graph property holds in $\tilde{P}$ , then whp this property holds in $P$ . In order to determine what ‘typical’ choices of $C$ , $\lambda$ , and $\sigma$ are, we use known results on the internal structure of $P$ (see Theorem 2.10). For example, if we know that whp the core $C\left(P\right)$ satisfies a certain structure, e.g. the maximum degree is bounded or the number of vertices lies in a certain interval, then typical choices of $C$ are those cores having this structure.

Due to this relation between $P$ and $\tilde{P}$ and (2)–(4) it suffices to consider the random graphs $Q\left(C,q\right)$ and $U(n,m)$ for fixed values of $C$ , $q$ , $n$ , and $m$ . We will see that if we consider $U(n,m)$ , then we always have $m=n/2+O\left(n^{2/3}\right)$ . It is well known that in this regime the Erdős-Rényi random graph $G(n,m)$ has with positive probability no complex components (see Theorem 5.2). Hence, we can consider $\Delta\left(G(n,m)\right)$ instead of $\Delta\left(U(n,m)\right)$ , which we will do in Section 3.3. Furthermore, in Section 3.2 we will study $Q\left(C,q\right)$ by using the balls-into-bins model.

We emphasize that the decomposition $P=Q_{L}\leavevmode\nobreak\ \dot{\cup}\leavevmode\nobreak\ Q_{S}\leavevmode\nobreak\ \dot{\cup}\leavevmode\nobreak\ U$ describes the structure of $P$ as stated at the beginning of Section 3 and illustrated in Figure 1: By (1) the large complex part $Q_{L}$ corresponds to the largest component $L=L\left(P\right)$ . Using (2) this implies that the asymptotic behaviour of $L$ can be deduced by that of $Q\left(C,q\right)$ for a suitable core $C$ and $q\in\mathbb{N}$ . The random graph $Q\left(C,q\right)$ can be constructed by replacing each vertex of $C$ randomly by a rooted tree component such that a complex graph with $q$ vertices is obtained. Furthermore, in our applications $\Delta\left(C\right)$ will be bounded and $v\left({C}\right)$ will be ‘small’ compared to $q$ (see Theorem 2.10 (a) and (b)). This implies that $Q\left(C,q\right)$ , and therefore also $L$ , consists of a family of rooted tree components (containing the edges not lying in $C$ ), which are connected via ‘few’ additional edges (which are the edges lying in $C$ ). For the structure of the remaining part $R=P\setminus L$ we observe that $R$ corresponds to $Q_{S}\cup U$ (see (1)). Combining the facts that $v\left({Q_{S}}\right)$ will be ‘small’ compared to $v\left({U}\right)$ and $e\left({U}\right)\approx v\left({U}\right)/2$ (see Theorem 2.10 (e) and (g)) with (4), we obtain that $R$ is closely related to $U(\tilde{n},\tilde{n}/2)$ , and therefore also to $G(\tilde{n},\tilde{n}/2)$ , for a suitable $\tilde{n}\in\mathbb{N}$ .

3.2. Random complex part and forests with specified roots

Let $C$ be a core (on vertex set $[v\left({C}\right)]$ ) and $q\in\mathbb{N}$ . In Definition 2.5 we denoted by $Q\left(C,q\right)$ a graph chosen uniformly at random from the family $\mathcal{Q}(C,q)$ of all complex graphs with core $C$ and vertex set $[q]$ . Moreover, we let $\mathcal{F}(n,t)$ be the class of forests on vertex set $[n]$ consisting of $t$ tree components such that each vertex from $[t]$ lies in a different tree component. The elements in $\mathcal{F}(n,t)$ are called forests with specified roots and the vertices in $[t]$ roots. For simplicity, we will often just write forest instead of forest with specified roots. We can construct $Q=Q\left(C,q\right)$ by choosing a random forest $F=F(q,v\left({C}\right))\in_{R}\mathcal{F}(q,v\left({C}\right))$ and replacing each vertex $v$ in $C$ by the tree component with root $v$ . For the degrees of vertices in $Q$ we obtain $d_{Q}\left(v\right)=d_{C}\left(v\right)+d_{F}\left(v\right)$ for $v\in C$ and $d_{Q}\left(v\right)=d_{F}\left(v\right)$ otherwise. In our applications we will have that $\Delta\left(C\right)$ is bounded and $v\left({C}\right)=O\left(q^{1-\beta}\right)$ for some $\beta>0$ , i.e. $v\left({C}\right)$ is ‘small’ compared to $q$ (see Theorem 2.10 (a), (b), and (d)). This will imply that whp $\Delta\left(Q\right)=\Delta\left(F\right)$ (see Theorem 6.4).

In order to determine $\Delta\left(F\right)$ , we will introduce a bijection between $\mathcal{F}(n,t)$ and $\mathcal{S}\left(n,t\right):=[n]^{n-t-1}\times[t]$ similar to Prüfer sequences for trees (see Section 6.1). Given a forest $F\in\mathcal{F}(n,t)$ we recursively delete the leaf, i.e. a vertex with degree one, with largest label and thereby build a sequence by noting the unique neighbours of the leaves. We will show in Theorem 6.1 that this is indeed a bijection and that the degree of a vertex $v$ is determined by the number of occurrences of $v$ in the sequence (see (13)). It is straightforward to construct a random element from $\mathcal{S}\left(n,t\right)$ by a balls-into-bins model such that the load of a bin equals the number of occurrences in the sequence of the corresponding element. Thus, we will derive the concentration of the maximum degree $\Delta\left(F\right)$ from a concentration result on the maximum load. We refer to Figure 3 for an illustration of the construction of $Q\left(C,q\right)$ via the random forest $F$ and the balls-into-bins model.

3.3. Erdős-Rényi random graph and the balls-into-bins model

Given $n$ bins $\mathcal{B}_{1},\ldots,\mathcal{B}_{n}$ and $2m$ balls $B_{1},\ldots,B_{2m}$ we denote by $A_{i}$ the index of the bin to which the $i$ -th ball $B_{i}$ is assigned for each $i\in[2m]$ . We will consider the random multigraph $M$ with $V\left(M\right)=[n]$ and $E\left(M\right)=\left\{\left\{A_{2i-1},A_{2i}\right\}\mid i\in[m]\right\}$ (see also Figure 2). We will see that conditioned on $M$ being simple, $M$ is distributed like $G(n,m)$ . Furthermore, we will show that as long as $m=O\left(n\right)$ , with positive probability $M$ is simple. Hence, the concentration of $\Delta\left(G(n,m)\right)$ will follow by the concentration of the maximum load of a bin (see Theorem 4.1).

Figure 2. Construction of a multigraph

M

via the balls-into-bins model. In (a) we have

n=5

bins,

2m=8

balls, and

A_{1}=5,A_{2}=3,A_{3}=5,\ldots,A_{8}=3

. In (b) this results in a multigraph

M

with

V\left(M\right)=[5]

and

E\left(M\right)=\left\{\{5,3\},\{5,1\},\{2,5\},\{2,3\}\right\}

. The maximum load of a bin (

=3

) corresponds to the maximum degree

\Delta\left(M\right)=3

M

3.4. Double counting

To prove Theorem 1.10, we will combine results on the asymptotic number of planar graphs from [26] (see Theorem 8.1) and a double counting argument (see Lemma 8.2) and deduce that for all fixed $k,l\in\mathbb{N}$ we have

\displaystyle\liminf_{n\to\infty}\leavevmode\nobreak\ \mathbb{P}\left[P\text{ has }k\text{ isolated vertices and }l\text{ isolated edges}\right]>0,

(5)

where we call a vertex isolated if it has degree zero and say that an edge is isolated if both endpoints have degree one. Then we introduce an operation that uses an isolated vertex and two isolated edges to increase the maximum degree of a graph by one (see Figure 4). Starting with a graph that has ‘many’ isolated vertices and isolated edges, we can repeatedly apply this operation to create lots of graphs with various maximum degrees (see Lemma 8.4). Together with (5) this will imply that also $\Delta\left(P\right)$ takes ‘many’ different values.

4. Balls into bins

Balls-into-bins models have been extensively studied in the literature (see e.g. [31, 41]). Throughout the paper, we will use the following model. Given $n$ bins $\mathcal{B}_{1},\ldots,\mathcal{B}_{n}$ we sequentially assign $k$ balls $B_{1},\ldots,B_{k}$ to those $n$ bins by choosing a bin for each ball, independently and uniformly at random. Let $\mathbf{A}=\left(A_{1},\ldots,A_{k}\right)$ be the location vector, i.e. $A_{i}$ is the index of the bin to which the $i$ -th ball $B_{i}$ is assigned. For each $j\in[n]$ we call the number of balls in the $j$ -th bin $\mathcal{B}_{j}$ the load $\lambda_{j}=\lambda_{j}(\mathbf{A})$ . We write $\mathbf{\lambda}=\mathbf{\lambda}(\mathbf{A})=\left(\lambda_{1},\ldots,\lambda_{n}\right)$ for the vector of all loads and denote by $\lambda^{\ast}=\lambda^{\ast}(\mathbf{A})=\max_{j\in[n]}\lambda_{j}$ the maximum load in a bin. For $t\in[n]$ we let $\lambda^{\ast}_{t}=\lambda^{\ast}_{t}(\mathbf{A})=\max_{j\in[t]}\lambda_{j}$ be the maximum load among the first $t$ bins $\mathcal{B}_{1},\ldots,\mathcal{B}_{t}$ . We write $\operatorname{BB}\left(n,k\right)$ for a random vector distributed like the location vector $\mathbf{A}$ of a balls-into-bins experiment with $n$ bins and $k$ balls, denoted by

\displaystyle\mathbf{A}\sim\operatorname{BB}\left(n,k\right)

and $\operatorname{M}\left(n,k\right)$ for a random variable distributed like the maximum load $\lambda^{\ast}$ , which we denote by

\displaystyle\lambda^{\ast}=\lambda^{\ast}(\mathbf{A})\sim\operatorname{M}\left(n,k\right).

Gonnet [27] proved in the case $n=k$ that whp $\operatorname{M}\left(n,n\right)=\left(1+o\left(1\right)\right)\log n/\log\log n$ . Later Raab and Steger [47] considered $\operatorname{M}\left(n,k\right)$ for different ranges of $k$ . Amongst other results, they showed that whp $\operatorname{M}\left(n,k\right)=\left(1+o\left(1\right)\right)\log n/\log\log n$ is still true, as long as $k=\Theta\left(n\right)$ . In the following we refine their result, showing that if $k=O\left(n\right)$ , then whp $\operatorname{M}\left(n,k\right)$ is actually concentrated at two values.

Before proving that rigorously, we motivate this result by providing the following heuristic. For $l=l(n)\in\mathbb{N}$ we let $X^{(l)}$ be the number of bins with load $l$ . We have

\displaystyle\mathbb{E}\left[X^{(l)}\right]=n\binom{k}{l}\left(1/n\right)^{l}\left(1-1/n\right)^{k-l}=:\mu(l).

(6)

We expect that the load $l$ of a bin is much smaller than $k$ and therefore we have

\displaystyle\mu(l)=\Theta\left(1\right)k^{l}e^{l}l^{-l-1/2}n^{-l+1}.

Intuitively, the maximum load $\lambda^{\ast}\sim\operatorname{M}\left(n,k\right)$ should be close to the largest $l$ for which $\mu(l)=\Theta\left(1\right)$ is satisfied, in other words, $\log\left(\mu(\lambda^{\ast})\right)$ should be close to 0. This motivates the definition of $\nu\left(n,k\right)$ in Definition 1.3 as the unique positive zero of the function

\displaystyle f(l)=f_{n,k}(l):=l\log k+l-(l+1/2)\log l-(l-1)\log n,

which is asymptotically equal to $\log\left(\mu(l)\right)$ up to an additive constant. We will use the first and second moment method (see e.g. [1, 20]) to make that heuristic rigorous and show that the maximum load $\lambda^{\ast}\sim\operatorname{M}\left(n,k\right)$ is strongly concentrated around $\nu\left(n,k\right)$ .

Theorem 4.1.

If $k=k(n)=O\left(n\right)$ and $\varepsilon>0$ , then whp

\displaystyle\left\lfloor\nu\left(n,k\right)-\varepsilon\right\rfloor\hskip 1.70709pt\leq\hskip 1.70709pt\operatorname{M}\left(n,k\right)\hskip 1.70709pt\leq\hskip 1.70709pt\left\lfloor\nu\left(n,k\right)+\varepsilon\right\rfloor.

Proof.

Let $\mathbf{A}\sim\operatorname{BB}\left(n,k\right)$ be the location vector, $\lambda_{j}=\lambda_{j}(\mathbf{A})$ the load of bin $\mathcal{B}_{j}$ for each $j\in[n]$ , and $\lambda^{\ast}=\lambda^{\ast}(\mathbf{A})\sim\operatorname{M}\left(n,k\right)$ the maximum load. First we consider the case $k\leq n^{1/3}$ . Then we have

\displaystyle\mathbb{P}\left[\lambda^{\ast}=1\right]=\prod_{i=1}^{k-1}\left(1-\frac{i}{n}\right)\hskip 1.70709pt\geq\hskip 1.70709pt\left(1-\frac{k}{n}\right)^{k}=1-o\left(1\right).

(7)

Due to Lemma 2.11 (a) and (b) we have $1<\nu\left(n,k\right)\leq 7/4$ for $n$ large enough. Together with (7) this shows the statement for the case $k\leq n^{1/3}$ . Hence, it remains to consider the case $k>n^{1/3}$ . For $l\in[k]$ and $j\in[n]$ we let $X_{j}^{(l)}=1$ if $\lambda_{j}=l$ , i.e. the number $\lambda_{j}$ of balls (among $k$ balls) in the $j$ -th bin $\mathcal{B}_{j}$ is equal to $l$ , and $X_{j}^{(l)}=0$ otherwise. In addition, we let $X^{(l)}=\sum_{j=1}^{n}X_{j}^{(l)}$ be the number of bins with load $l$ . Then we have $\mathbb{P}\left[X_{j}^{(l)}=1\right]=\binom{k}{l}\left(1/n\right)^{l}\left(1-1/n\right)^{k-l}$ and obtain (6). If $l=O\left(k^{1/2}\right)$ , then $\binom{k}{l}=\Theta\left(1\right)k^{l}e^{l}/l^{l+1/2}$ , where we used Stirling’s formula for $l!$ . Hence, we get

\displaystyle\mu(l)=\Theta\left(1\right)\frac{k^{l}e^{l}}{l^{l+1/2}n^{l-1}},

(8)

because $\left(1-1/n\right)^{k-l}=\Theta(1)$ . For an upper bound of the maximum load $\lambda^{\ast}$ we will use the first moment method. Let $l^{\ast}=l^{\ast}(n):=\left\lfloor\nu\left(n,k\right)+\varepsilon\right\rfloor+1$ and $\tau=\tau(n):=l^{\ast}-\nu\left(n,k\right)\geq\varepsilon$ . Due to Lemma 2.11 (c) and (d) and the assumption $k>n^{1/3}$ we have $l^{\ast}=O\left(k^{1/2}\right)$ . Thus, equation (8) holds for $l=l^{\ast}$ and by the definition of $\nu=\nu\left(n,k\right)$ we obtain

\displaystyle\mu\left(l^{\ast}\right)=\Theta\left(1\right)\frac{k^{\nu+\tau}e^{\nu+\tau}}{\left(\nu+\tau\right)^{\nu+\tau+1/2}n^{\nu+\tau-1}}=\Theta\left(1\right)\left(\frac{ke}{n\left(\nu+\tau\right)}\right)^{\tau}\left(\frac{\nu}{\nu+\tau}\right)^{\nu+1/2}.

(9)

Together with Lemma 2.11 (e) this yields $\mu\left(l^{\ast}\right)=o\left(1\right)$ . Due to Lemma 2.11 (e) we have $\mu\left(l+1\right)/\mu\left(l\right)=\left(k-l\right)/\left(\left(l+1\right)\left(n-1\right)\right)=o(1)$ for all $l\geq l^{\ast}$ . Hence,

\displaystyle\mathbb{P}\left[\lambda^{\ast}\geq l^{\ast}\right]\hskip 1.70709pt\leq\hskip 1.70709pt\sum_{l\geq l^{\ast}}\mu(l)=\left(1+o\left(1\right)\right)\mu(l^{\ast})=o(1).

For a lower bound, we will show that $\mathbb{P}\left[X^{\left(l_{\ast}\right)}>0\right]=1-o(1)$ , where $l_{\ast}=l_{\ast}(n):=\left\lfloor\nu\left(n,k\right)-\varepsilon\right\rfloor$ , using the second moment method. In the following we consider the random variables $X_{j}^{(l)}$ and $X^{(l)}$ only for $l=l_{\ast}$ and therefore we use $X_{j}=X_{j}^{\left(l_{\ast}\right)}$ and $X=X^{\left(l_{\ast}\right)}$ for simplicity. In order to apply the second moment method, we will show $\mathbb{E}\left[X\right]=\omega\left(1\right)$ and $\mathbb{E}\left[X_{i}X_{j}\right]=\left(1+o\left(1\right)\right)\mathbb{E}\left[X_{i}\right]\mathbb{E}\left[X_{j}\right]$ for all $i\neq j$ . We let $\rho=\rho(n):=\nu-l_{\ast}\geq\varepsilon$ and by (8), Lemma 2.11 (e), and the definition of $\nu$ we obtain

\displaystyle\mu\left(l_{\ast}\right)=\Theta\left(1\right)\frac{k^{\nu-\rho}e^{\nu-\rho}}{\left(\nu-\rho\right)^{\nu-\rho+1/2}n^{\nu-\rho-1}}=\Theta\left(1\right)\left(\frac{n\left(\nu-\rho\right)}{ke}\right)^{\rho}\left(\frac{\nu}{\nu-\rho}\right)^{\nu+1/2}=\omega\left(1\right).

Next, we note that conditioned on the event $X_{i}=1$ , i.e. $\lambda_{i}=l_{\ast}$ , the loads $\lambda_{j}$ for $j\neq i$ are distributed like the loads of a balls-into-bins experiment with $n-1$ bins and $k-l_{\ast}$ balls, and thus

\displaystyle\mathbb{P}\left[X_{j}=1\;\middle|\;X_{i}=1\right]\hskip 1.70709pt=\hskip 1.70709pt\binom{k-l_{\ast}}{l_{\ast}}\left(1/(n-1)\right)^{l_{\ast}}\left(1-1/(n-1)\right)^{k-2l_{\ast}}.

Hence, we obtain

\displaystyle\frac{\mathbb{E}\left[X_{i}X_{j}\right]}{\mathbb{E}\left[X_{i}\right]\mathbb{E}\left[X_{j}\right]}\hskip 1.70709pt=\hskip 1.70709pt\frac{\mathbb{P}\left[X_{j}=1\;\middle|\;X_{i}=1\right]}{\mathbb{P}\left[X_{j}=1\right]}\hskip 1.70709pt=\hskip 1.70709pt\frac{\binom{k-l_{\ast}}{l_{\ast}}\left(1/(n-1)\right)^{l_{\ast}}\left(1-1/(n-1)\right)^{k-2l_{\ast}}}{\binom{k}{l_{\ast}}\left(1/n\right)^{l_{\ast}}\left(1-1/n\right)^{k-l_{\ast}}}\hskip 1.70709pt=\hskip 1.70709pt1+o\left(1\right),

where we used the assumption $k>n^{1/3}$ and the fact $l_{\ast}=O\left(\log n/\log\log n\right)$ due to Lemma 2.11 (c) and (d). Thus, by the second moment method we obtain $\mathbb{P}\left[X>0\right]=1-o(1)$ , which finishes the proof. ∎

Next, we show that if we consider a ‘small’ subset of bins, then the maximum load in one of these bins is significantly smaller than the maximum load of all bins. We will use this fact later when we relate random forests to the balls-into-bins model (see Section 6), in which this ‘small’ subset will correspond to the set of all roots.

Lemma 4.2.

Let $k=k(n)$ and $t=t(n)\in\mathbb{N}$ be such that $k=\Theta\left(n\right)$ and $t=O\left(n^{1-\beta}\right)$ for some $\beta>0$ . Let $\mathbf{A}\sim\operatorname{BB}\left(n,k\right)$ , $\lambda^{\ast}=\lambda^{\ast}(\mathbf{A})\sim\operatorname{M}\left(n,k\right)$ be the maximum load, and $\lambda^{\ast}_{t}=\lambda^{\ast}_{t}(\mathbf{A})$ be the maximum load in one of the first $t$ bins. Then, whp $\lambda^{\ast}-\lambda^{\ast}_{t}\hskip 1.70709pt=\hskip 1.70709pt\omega\left(1\right)$ .

Proof.

We observe that $\lambda^{\ast}-\lambda^{\ast}_{t}$ is strictly decreasing in $t$ . Thus, it suffices to show $\lambda^{\ast}-\lambda^{\ast}_{t}\hskip 1.70709pt=\hskip 1.70709pt\omega\left(1\right)$ for $t=\left\lfloor n^{1-\beta}\right\rfloor$ and $\beta\in(0,1)$ . We denote by $S_{t}$ the total number of balls in the first $t$ bins. We have $\mathbb{E}\left[S_{t}\right]=tk/n$ and $\mathbb{V}\left[S_{t}\right]\leq\mathbb{E}\left[S_{t}\right]$ . Hence, by Chebyshev’s inequality, we have whp

\displaystyle S_{t}\hskip 1.70709pt\leq\hskip 1.70709pt\frac{tk}{n}+\left(\frac{tk}{n}\right)^{2/3}=:\bar{l}=\bar{l}(n).

(10)

Conditioned on the event $S_{t}=l$ for $l\in\mathbb{N}$ , $\lambda^{\ast}_{t}$ is distributed like $\operatorname{M}\left(t,l\right)$ . Thus,

	$\displaystyle\mathbb{P}\left[\lambda^{\ast}_{t}\hskip 1.70709pt\leq\hskip 1.70709pt\left\lfloor\nu\left(t,\bar{l}\right)\right\rfloor+1\right]$	$\displaystyle\hskip 1.70709pt\geq\hskip 1.70709pt\sum_{l=1}^{\bar{l}}\mathbb{P}\big{[}S_{t}=l\big{]}\mathbb{P}\left[\lambda^{\ast}_{t}\hskip 1.70709pt\leq\hskip 1.70709pt\left\lfloor\nu\left(t,\bar{l}\right)\right\rfloor+1\;\middle\|\;S_{t}=l\right]$
		$\displaystyle\hskip 1.70709pt\geq\hskip 1.70709pt\mathbb{P}\left[S_{t}\leq\bar{l}\right]\mathbb{P}\left[\operatorname{M}\left(t,\bar{l}\right)\hskip 1.70709pt\leq\hskip 1.70709pt\left\lfloor\nu\left(t,\bar{l}\right)\right\rfloor+1\right]\hskip 1.70709pt=\hskip 1.70709pt\left(1-o\left(1\right)\right),$

where the last equality follows from Theorem 4.1 and (10). Due to Lemma 2.11 (c) and the assumption $t=\left\lfloor n^{1-\beta}\right\rfloor$ we get $\nu\left(t,\bar{l}\right)=\left(1+o\left(1\right)\right)\log t/\log\log t=\left(1-\beta+o\left(1\right)\right)\log n/\log\log n$ , which yields whp $\lambda^{\ast}_{t}\leq\left(1-\beta+o\left(1\right)\right)\log n/\log\log n$ . By Lemma 2.11 (c) we have whp $\lambda^{\ast}=\left(1+o\left(1\right)\right)\log n/\log\log n$ . Hence, we obtain whp $\lambda^{\ast}-\lambda^{\ast}_{t}\hskip 1.70709pt\geq\hskip 1.70709pt\left(\beta+o\left(1\right)\right)\log n/\log\log n=\omega\left(1\right)$ , as desired. ∎

5. Erdős-Rényi random graph and graphs without complex components

We start this section by providing a relation between the degree sequence of the Erdős-Rényi random graph $G(n,m)$ and the loads of a balls-into-bins model. In particular, this yields a refined version of Theorem 1.1.

Theorem 5.1.

Let $m=m(n)=O\left(n\right)$ and $\mathbf{d}=\mathbf{d}(n)=\left(d_{G}\left(1\right),\ldots,d_{G}\left(n\right)\right)$ be the degree sequence of $G=G(n,m)\in_{R}\mathcal{G}(n,m)$ . Moreover, let $\mathbf{A}=\mathbf{A}(n)\sim\operatorname{BB}\left(n,2m\right)$ , $\mathbf{\lambda}=\mathbf{\lambda}(n)=\mathbf{\lambda}(\mathbf{A})$ be the vector of loads of $\mathbf{A}$ , and $\varepsilon>0$ . Then

(a)

the degree sequence $\mathbf{d}$ is contiguous with respect to $\mathbf{\lambda}$ , i.e. $\mathbf{d}\triangleleft\mathbf{\lambda}$ ;
(b)

whp $\left\lfloor\nu\left(n,2m\right)-\varepsilon\right\rfloor\hskip 1.70709pt\leq\hskip 1.70709pt\Delta\left(G\right)\hskip 1.70709pt\leq\hskip 1.70709pt\left\lfloor\nu\left(n,2m\right)+\varepsilon\right\rfloor$ .

Proof.

We consider the random multigraph $M$ given by $V\left(M\right)=[n]$ and $E\left(M\right)=\left\{\left\{A_{2i-1},A_{2i}\right\}\mid i\in[m]\right\}$ , where $\mathbf{A}=\left(A_{1},\ldots,A_{2m}\right)$ is the location vector (see Figure 2 for an illustration). We observe that for $v\in[n]$ the load $\lambda_{v}$ equals the degree $d_{M}\left(v\right)$ . For each graph $H\in\mathcal{G}(n,m)$ we have $\mathbb{P}\left[M=H\right]=2^{m}m!/n^{2m}$ . Hence, conditioned on the event that $M$ is simple, $M$ is distributed like $G$ . Moreover, for $n$ large enough we have

	$\displaystyle\mathbb{P}\left[M\text{ is simple}\right]$	$\displaystyle\hskip 1.70709pt=\hskip 1.70709pt\mathbb{P}\left[M\text{ has no loops}\right]\cdot\mathbb{P}\left[M\text{ has no multiple edges}\;\middle\|\;M\text{ has no loops}\right]$
		$\displaystyle\hskip 1.70709pt=\hskip 1.70709pt\left(1-\frac{1}{n}\right)^{m}\hskip 1.42271pt\cdot\hskip 1.42271pt\prod_{i=0}^{m-1}\left(1-\frac{i}{\binom{n}{2}}\right)\hskip 1.70709pt\geq\hskip 1.70709pt\exp\left(\frac{-2m}{n}-\frac{4m^{2}}{n^{2}}\right)\hskip 1.70709pt>\hskip 1.70709pt\rho,$

for a suitable chosen $\rho>0$ , since $m=O\left(n\right)$ . This shows $\liminf_{n\to\infty}\mathbb{P}\left[M\text{ is simple}\right]>0$ . Thus, each property that holds whp in $M$ , is also true whp in $G$ . In particular, the degree sequence $\mathbf{d}$ of $G$ is contiguous with respect to the degree sequence $\mathbf{\lambda}$ of $M$ , i.e. $\mathbf{d}\triangleleft\mathbf{\lambda}$ . Together with Theorem 4.1 this yields whp $\left\lfloor\nu\left(n,2m\right)-\varepsilon\right\rfloor\hskip 1.70709pt\leq\hskip 1.70709pt\Delta\left(G\right)\hskip 1.70709pt\leq\hskip 1.70709pt\left\lfloor\nu\left(n,2m\right)+\varepsilon\right\rfloor$ , as desired. ∎

We recall that we denote by $U(n,m)$ a graph chosen uniformly at random from the class $\mathcal{U}(n,m)$ consisting of graphs having no complex components, vertex set $[n]$ , and $m$ edges. Later $U(n,m)$ will take the role of the non-complex part of the random planar graph. In this case the relation $m=n/2+O\left(n^{2/3}\right)$ is satisfied (see Theorem 2.10). Britikov [6] provided a useful relation between $U(n,m)$ and $G(n,m)$ in this range.

Theorem 5.2 ([6]).

Let $m=m(n)\leq n/2+O\left(n^{2/3}\right)$ and $G=G(n,m)\in_{R}\mathcal{G}(n,m)$ . Then

\displaystyle\liminf_{n\to\infty}\leavevmode\nobreak\ \mathbb{P}\left[G\text{ has no complex components }\right]>0.

In particular, $\liminf_{n\to\infty}\leavevmode\nobreak\ \mathbb{P}\left[G\text{ is planar }\right]>0$ .

Combining Theorems 5.1 (b) and 5.2 we can deduce that whp $\Delta\left(U(n,m)\right)$ is concentrated at two values.

Lemma 5.3.

Let $m=m(n)=n/2+O\left(n^{2/3}\right)$ , $U=U(n,m)\in_{R}\mathcal{U}(n,m)$ be a random graph without complex components, and $\varepsilon>0$ . Then whp $\left\lfloor\nu\left(n\right)-\varepsilon\right\rfloor\hskip 1.70709pt\leq\hskip 1.70709pt\Delta\left(U\right)\hskip 1.70709pt\leq\hskip 1.70709pt\left\lfloor\nu\left(n\right)+\varepsilon\right\rfloor$ .

Proof.

Combining Theorems 5.1 (b) and 5.2 yields whp

\displaystyle\left\lfloor\nu\left(n,2m\right)-\varepsilon/2\right\rfloor\hskip 1.70709pt\leq\hskip 1.70709pt\Delta\left(U\right)\hskip 1.70709pt\leq\hskip 1.70709pt\left\lfloor\nu\left(n,2m\right)+\varepsilon/2\right\rfloor.

(11)

Using Lemma 2.11 (f) we obtain $\nu\left(n,2m\right)=\nu\left(n\right)+o\left(1\right)$ . Together with (11) this shows the statement. ∎

6. Random complex part and forests with specified roots

The goal of this section is to prove that whp the maximum degree of a random complex part is concentrated at two values (see Theorem 6.4 (b)). As a random complex part can be constructed by using a random forest, we start by analysing the class $\mathcal{F}(n,t)$ of forests on vertex set $[n]$ having $t$ tree components (some of which might just be isolated vertices) such that the vertices $1,\ldots,t$ lie all in different tree components.

In Section 6.1 we generalise the concept of Prüfer sequences to forests. Then we determine the maximum degree in a random forest in Section 6.2. Finally, we derive the concentration result on the maximum degree in a random complex part in Section 6.3.

6.1. Prüfer sequences for forests with specified roots

Similar to Prüfer sequences for trees (see e.g. [50, 36]), there is a bijection between $\mathcal{F}(n,t)$ and $\mathcal{S}\left(n,t\right):=[n]^{n-t-1}\times[t]$ (see e.g. [49, Section 6.6]): Given a forest $F\in\mathcal{F}(n,t)$ we construct a sequence $\left(F_{0},\ldots,F_{n-t}\right)$ of forests and two sequences $\left(x_{1},\ldots,x_{n-t}\right)$ and $\left(y_{1},\ldots,y_{n-t}\right)$ of vertices as follows. We start with $F_{0}:=F$ . Given $F_{i-1}$ for an $i\in[n-t]$ , we let $y_{i}$ be the leaf with largest label in $F_{i-1}$ and $x_{i}$ be the unique neighbour of $y_{i}$ . Furthermore, we obtain $F_{i}$ by deleting the edge $x_{i}y_{i}$ in $F_{i-1}$ . We note that this construction is always possible, since $F_{i-1}$ has $n-t-i+1$ edges and therefore at least one leaf. We call

\displaystyle\psi(F):=\left(x_{1},\ldots,x_{n-t}\right)

(12)

the Prüfer sequence of $F$ . We denote by $\#\left(v,\mathbf{w}\right):=\left|\left\{i\in[n-t]\mid w_{i}=v\right\}\right|$ the number of occurrences of an element $v\in[n]$ in $\mathbf{w}=\left(w_{1},\ldots,w_{n-t}\right)\in[n]^{n-t}$ .

Theorem 6.1.

Let $n,t\in\mathbb{N}$ and $\mathcal{F}(n,t)$ be the class of forests on vertex set $[n]$ consisting of $t$ tree components such that the vertices $1,\ldots,t$ lie all in different tree components. In addition, let $\mathcal{S}\left(n,t\right)=[n]^{n-t-1}\times[t]$ and $\psi(F)$ be the Prüfer sequence of $F\in\mathcal{F}(n,t)$ as defined in (12). Then $\psi:\mathcal{F}(n,t)\to\mathcal{S}\left(n,t\right)$ is a bijection. For $F\in\mathcal{F}(n,t)$ and $v\in[n]$ we have

\displaystyle d_{F}\left(v\right)\hskip 1.70709pt=\hskip 1.70709pt\begin{cases}\#\left(v,\psi(F)\right)&\text{\leavevmode\nobreak\ \leavevmode\nobreak\ if\leavevmode\nobreak\ \leavevmode\nobreak\ }v\in[t]\\ \#\left(v,\psi(F)\right)+1&\text{\leavevmode\nobreak\ \leavevmode\nobreak\ if\leavevmode\nobreak\ \leavevmode\nobreak\ }v\in[n]\setminus[t].\end{cases}

(13)

Theorem 6.1 can be shown by using similar ideas as in the classical case of trees. For the sake of completeness, we provide a proof of Theorem 6.1 in Appendix B.

6.2. Degree sequence and maximum degree of a random forest

We consider a random forest $F=F(n,t)\in_{R}\mathcal{F}(n,t)$ and determine the degree sequence of $F$ and the maximum degree $\Delta\left(F\right)$ .

Theorem 6.2.

Let $n,t\in\mathbb{N}$ and $\mathbf{d}=\left(d_{F}\left(1\right),\ldots,d_{F}\left(n\right)\right)$ be the degree sequence of $F=F\left(n,t\right)\in_{R}\mathcal{F}\left(n,t\right)$ . Let $\mathbf{A}\sim\operatorname{BB}\left(n,n-t-1\right)$ and $\lambda_{j}=\lambda_{j}(\mathbf{A})$ be the load in bin $\mathcal{B}_{j}$ for each $j\in[n]$ . In addition, let $Z\in_{R}[t]$ (independent of $F$ ) and for $j\in[t]$ we define $Y_{j}=1$ if $Z=j$ and $Y_{j}=0$ otherwise. Then

\displaystyle\big{(}\lambda_{1}+Y_{1},\ldots,\lambda_{t}+Y_{t},\lambda_{t+1}+1,\ldots,\lambda_{n}+1\big{)}\sim\mathbf{d}.

Proof.

Instead of directly choosing $F$ from $\mathcal{F}(n,t)$ , we can equivalently create $F$ by Prüfer sequences from Section 6.1: First we perform a balls-into-bins experiment with $n$ bins and $n-t-1$ balls and let $\mathbf{A}=\left(A_{1},\ldots,A_{n-t-1}\right)\sim\operatorname{BB}\left(n,n-t-1\right)$ be the location vector. Then we independently choose $A_{n-t}\in_{R}[t]$ and set $F=\psi^{-1}\left(A_{1},\ldots,A_{n-t}\right)$ and the statement follows by (13). ∎

Using this connection to the balls-into-bins model we obtain an upper bound on $\Delta\left(F(n,t)\right)$ (see Theorem 6.3 (a)). If we assume that $t$ is not too ‘large’, we can even show that whp $\Delta\left(F(n,t)\right)$ is concentrated at two values and that the maximum degree of a root vertex, i.e. a vertex in $[t]$ , is much smaller than $\Delta\left(F(n,t)\right)$ (see Theorem 6.3 (b)). We will need these facts later when we use random forests to build a random complex part (see Section 6.3).

Theorem 6.3.

Let $t=t(n)$ , $F=F\left(n,t\right)\in_{R}\mathcal{F}\left(n,t\right)$ , and $\varepsilon>0$ . Then

(a)

whp $\Delta\left(F\right)\hskip 1.70709pt\leq\hskip 1.70709pt\left\lfloor\nu\left(n\right)\right\rfloor+2$ ;
(b)

if $t=O\left(n^{1-\beta}\right)$ for some $\beta>0$ , then whp $\left\lfloor\nu\left(n\right)-\varepsilon\right\rfloor+1\hskip 1.70709pt\leq\hskip 1.70709pt\Delta\left(F\right)\hskip 1.70709pt\leq\hskip 1.70709pt\left\lfloor\nu\left(n\right)+\varepsilon\right\rfloor+1$ and $\Delta\left(F\right)-\max\left\{d_{F}(r)\mid r\in[t]\right\}=\omega\left(1\right)$ .

Proof.

Let $\mathbf{A}\sim\operatorname{BB}\left(n,n-t-1\right)$ , $\lambda^{\ast}=\lambda^{\ast}(\mathbf{A})\sim\operatorname{M}\left(n,n-t-1\right)$ be the maximum load of $\mathbf{A}$ , and $\lambda^{\ast}_{t}=\lambda^{\ast}_{t}(\mathbf{A})$ be the maximum load of one of the first $t$ bins of $\mathbf{A}$ . Due to Theorem 4.1 we have whp $\lambda^{\ast}\leq\left\lfloor\nu\left(n,n-t-1\right)\right\rfloor+1\leq\left\lfloor\nu\left(n\right)\right\rfloor+1$ , where we used in the last inequality Lemma 2.11 (d). Combining it with Theorem 6.2 we have

\displaystyle\mathbb{P}\big{[}\Delta\left(F\right)>\left\lfloor\nu\left(n\right)\right\rfloor+2\big{]}\hskip 1.70709pt\leq\hskip 1.70709pt\mathbb{P}\left[\lambda^{\ast}>\left\lfloor\nu\left(n\right)\right\rfloor+1\right]=o\left(1\right).

This shows statement (a).

By Lemma 4.2 we have whp $\lambda^{\ast}-\lambda^{\ast}_{t}=\omega\left(1\right)$ . This together with Theorem 6.2 implies whp $\Delta\left(F\right)-\max\left\{d_{F}(r)\mid r\in[t]\right\}=\omega\left(1\right)$ and $\Delta\left(F\right)\triangleleft\lambda^{\ast}+1$ . Thus, we obtain by Theorem 4.1 that whp

\displaystyle\left\lfloor\nu\left(n,n-t-1\right)-\varepsilon/2\right\rfloor+1\hskip 1.70709pt\leq\hskip 1.70709pt\Delta\left(F\right)\hskip 1.70709pt\leq\hskip 1.70709pt\left\lfloor\nu\left(n,n-t-1\right)+\varepsilon/2\right\rfloor+1.

By Lemma 2.11 (f) we have $\nu\left(n,n-t-1\right)=\nu\left(n\right)+o\left(1\right)$ , which proves statement (b). ∎

We note that the special case of random trees, i.e. when $t=1$ , was studied in [42, 7]. In particular, Carr, Goh, and Schmutz [7] used the saddle-point method to show that whp the maximum degree in random trees is concentrated at two values.

6.3. Random complex part

We consider the class $\mathcal{Q}\left(C,q\right)$ consisting of complex graphs with core $C$ and vertex set $[q]$ , where $C$ is a given core and $q\in\mathbb{N}$ (cf. Definition 2.5). As illustrated in Figure 3, we can construct $Q\left(C,q\right)\in_{R}\mathcal{Q}\left(C,q\right)$ via the balls-into-bins model. Assuming that $\Delta\left(C\right)$ is bounded and $v\left({C}\right)$ is ‘small’ compared to $q$ , we will use Theorem 6.3 to show that the maximum degree of $Q\left(C,q\right)$ is strongly concentrated.

Figure 3. Construction of the random complex part

Q(C,q)

: (a) Given a core

C

and

q\in\mathbb{N}

, (b) a balls-into-bins experiment is translated (deterministically) to (c) a Prüfer sequence, (d) a random forest, and finally to (e) the random complex part

Q(C,q)

Theorem 6.4.

For each $n\in\mathbb{N}$ , let $C=C(n)$ be a core and $q=q(n)\in\mathbb{N}$ . In addition, let $Q=Q\left(C,q\right)\in_{R}\mathcal{Q}\left(C,q\right)$ be a random complex part with core $C$ and vertex set $[q]$ as in Definition 2.5 and $\varepsilon>0$ . If $\Delta\left(C\right)=\Theta\left(1\right)$ , then the following hold.

(a)

Whp $\Delta\left(Q\right)\hskip 1.70709pt\leq\hskip 1.70709pt\nu\left(q\right)+O\left(1\right)$ .
(b)

If in addition $v\left({C}\right)=O\left(q^{1-\beta}\right)$ for some $\beta>0$ , then whp $\left\lfloor\nu\left(q\right)-\varepsilon\right\rfloor+1\hskip 1.70709pt\leq\hskip 1.70709pt\Delta\left(Q\right)\hskip 1.70709pt\leq\hskip 1.70709pt\left\lfloor\nu\left(q\right)+\varepsilon\right\rfloor+1$ .

Proof.

We observe that $Q$ can be obtained by choosing a random forest $F=F(q,v\left({C}\right))\in_{R}\mathcal{F}(q,v\left({C}\right))$ and then replacing each vertex $r$ in $C$ by the tree component of $F$ with root $r$ . For a vertex $v\in V\left(Q\right)$ we have

\displaystyle d_{Q}\left(v\right)=\begin{cases}d_{C}\left(v\right)+d_{F}\left(v\right)&\text{if}\leavevmode\nobreak\ \leavevmode\nobreak\ v\in V\left(C\right)\\ d_{F}\left(v\right)&\text{ otherwise}.\end{cases}

(14)

Hence, we have $\Delta\left(Q\right)\hskip 1.70709pt\leq\hskip 1.70709pt\Delta\left(C\right)+\Delta\left(F\right)$ . By Theorem 6.3 (a) we get whp $\Delta\left(F\right)\hskip 1.70709pt\leq\hskip 1.70709pt\nu\left(q\right)+2$ . Together with the fact $\Delta\left(C\right)=\Theta\left(1\right)$ this yields statement (a). For (b) we apply Theorem 6.3 (b) to $F$ . Together with (14) and $\Delta\left(C\right)=\Theta\left(1\right)$ this implies whp $\Delta\left(Q\right)=\Delta\left(F\right)$ . Thus, statement (b) follows by applying again Theorem 6.3 (b). ∎

7. Proofs of Theorems 1.4 and 1.6 and Corollaries 1.7 and 1.8

Throughout this section, let $P=P(n,m)\in_{R}\mathcal{P}(n,m)$ be the random planar graph.

7.1. Proof of Theorem 1.4

In Theorem 5.2 we have seen that $\liminf_{n\to\infty}\mathbb{P}\left[G(n,m)\text{ is planar}\right]>0$ . Thus, each graph property that holds whp in $G(n,m)$ is also true whp in $P$ and the first statement follows by Theorem 5.1 (b). By taking $\varepsilon=1/3$ we get the ‘in particular’ statement. ∎

7.2. Proof of Theorem 1.6

We split $P$ into the large complex part $Q_{L}=Q_{L}\left(P\right)$ , the small complex part $Q_{S}=Q_{S}\left(P\right)$ , and the non-complex part $U=U\left(P\right)$ as described in Section 2.3. We claim that whp the following hold.

(i)

$\left\lfloor\nu\left(\ell\right)-\varepsilon\right\rfloor+1\hskip 1.70709pt\leq\hskip 1.70709pt\Delta\left(Q_{L}\right)\hskip 1.70709pt\leq\hskip 1.70709pt\left\lfloor\nu\left(\ell\right)+\varepsilon\right\rfloor+1$ ;
(ii)

$\Delta\left(Q_{S}\right)\hskip 1.70709pt\leq\hskip 1.70709pt\nu\left(r^{2/3}\right)+O\left(1\right)$ ;
(iii)

$\left\lfloor\nu\left(r\right)-\varepsilon\right\rfloor\hskip 1.70709pt\leq\hskip 1.70709pt\Delta\left(U\right)\hskip 1.70709pt\leq\hskip 1.70709pt\left\lfloor\nu\left(r\right)+\varepsilon\right\rfloor$ .

Assuming these three claims are true we can finish the proof as follows. By Theorem 2.10 (c) we have whp $L=Q_{L}$ and therefore also whp $R=Q_{S}\cup U$ . Thus, statement (a) of Theorem 1.6 follows by (i). By Lemma 2.11 (c) we have $\nu\left(r^{2/3}\right)=\left(2/3+o\left(1\right)\right)\log r/\log\log r$ and $\nu\left(r\right)=\left(1+o\left(1\right)\right)\log r/\log\log r$ . Combining that with (ii) and (iii) yields whp $\Delta\left(Q_{S}\cup U\right)=\Delta\left(U\right)$ and therefore also whp $\Delta\left(R\right)=\Delta\left(U\right)$ . Hence, statement (b) of Theorem 1.6 follows by (iii). Finally, we obtain the ‘in particular’ statement by taking $\varepsilon=1/3$ .

To prove the claims (i)–(iii), we will follow the strategy described in Section 3: We will construct a conditional random graph $A\mid\mathbf{a}$ which is distributed like the random graph $\tilde{P}$ introduced in Section 3.1. Then we will determine the maximum degrees of the large complex part, small complex part and non-complex part of $A\mid\mathbf{a}$ (or equivalently of $\tilde{P}$ ). Finally, we will apply Lemma 2.9 to translate these results to the random planar graph $P$ .

Let $\beta:=\min\left\{\delta/2,1/5\right\}$ and $\mathcal{A}(n)$ be the subclass of $\mathcal{P}(n,m)$ consisting of those graphs $H$ satisfying

$\displaystyle\Delta\big{(}C\left(H\right)\big{)}$	$\displaystyle\hskip 1.70709pt=\hskip 1.70709pt\Theta\left(1\right),$	(15)
$\displaystyle v\big{(}{L\left(C\left(H\right)\right)}\big{)}$	$\displaystyle\hskip 1.70709pt=\hskip 1.70709ptO\left(\ell^{1-\beta}\right),$	(16)
$\displaystyle v\big{(}{Q_{L}\left(H\right)}\big{)}$	$\displaystyle\hskip 1.70709pt=\hskip 1.70709pt\Theta\left(\ell\right),$	(17)
$\displaystyle v\big{(}{Q_{S}\left(H\right)}\big{)}$	$\displaystyle\hskip 1.70709pt=\hskip 1.70709ptO\left(r^{2/3}\right),$	(18)
$\displaystyle v\big{(}{U\left(H\right)}\big{)}$	$\displaystyle\hskip 1.70709pt=\hskip 1.70709pt\Theta\left(r\right),$	(19)
$\displaystyle e\big{(}{U\left(H\right)}\big{)}$	$\displaystyle\hskip 1.70709pt=\hskip 1.70709ptv\big{(}{U\left(H\right)}\big{)}/2+O\left(v\big{(}{U\left(H\right)}\big{)}^{2/3}\right).$	(20)

Due to Theorem 2.10 we can choose the implicit hidden constants in the equations (15)–(20) such that $P\in\mathcal{A}(n)$ with a probability of at least $1-\gamma/2$ , for arbitrary $\gamma>0$ . We will apply Lemma 2.9 to the class $\mathcal{A}:=\bigcup_{n\in\mathbb{N}}\mathcal{A}(n)$ . To that end, we define the function $\Phi$ such that for $H\in\mathcal{A}$ we have

\displaystyle\Phi(H):=\big{(}C\left(H\right),v\left({Q_{L}\left(H\right)}\right),v\left({Q_{S}\left(H\right)}\right)\big{)}.

Let $\mathbf{a}=\left(C_{n},\lambda_{n},\sigma_{n}\right)_{n\in\mathbb{N}}$ be a sequence that is feasible for $(\mathcal{A},\Phi)$ and let $A=A(n)\in_{R}\mathcal{A}(n)$ . By definition the possible realisations of $A\mid\mathbf{a}$ are those graphs $H\in\mathcal{A}$ with $C\left(H\right)=C_{n}$ , $v\left({Q_{L}\left(H\right)}\right)=\lambda_{n}$ , and $v\left({Q_{S}\left(H\right)}\right)=\sigma_{n}$ . Hence, $A\mid\mathbf{a}=Q_{L}\left(A\mid\mathbf{a}\right)\leavevmode\nobreak\ \dot{\cup}\leavevmode\nobreak\ Q_{S}\left(A\mid\mathbf{a}\right)\leavevmode\nobreak\ \dot{\cup}\leavevmode\nobreak\ U\left(A\mid\mathbf{a}\right)$ can be constructed as follows. For $Q_{L}\left(A\mid\mathbf{a}\right)$ we choose uniformly at random a complex graph with $\lambda_{n}$ vertices and core $L\left(C_{n}\right)$ and for $Q_{S}\left(A\mid\mathbf{a}\right)$ a complex graph with $\sigma_{n}$ vertices and core $R\left(C_{n}\right)$ . For $U\left(A\mid\mathbf{a}\right)$ we choose a graph without complex components having $u_{n}:=n-\lambda_{n}-\sigma_{n}$ vertices and $w_{n}:=m-e\left({C_{n}}\right)+v\left({C_{n}}\right)-\lambda_{n}-\sigma_{n}$ edges. Summing up, we have

$\displaystyle Q_{L}\big{(}A\mid\mathbf{a}\big{)}$	$\displaystyle\sim Q\big{(}L\left(C_{n}\right),\lambda_{n}\big{)};$	(21)
$\displaystyle Q_{S}\big{(}A\mid\mathbf{a}\big{)}$	$\displaystyle\sim Q\big{(}R\left(C_{n}\right),\sigma_{n}\big{)};$	(22)
$\displaystyle U\big{(}A\mid\mathbf{a}\big{)}$	$\displaystyle\sim U\big{(}u_{n},w_{n}\big{)},$	(23)

where the random complex parts and the random graph without complex components on the right hand side are as defined in Definitions 2.5 and 2.6, respectively. Due to (15) and (16) we have $\Delta\left(C_{n}\right)=\Theta\left(1\right)$ and $v\big{(}{L\left(C_{n}\right)}\big{)}=O\left(\lambda_{n}^{1-\beta}\right)$ . Hence, we can apply Theorem 6.4 (b) to $Q\big{(}L\left(C_{n}\right),\lambda_{n}\big{)}$ . Together with (21) this implies whp

\displaystyle\left\lfloor\nu\left(\lambda_{n}\right)-\varepsilon/2\right\rfloor+1\hskip 1.70709pt\leq\hskip 1.70709pt\Delta\big{(}Q_{L}\left(A\mid\mathbf{a}\right)\big{)}\hskip 1.70709pt\leq\hskip 1.70709pt\left\lfloor\nu\left(\lambda_{n}\right)+\varepsilon/2\right\rfloor+1.

(24)

Using Lemma 2.11 (h) we have $\nu\left(\lambda_{n}\right)=\nu\left(\ell\right)+o\left(1\right)$ , as $\lambda_{n}=\Theta\left(\ell\right)$ by (17). Together with (24) this shows whp

\displaystyle\left\lfloor\nu\left(\ell\right)-\varepsilon\right\rfloor+1\hskip 1.70709pt\leq\hskip 1.70709pt\Delta\big{(}Q_{L}\left(A\mid\mathbf{a}\right)\big{)}\hskip 1.70709pt\leq\hskip 1.70709pt\left\lfloor\nu\left(\ell\right)+\varepsilon\right\rfloor+1.

(25)

By Lemma 2.9 inequality (25) is also whp true if we replace $A\mid\mathbf{a}$ by $A$ . Combining it with the fact that $P\in\mathcal{A}$ with probability at least $1-\gamma/2$ we obtain that with probability at least $1-\gamma$

\displaystyle\left\lfloor\nu\left(\ell\right)-\varepsilon\right\rfloor+1\hskip 1.70709pt\leq\hskip 1.70709pt\Delta\left(Q_{L}\right)\hskip 1.70709pt\leq\hskip 1.70709pt\left\lfloor\nu\left(\ell\right)+\varepsilon\right\rfloor+1

for all $n$ large enough. As $\gamma>0$ was arbitrary, this shows claim (i).

Next, we prove claims (ii) and (iii) in a similar fashion. Combining (22) and Theorem 6.4 (a) yields $\Delta\big{(}Q_{S}\left(A\mid\mathbf{a}\right)\big{)}\leq\nu\left(\sigma_{n}\right)+O\left(1\right)$ . Due to Lemma 2.11 (g) and (h) we have $\nu\left(\sigma_{n}\right)\leq\nu\left(r^{2/3}\right)+o(1)$ , where we used $\sigma_{n}=O\left(r^{2/3}\right)$ by (18). This yields $\Delta\big{(}Q_{S}\left(A\mid\mathbf{a}\right)\big{)}\leq\nu\left(r^{2/3}\right)+O\left(1\right)$ . Thus, claim (ii) follows by Lemma 2.9. Due to (20) we have $w_{n}=u_{n}/2+O\left(u_{n}^{2/3}\right)$ . Hence, we can combine (23) and Lemma 5.3 to obtain whp

\displaystyle\left\lfloor\nu\left(u_{n}\right)-\varepsilon/2\right\rfloor\hskip 1.70709pt\leq\hskip 1.70709pt\Delta\big{(}U\left(A\mid\mathbf{a}\right)\big{)}\hskip 1.70709pt\leq\hskip 1.70709pt\left\lfloor\nu\left(u_{n}\right)+\varepsilon/2\right\rfloor.

(26)

Due to (19) we have $u_{n}=\Theta\left(r\right)$ and therefore, we obtain $\nu\left(u_{n}\right)=\nu\left(r\right)+o\left(1\right)$ by Lemma 2.11 (h). Using that in (26) we get whp

\displaystyle\left\lfloor\nu\left(r\right)-\varepsilon\right\rfloor\hskip 1.70709pt\leq\hskip 1.70709pt\Delta\big{(}U\left(A\mid\mathbf{a}\right)\big{)}\hskip 1.70709pt\leq\hskip 1.70709pt\left\lfloor\nu\left(r\right)+\varepsilon\right\rfloor.

Now claim (iii) follows by Lemma 2.9. ∎

7.3. Proof of Corollary 1.7

We distinguish two cases. If $m$ is as in Theorem 1.4, then whp $\Delta\left(P\right)=\nu\left(n,2m\right)+O\left(1\right)=\left(1+o\left(1\right)\right)\log n/\log\log n$ , where we used Theorem 1.4, Lemma 2.11 (c), and that $m=\Theta\left(n\right)$ . If $m$ is as in Theorem 1.6, then $\max\left\{\ell(n),r(n)\right\}=n$ . Together with Lemma 2.11 (c) and (g) this implies $\max\left\{\nu\left(\ell\right),\nu\left(r\right)\right\}=\nu\left(n\right)=\left(1+o\left(1\right)\right)\log n/\log\log n$ . Combining that with the ‘in particular’ statement of Theorem 1.6 we obtain whp $\Delta\left(P\right)=\left(1+o\left(1\right)\right)\log n/\log\log n$ , as desired. ∎

7.4. Proof of Corollary 1.8

The assertion follows directly from Theorem 1.6 and the fact from Definition 1.5(b) that $\ell=n$ and $r=n$ . ∎

8. Non-concentration of the maximum degree: Proof of Theorem 1.10

We recall that we denote by $\mathcal{P}(n,m)$ the class of all vertex-labelled planar graphs on vertex set $[n]$ with $m$ edges. Furthermore, let $\mathcal{P}_{C}(n,m)\subseteq\mathcal{P}(n,m)$ be the subclass containing all connected planar graphs on vertex set $[n]$ with $m$ edges. Our starting point is the following result of Giménez and Noy [26].

Theorem 8.1 ([26]).

Let $\mu\in(1,3)$ and $m=m(n)=\left\lfloor\mu n\right\rfloor$ . Then there exist constants $\gamma,u>0$ and $c\geq c_{1}>0$ such that

	$\displaystyle\left\|\mathcal{P}(n,m)\right\|$	$\displaystyle=\left(1+o\left(1\right)\right)cn^{-4}\gamma^{n}u^{m}n!;$
	$\displaystyle\left\|\mathcal{P}_{C}(n,m)\right\|$	$\displaystyle=\left(1+o\left(1\right)\right)c_{1}n^{-4}\gamma^{n}u^{m}n!.$

Using Theorem 8.1 we can show that the probability that the dense random planar graph $P(n,m)$ has $k$ isolated vertices and $l$ isolated edges is bounded away from 0, for each fixed $k,l\in\mathbb{N}_{0}:=\mathbb{N}\cup\left\{0\right\}$ .

Lemma 8.2.

Let $P=P(n,m)\in_{R}\mathcal{P}(n,m)$ and assume $m=m(n)=\left\lfloor\mu n\right\rfloor$ for $\mu\in(1,3)$ . Then we have for all fixed $k,l\in\mathbb{N}_{0}$

\displaystyle\liminf_{n\to\infty}\leavevmode\nobreak\ \mathbb{P}\left[P\text{ has }k\text{ isolated vertices and }l\text{ isolated edges}\right]>0.

Proof.

Throughout the proof, let $n$ be sufficiently large. Let $H$ be a fixed planar graph having $k$ isolated vertices and $l$ isolated edges and satisfying $e\left({H}\right)=\left\lfloor\mu\cdot v\left({H}\right)\right\rfloor$ . Then we can construct ‘many’ graphs in $\mathcal{P}(n,m)$ with $k$ isolated vertices and $l$ isolated edges by adding a copy of $H$ to a connected graph $H^{\prime}\in\mathcal{P}_{C}(n-v\left({H}\right),m-e\left({H}\right))$ . More precisely, we consider the following construction:

•

Choose a subset $L\subseteq[n]$ of size $v\left({H}\right)$ and label the vertices of $H$ with $L$ ;
•

Choose a graph $H^{\prime}\in\mathcal{P}_{C}(n-v\left({H}\right),m-e\left({H}\right))$ , label the vertices with $[n]\setminus L$ , and add the copy of $H$ to $H^{\prime}$ .

As these constructed graphs are all pairwise distinct, we obtain

\displaystyle\mathbb{P}\left[P\text{ has }k\text{ isolated vertices and }l\text{ isolated edges}\right]\geq\frac{\binom{n}{v\left({H}\right)}\left|\mathcal{P}_{C}(n-v\left({H}\right),m-e\left({H}\right))\right|}{\left|\mathcal{P}(n,m)\right|}.

(27)

We note that $\left\lfloor\mu\cdot\left(n-v\left({H}\right)\right)\right\rfloor$ is either $m-e\left({H}\right)$ or $m-e\left({H}\right)-1$ . We assume $\left\lfloor\mu\cdot\left(n-v\left({H}\right)\right)\right\rfloor=m-e\left({H}\right)$ , as the latter case can be done analogously by considering instead of $H$ a graph having $v\left({H}\right)$ vertices, $e\left({H}\right)+1$ edges, $k$ isolated vertices, and $l$ isolated edges. Theorem 8.1 implies

\displaystyle\left|\mathcal{P}_{C}(n-v\left({H}\right),m-e\left({H}\right))\right|=\Theta\left(1\right)\left|\mathcal{P}(n-v\left({H}\right),m-e\left({H}\right))\right|=\Theta\left(1\right)n^{-v\left({H}\right)}\left|\mathcal{P}(n,m)\right|.

(28)

Finally, the statement follows by using (28) and the fact $\binom{n}{v\left({H}\right)}=\Theta\left(1\right)n^{v\left({H}\right)}$ in (27). ∎

We note that the formulas on the number of planar graphs in Theorem 8.1 are not true in the sparse regime where $m\leq n+o\left(n\right)$ . As a consequence, also Lemma 8.2 does not hold in that case.

Next, we will show that we can locally change a graph so that the maximum degree increases by one, the number of isolated vertices by three, and the number of isolated edges decreases by two. Using it we can create graphs with many different maximum degrees. The following definition and lemma make this idea more precise.

Definition 8.3.

For $n,m,d\in\mathbb{N}$ and $k,l\in\mathbb{N}_{0}$ we let $\mathcal{P}(n,m,k,l,d)\subseteq\mathcal{P}(n,m)$ be the subclass of all planar graphs on vertex set $[n]$ having $m$ edges, $k$ isolated vertices, $l$ isolated edges, and maximum degree $d$ .

Lemma 8.4.

Let $n,m,k,l,d\in\mathbb{N}$ with $l\geq 2$ and $d\geq 3$ . Then we have

\displaystyle\frac{\left|\mathcal{P}(n,m,k+3,l-2,d+1)\right|}{\left|\mathcal{P}(n,m,k,l,d)\right|}\geq\frac{1}{8k^{3}}.

Proof.

We consider the following operation that transforms a graph $H\in\mathcal{P}(n,m,k,l,d)$ to a graph $H^{\prime}\in\mathcal{P}(n,m,k+3,l-2,d+1)$ (see also Figure 4). We pick in $H$ a vertex $v_{1}$ of degree $d$ , a neighbour $v_{2}$ of $v_{1}$ , an isolated vertex $v_{3}$ , and isolated edges $v_{4}v_{5}$ , $v_{6}v_{7}$ . Then we obtain $H^{\prime}$ from $H$ by deleting the edges $v_{4}v_{5}$ , $v_{6}v_{7}$ and adding $v_{1}v_{3}$ and $v_{2}v_{3}$ . For two graphs $H\in\mathcal{P}(n,m,k,l,d)$ and $H^{\prime}\in\mathcal{P}(n,m,k+3,l-2,d+1)$ we write $H\rightarrow H^{\prime}$ if $H$ can be transformed to $H^{\prime}$ via the above operation. For a fixed graph $H$ we have

\displaystyle\left|\left\{H^{\prime}\mid H\rightarrow H^{\prime}\right\}\right|\geq dk\binom{l}{2}.

(29)

Next, we note that if we perform our operation $H\rightarrow H^{\prime}$ , then $H^{\prime}$ satisfies the following properties:

•

There are at most two vertices in $H^{\prime}$ with degree $d+1$ ;
•

The vertex $v_{1}$ has degree $d+1$ ;
•

The vertex $v_{3}$ has exactly two neighbours, which are $v_{1}$ and $v_{2}$ ;
•

The vertices $v_{4},v_{5},v_{6}$ and $v_{7}$ are isolated.

Using these observations we can bound for a fixed $H^{\prime}$ the number of graphs $H$ with $H\rightarrow H^{\prime}$ . There are at most two possible vertices in $H^{\prime}$ which can be $v_{1}$ and knowing $v_{1}$ there are at most $d+1$ options for the vertex $v_{3}$ . Given $v_{1}$ and $v_{3}$ the vertex $v_{2}$ is already determined. Finally, for the vertices $v_{4},v_{5},v_{6}$ and $v_{7}$ there are $3\binom{k+3}{4}$ possibilities. Hence, we obtain

\displaystyle\left|\left\{H\mid H\rightarrow H^{\prime}\right\}\right|\leq 2(d+1)3\binom{k+3}{4}.

(30)

Combining (29) and (30) yields

\displaystyle\frac{\left|\mathcal{P}(n,m,k+3,l-2,d+1)\right|}{\left|\mathcal{P}(n,m,k,l,d)\right|}\geq\frac{dk\binom{l}{2}}{2(d+1)3\binom{k+3}{4}}\geq\frac{1}{8k^{3}},

where we used $k/\binom{k+3}{4}\geq 1/k^{3}$ and $d/(d+1)\geq 3/4$ , as $d\geq 3$ . This shows the statement. ∎

Figure 4. The operation used in the proof of Lemma 8.4: A graph

H\in\mathcal{P}(n,m,k,l,d)

is transformed to a graph

H^{\prime}\in\mathcal{P}(n,m,k+3,l-2,d+1)

Finally, we can show Theorem 1.10 by using Lemma 8.2 and applying Lemma 8.4 repeatedly.

8.1. Proof of Theorem 1.10

We assume to the contrary that there is a $A\in\mathbb{N}$ such that $\left|I\right|\leq A$ for infinitely many $n$ . To simplify notation, we even assume that $\left|I\right|\leq A$ is true for all $n\in\mathbb{N}$ . Otherwise, we could restrict our considerations to the subsequence consisting of all $n$ satisfying $\left|I\right|\leq A$ . By Lemma 8.2 there is a $\rho>0$ such that for all $n$ large enough

\displaystyle\sum_{d\in I}\left|\mathcal{P}(n,m,1,2A,d)\right|\geq\rho\left|\mathcal{P}(n,m)\right|.

In particular, we can choose $d=d(n)\in\mathbb{N}$ such that

\displaystyle\left|\mathcal{P}(n,m,1,2A,d)\right|\geq\frac{\rho}{A}\left|\mathcal{P}(n,m)\right|.

Combining that with Lemma 8.4 we get for all $i\leq A$

\displaystyle\left|\mathcal{P}(n,m,1+3i,2A-2i,d+i)\right|\geq\left(\frac{1}{8(3i-2)^{3}}\right)^{i}\left|\mathcal{P}(n,m,1,2A,d)\right|\geq\left(\frac{1}{8(3A)^{3}}\right)^{A}\frac{\rho}{A}\left|\mathcal{P}(n,m)\right|.

This implies that

\displaystyle\mathbb{P}\left[\Delta\left(P\right)=d+i\right]\geq\frac{\left|\mathcal{P}(n,m,1+3i,2A-2i,d+i)\right|}{\left|\mathcal{P}(n,m)\right|}\geq\left(\frac{1}{8(3A)^{3}}\right)^{A}\frac{\rho}{A}.

As $A$ and $\rho$ are fixed constants and whp $\Delta\left(P\right)\in I$ , this shows that for all $n$ large enough we have $d+i\in I$ . Hence, we get $\left\{d,d+1,\ldots,d+A\right\}\subseteq I$ , and therefore $|I|\geq A+1$ , contradicting the fact $\left|I\right|\leq A$ . This finishes the proof. ∎

9. Properties of $\nu\left(n,k\right)$

In this section we consider the function $\nu\left(n,k\right)$ introduced in Definition 1.3. First we will show that $\nu\left(n,k\right)$ is well defined and then we will provide a proof of Lemma 2.11.

9.1. Well-definedness of $\nu\left(n,k\right)$

We recall that for given $n,k\in\mathbb{N}$ we defined the function $f$ as

\displaystyle f(x)=f_{n,k}(x):=x\log k+x-\left(x+1/2\right)\log x-(x-1)\log n.

(31)

By basic calculus we obtain $f(x)>0$ for all $x\in(0,1]$ , $f^{\prime\prime}(x)<0$ for all $x\geq 1$ , and $f(x)\to-\infty$ as $x\to\infty$ . This implies that $f$ has a unique zero in $(0,\infty)$ , which shows that $\nu\left(n,k\right)$ is well defined.

Moreover, we obtain the following fact, which we will use in Section 9.2:

\displaystyle f(x)\begin{cases}>0&\text{if }x<\nu\left(n,k\right),\\ =0&\text{if }x=\nu\left(n,k\right),\\ <0&\text{if }x>\nu\left(n,k\right).\end{cases}

(32)

9.2. Proof of Lemma 2.11

Let $f$ be as defined in (31) and let $\nu\left(n,k\right)$ be the unique positive zero of $f$ . For $x\in(0,1]$ we have $f(x)>0$ , which together with (32) implies (a), i.e. $\nu\left(n,k\right)>1$ .

In order to prove (b), we may assume that $k\leq Cn^{1/3}$ for a suitable constant $C>0$ . Now we get for $n$ large enough

\displaystyle f(5/3)\hskip 1.70709pt\leq\hskip 1.70709pt-1/9\log n+5/3\log C+5/3-13/6\log\left(5/3\right)<0.

Together with (32) this implies $\nu\left(n,k\right)\leq 5/3$ for all $n$ large enough, which yields (b).

For (c) we may assume $k=\Theta\left(n\right)$ . Then we have for $a>0$

\displaystyle f\left(a\frac{\log n}{\log\log n}\right)=\left(1-a+o\left(1\right)\right)\log n.

Thus, (c) follows by (32).

For (d) we fix $n\in\mathbb{N}$ and define $K(x):=\left(1+1/(2x)\right)\log x+\left(1-1/x\right)\log n-1$ . It is easy to check that $K(\nu\left(n,k\right))=\log k$ and $K$ is strictly increasing. This implies (d).

For (e) we observe that by definition of $\nu=\nu\left(n,k\right)$

\displaystyle 1=e\frac{k}{n\nu}\exp\left(\left(\log n-1/2\log\nu\right)/\nu\right).

(33)

Due to (c) and (d) we have $\nu=o\left(\log n\right)$ , which yields $\left(\log n-1/2\log\nu\right)/\nu=\omega\left(1\right)$ . Combining that with (33) shows $\nu=\omega\left(k/n\right)$ .

For (f) we let $\nu=\nu\left(n,k\right)$ and $\rho\in\mathbb{R}$ . Due to (c) we have $\nu=\left(1+o\left(1\right)\right)\log n/\log\log n$ and therefore

\displaystyle K\left(\nu+\rho\right)-K(\nu)=\frac{\left(\log\log n\right)^{2}}{\log n}\left(\rho+o\left(1\right)\right).

(34)

On the other hand, we have

\displaystyle K\big{(}\nu\left(n,k+d\right)\big{)}-K\big{(}\nu\left(n,k\right)\big{)}=\log(k+d)-\log k=\Theta\left(d/k\right)=o\left(\left(\log\log n\right)^{2}/\log n\right).

Together with (34) this implies (f), as $K$ is strictly increasing.

Similarly, we define for (g) the function $g(x):=\left(x+1/2\right)\log x-x$ . Now (g) follows by the facts that $g(\nu\left(n\right))=\log n$ and $g$ is strictly increasing.

For (h), let $C(x)=C_{n,k}(x):=\left(x+1/2\right)\log x+x\left(\log n-\log k-1\right)-\log n$ and $\rho\in\mathbb{R}$ be fixed. Then we have

\displaystyle C(x+\rho)-C(x)=\rho\log(x+\rho)+\left(x+1/2\right)\log\left((x+\rho)/x\right)+\rho\left(\log n-\log k-1\right)=\rho\log(x+\rho)+O\left(1\right).

Moreover, there is a constant $A>0$ independent of $n$ such that $C$ is strictly increasing for $x>A$ . Due to (c) we have $\nu\left(n,k\right)=\omega\left(1\right)$ and $\nu\left(cn,ck\right)=\omega\left(1\right)$ and using the definition of $\nu$ we get $C\left(\nu\left(cn,ck\right)\right)-C\left(\nu\left(n,k\right)\right)=\log c-0=O\left(1\right)$ . This implies $\nu\left(cn,ck\right)=\nu\left(n,k\right)+o\left(1\right)$ .

Finally for (i), let $x=\nu\left(n\right)$ and $y=\nu\left(n,cn\right)$ . Using the definition of $\nu$ we have $0=x-(x+1/2)\log x+\log n=y\log c+y-(y+1/2)\log y+\log n$ . Hence, we obtain

\displaystyle y-x=\frac{y\log c-\left(y+1/2\right)\log\left(y/x\right)}{\log x-1}.

(35)

By (c) we have $x,y=\left(1+o\left(1\right)\right)\log n/\log\log n$ and $y/x=1+o\left(1\right)$ . Together with (35) this yields (i). ∎

10. Discussion

The only properties about the random planar graph $P=P(n,m)$ which we used in the proofs of our main results in the sparse regime (Theorems 1.4 and 1.6 and Corollaries 1.7 and 1.8) are the results on the internal structure in Theorem 2.10. Kang, Moßhammer, and Sprüssel [34] showed that Theorem 2.10 is true for much more general classes of graphs. Prominent examples of such classes are cactus graphs, series-parallel graphs, and graphs embeddable on an orientable surface of genus $g\in\mathbb{N}\cup\{0\}$ (see [33, Section 4]). Using the generalised version of Theorem 2.10 and analogous proofs of Theorems 1.4 and 1.6 and Corollaries 1.7 and 1.8, one can show the following.

Theorem 10.1.

Theorems 1.4 and 1.6 and Corollaries 1.7 and 1.8 are true for the class of cactus graphs, the class of series-parallel graphs, and the class of graphs embeddable on an orientable surface of genus $g\in\mathbb{N}_{0}$ .

Theorem 1.6 does not cover the whole regime $m=n+o\left(n\right)$ and leaves a small gap of order $n^{o\left(1\right)}$ to the dense case where $m=m(n)=\left\lfloor\mu n\right\rfloor$ for $\mu\in(1,3)$ . This leads to the following natural question on the behaviour of $\Delta\left(P\right)$ in the unconsidered region where $m=m(n)=n+t$ for a $t=t(n)>0$ such that $t=n^{1+o\left(1\right)}$ and $t=o\left(n\right)$ .

Question 10.2.

Let $P=P(n,m)\in_{R}\mathcal{P}(n,m)$ and $m=m(n)=n+t$ where $t=t(n)>0$ is such that $t=n^{1+o\left(1\right)}$ and $t=o\left(n\right)$ . Is $\Delta\left(P\right)$ concentrated on a subset of $[n]$ with bounded size?

In Theorem 1.10 we saw that $\Delta\left(P\right)$ is not concentrated on any subset of $[n]$ with bounded size if $m=m(n)=\left\lfloor\mu n\right\rfloor$ for $\mu\in(1,3)$ . This raises the question how large a set $I=I(n)\subseteq[n]$ needs to be such that whp $\Delta\left(P\right)\in I$ can hold. Furthermore, it would be interesting to know the precise asymptotic order of $\Delta\left(P\right)$ in that regime.

Question 10.3.

Let $P=P(n,m)\in_{R}\mathcal{P}(n,m)$ and assume $m=m(n)=\left\lfloor\mu n\right\rfloor$ for $\mu\in(1,3)$ . What is the smallest size of a set $I=I(n)\subseteq[n]$ satisfying whp $\Delta\left(P\right)\in I$ ? Moreover, what is the asymptotic order of $\Delta\left(P\right)$ ?

Acknowledgement

The authors thank the anonymous referees for many helpful remarks to improve the presentation of this paper.

References

[1] N. Alon and J.H. Spencer. The Probabilistic Method. Wiley Series in Discrete Mathematics and Optimization. Wiley, 3rd edition, 2011.
[2] B. Bollobás. The distribution of the maximum degree of a random graph. Discrete Math., 32(2):201–203, 1980.
[3] B. Bollobás. Degree sequences of random graphs. Discrete Math., 33(1):1–19, 1981.
[4] B. Bollobás. Vertices of given degree in a random graph. J. Graph Theory, 6(2):147–155, 1982.
[5] B. Bollobás. Random Graphs. Cambridge University Press, 2nd edition, 2001.
[6] V. E. Britikov. The structure of a random graph near a critical point. Diskret. Mat., 1(3):121–128, 1989.
[7] R. Carr, W. Goh, and E. Schmutz. The maximum degree in a random tree and related problems. Random Structures Algorithms, 5(1):13–24, 1994.
[8] G. Chapuy, É. Fusy, O. Giménez, B. Mohar, and M. Noy. Asymptotic enumeration and limit laws for graphs of fixed genus. J. Combin. Theory Ser. A, 118(3):748–777, 2011.
[9] G. Chapuy, É. Fusy, O. Giménez, and M. Noy. On the diameter of random planar graphs. Combin. Probab. Comput., 24(1):145–178, 2015.
[10] G. Collet, M. Drmota, and L. D. Klausner. Limit laws of planar maps with prescribed vertex degrees. Combin. Probab. Comput., 28(4):519–541, 2019.
[11] C. Dowden, M. Kang, and P. Sprüssel. The evolution of random graphs on surfaces. SIAM J. Discrete Math., 32(1):695–727, 2018.
[12] M. Drmota, O. Giménez, and M. Noy. Degree distribution in random planar graphs. J. Combin. Theory Ser. A, 118(7):2102–2130, 2011.
[13] M. Drmota, O. Giménez, M. Noy, K. Panagiotou, and A. Steger. The maximum degree of random planar graphs. Proc. Lond. Math. Soc. (3), 109(4):892–920, 2014.
[14] M. Drmota, M. Noy, and B. Stufler. Cut Vertices in Random Planar Maps. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020), volume 159 of Leibniz International Proceedings in Informatics (LIPIcs), pages 10:1–10:18, 2020.
[15] M. Drmota and B. Stufler. Pattern occurrences in random planar maps. Statist. Probab. Lett., 158:108666, 2020.
[16] P. Erdős and A. Rényi. On random graphs. I. Publ. Math. Debrecen, 6:290–297, 1959.
[17] P. Erdős and A. Rényi. On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutató Int. Közl., 5:17–61, 1960.
[18] P. Erdős and R. Wilson. On the chromatic index of almost all graphs. J. Combin. Theory Ser. B, 23(2-3):255–257, 1977.
[19] N. Fountoulakis and K. Panagiotou. 3-connected cores in random planar graphs. Combin. Probab. Comput., 20(3):381–412, 2011.
[20] A. Frieze and M. Karoński. Introduction to Random Graphs. Cambridge University Press, 2015.
[21] É. Fusy. Uniform random sampling of planar graphs in linear time. Random Structures Algorithms, 35(4):464–522, 2009.
[22] S. Gerke and C. McDiarmid. On the number of edges in random planar graphs. Combin. Probab. Comput., 13(2):165–183, 2004.
[23] S. Gerke, C. McDiarmid, A. Steger, and A. Weißl. Random planar graphs with $n$ nodes and a fixed number of edges. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 999–1007. ACM, New York, 2005.
[24] S. Gerke, C. McDiarmid, A. Steger, and A. Weißl. Random planar graphs with given average degree. In Combinatorics, complexity, and chance, volume 34 of Oxford Lecture Ser. Math. Appl., pages 83–102. Oxford Univ. Press, Oxford, 2007.
[25] S. Gerke, D. Schlatter, A. Steger, and A. Taraz. The random planar graph process. Random Structures Algorithms, 32(2):236–261, 2008.
[26] O. Giménez and M. Noy. Asymptotic enumeration and limit laws of planar graphs. J. Amer. Math. Soc., 22(2):309–329, 2009.
[27] G. H. Gonnet. Expected length of the longest probe sequence in hash code searching. J. Assoc. Comput. Mach., 28(2):289–304, 1981.
[28] G. I. Ivčenko. The asymptotic behavior of the degrees of vertices in a random graph. Teor. Verojatnost. i Primenen., 18:195–203, 1973.
[29] S. Janson, D. E. Knuth, T. Łuczak, and B. Pittel. The birth of the giant component. Random Structures Algorithms, 4(3):231–358, 1993.
[30] S. Janson, T. Łuczak, and A. Ruciński. Random Graphs. Wiley, 2000.
[31] N. L. Johnson and S. Kotz. Urn models and their application: an approach to modern discrete probability theory. Wiley, 1977.
[32] M. Kang and T. Łuczak. Two critical periods in the evolution of random planar graphs. Trans. Amer. Math. Soc., 364(8):4239–4265, 2012.
[33] M. Kang and M. Missethan. Longest and shortest cycles in random planar graphs. arXiv:2006.09697.
[34] M. Kang, M. Moßhammer, and P. Sprüssel. Phase transitions in graphs on orientable surfaces. Random Structures Algorithms, 56(4):1117–1170, 2020.
[35] T. Łuczak, B. Pittel, and J. C. Wierman. The structure of a random graph at the point of the phase transition. Trans. Amer. Math. Soc., 341(2):721–748, 1994.
[36] J. Matoušek and J. Nešetřil. Invitation to Discrete Mathematics. Oxford University Press, 2nd edition, 2009.
[37] C. McDiarmid. Random graphs on surfaces. J. Combin. Theory Ser. B, 98(4):778–797, 2008.
[38] C. McDiarmid and B. Reed. On the maximum degree of a random planar graph. Combin. Probab. Comput., 17(4):591–601, 2008.
[39] C. McDiarmid, A. Steger, and D. Welsh. Random planar graphs. J. Combin. Theory Ser. B, 93(2):187–205, 2005.
[40] B. McKay and N. Wormald. The degree sequence of a random graph. I. The models. Random Structures Algorithms, 11(2):97–117, 1997.
[41] M. Mitzenmacher and E. Upfal. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis. Cambridge University Press, 2nd edition, 2017.
[42] J. W. Moon. On the maximum degree in a random tree. Michigan Math. J., 15(4):429–432, 1968.
[43] M. Noy, V. Ravelomanana, and J. Rué. On the probability of planarity of a random graph near the critical point. Proc. Amer. Math. Soc., 143(3):925–936, 2015.
[44] M. Noy, C. Requilé, and J. Rué. Further results on random cubic planar graphs. Random Structures Algorithms, 56(3):892–924, 2020.
[45] K. Panagiotou and A. Steger. Maximal biconnected subgraphs of random planar graphs. ACM Trans. Algorithms, 6(2):Art. 31, 21, 2010.
[46] K. Panagiotou and A. Steger. On the degree distribution of random planar graphs. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1198–1210. SIAM, Philadelphia, PA, 2011.
[47] M. Raab and A. Steger. “Balls into bins” – a simple and tight analysis. In Randomization and Approximation Techniques in Computer Science, pages 159–170. Springer Berlin, 1998.
[48] O. Riordan and A. Selby. The maximum degree of a random graph. Combin. Probab. Comput., 9(6):549–572, 2000.
[49] J. Spencer. Asymptopia, volume 71 of Student Mathematical Library. American Mathematical Society, Providence, RI, 2014. With L. Florescu.
[50] J.H. van Lint and R.M. Wilson. A Course in Combinatorics. Cambridge University Press, 2nd edition, 2001.

Appendix A Sketch of the proof of Proposition 1.9

Due to Theorem 5.1 (b) we have whp

\displaystyle\Delta\left(G_{i}\right)=\nu\left(n,d_{i}n\right)+O\left(1\right).

(36)

Together with Lemma 2.11 (i) this shows whp $0<\Delta\left(G_{2}\right)-\Delta\left(G_{1}\right)=\Theta\left(\log n/\left(\log\log n\right)^{2}\right)$ . The so-called symmetry rule (see e.g. [30, Section 5.6]) says that $R(G_{i})$ ‘behaves’ asymptotically like $G\left(n_{i}^{\prime},m_{i}^{\prime}\right)$ for suitable $n_{i}^{\prime}=n_{i}^{\prime}(n)=\Theta\left(n\right)$ and $m_{i}^{\prime}=m_{i}^{\prime}(n)$ such that $2m_{i}^{\prime}/n_{i}^{\prime}$ tends to a constant $c_{i}^{\prime}\in(0,1)$ with $c_{1}^{\prime}>c_{2}^{\prime}$ . Together with Theorem 5.1 (b) this implies that whp

\displaystyle\Delta\left(R\left(G_{i}\right)\right)=\nu\left(n_{i}^{\prime},2m_{i}^{\prime}\right)+O\left(1\right)=\nu\left(n,c_{i}^{\prime}n\right)+o\left(\log n/\left(\log\log n\right)^{2}\right),

(37)

where we used in the last equality Lemma 2.11 (h) and (i). Using (37), Lemma 2.11 (i), and the fact $c_{1}^{\prime}>c_{2}^{\prime}$ , we obtain whp $0<\Delta\left(R\left(G_{1}\right)\right)-\Delta\left(R\left(G_{2}\right)\right)=\Theta\left(\log n/\left(\log\log n\right)^{2}\right)$ . Combining Lemma 2.11 (i), (36), and (37) yields that whp $\Delta\left(L\left(G_{i}\right)\right)=\Delta\left(G_{i}\right)=\nu\left(n,d_{i}n\right)+O\left(1\right)$ . Hence, we get whp $0<\Delta\left(L\left(G_{2}\right)\right)-\Delta\left(L\left(G_{1}\right)\right)=\Theta\left(\log n/\left(\log\log n\right)^{2}\right)$ and $0<\Delta\left(L\left(G_{1}\right)\right)-\Delta\left(R\left(G_{1}\right)\right)=\Theta\left(\log n/\left(\log\log n\right)^{2}\right)$ . ∎

Appendix B Proof of Theorem 6.1

We start by proving (13). To that end, let $r\in[t]$ be a root vertex. Throughout the construction of $\psi(F)$ the root $r$ is always the vertex with smallest label in the component of $F_{i}$ containing $r$ . This implies $r\neq y_{i}$ for all $i\in[n-t]$ . As the elements of the sequence $\mathbf{y}=\left(y_{1},\ldots,y_{n-t}\right)$ are all distinct, we obtain

\displaystyle\#\left(v,\mathbf{y}\right)=\begin{cases}0&\text{\leavevmode\nobreak\ \leavevmode\nobreak\ if\leavevmode\nobreak\ \leavevmode\nobreak\ }v\in[t]\\ 1&\text{\leavevmode\nobreak\ \leavevmode\nobreak\ if\leavevmode\nobreak\ \leavevmode\nobreak\ }v\in[n]\setminus[t].\end{cases}

(38)

This proves (13), since $d_{F}\left(v\right)=\#\left(v,\mathbf{x}\right)+\#\left(v,\mathbf{y}\right)$ .

Next, we provide an algorithm that builds a graph $\psi^{-1}(\mathbf{w})$ for each $\mathbf{w}\in\mathcal{S}\left(n,t\right)$ . Later we will see that the algorithm indeed reconstructs $F\in\mathcal{F}(n,t)$ if the input is $\mathbf{w}=\psi(F)$ . Let $\mathbf{w}=\left(w_{1},\ldots,w_{n-t}\right)\in\mathcal{S}\left(n,t\right)$ be given. We construct sequences $(\tilde{x}_{1},\ldots,\tilde{x}_{n-t})$ and $(\tilde{y}_{1},\ldots,\tilde{y}_{n-t})$ of vertices, a sequence $\left(\tilde{F}_{0},\ldots,\tilde{F}_{n-t}\right)$ of forests and for each $v\in[n]$ a sequence $(\tilde{d}_{0}(v),\ldots,\tilde{d}_{n-t}(v))$ of degrees as follows. We start with $V\left(\tilde{F}_{0}\right)=[n]$ , $E\left(\tilde{F}_{0}\right)=\emptyset$ , $\tilde{d}_{0}(v)=\#\left(v,\mathbf{w}\right)$ if $v\in[t]$ , and $\tilde{d}_{0}(v)=\#\left(v,\mathbf{w}\right)+1$ if $v\in[n]\setminus[t]$ . For $i\in[n-t]$ we set $\tilde{x}_{i}=w_{i}$ and $\tilde{y}_{i}=\max\left\{v\mid\tilde{d}_{i-1}(v)=1\right\}$ . In addition, we let $\tilde{d}_{i}(v)=\tilde{d}_{i-1}(v)-1$ if $v\in\{\tilde{x}_{i},\tilde{y}_{i}\}$ and $\tilde{d}_{i}(v)=\tilde{d}_{i-1}(v)$ otherwise. Finally, we obtain $\tilde{F}_{i}$ by adding the edge $\tilde{x}_{i}\tilde{y}_{i}$ in $\tilde{F}_{i-1}$ and we set $\psi^{-1}(\mathbf{w}):=\tilde{F}_{n-t}$ . Next, we show that this algorithm is well defined and that the output is indeed a graph. To that end, we note that for $v\in[n]\setminus[t]$ and $i\in[n-t]$ we have

\displaystyle\big{(}\tilde{d}_{i-1}(v)\geq 1,\tilde{d}_{i}(v)=0\big{)}\leavevmode\nobreak\ \implies\leavevmode\nobreak\ \big{(}\tilde{y}_{i}=v\big{)}.

This yields that there are at least $(n-t-i)$ vertices $v\in[n]\setminus[t]$ with $\tilde{d}_{i}(v)\geq 1$ . Thus, if $\tilde{d}_{i-1}(w_{n-t})\geq 1$ for some $i\in[n-t]$ , then $\sum_{v\in[n]\setminus[t]}\tilde{d}_{i-1}(v)\leq 2(n-t-i)+1$ and therefore $\tilde{y}_{i}\in[n]\setminus[t]$ . This yields $\tilde{d}_{i}(w_{n-t})\geq 1$ unless $i=n-t$ . As $\tilde{d}_{0}(w_{n-t})\geq 1$ we obtain by induction that $\tilde{y}_{i}\in[n]\setminus[t]$ for all $i\in[n-t]$ . In particular, this shows that $\tilde{y}_{i}$ is well defined and $\tilde{x}_{i}\neq\tilde{y}_{i}$ . Thus, the algorithm is always executable and $\tilde{F}_{i}$ is a graph for all $i\in[n-t]$ .

In order to prove that $\psi:\mathcal{F}(n,t)\to\mathcal{S}\left(n,t\right)$ is a bijection, it suffices to show the following claims.

(i)

$\psi(F)\in\mathcal{S}\left(n,t\right)$ for all $F\in\mathcal{F}(n,t)$ ;
(ii)

$\psi^{-1}(\psi(F))=F$ for all $F\in\mathcal{F}(n,t)$ ;
(iii)

$\psi^{-1}(\mathbf{w})\in\mathcal{F}\left(n,t\right)$ for all $\mathbf{w}\in\mathcal{S}\left(n,t\right)$ ;
(iv)

$\psi\left(\psi^{-1}\left(\mathbf{w}\right)\right)=\mathbf{w}$ for all $\mathbf{w}\in\mathcal{S}\left(n,t\right)$ .

We observe that $x_{n-t}\notin\left\{y_{1},\ldots,y_{n-t}\right\}$ . Thus, using (38) yields $x_{n-t}\in[t]$ , which implies (i).

To show (ii), we suppose that we first apply the algorithm to obtain $\psi(F)$ and then the algorithm $\psi^{-1}$ with input $\mathbf{w}=\psi(F)$ . Due to (13) the degree sequence of $F_{0}=F$ equals $\left(\tilde{d}_{0}(1),\ldots,\tilde{d}_{0}(n)\right)$ and therefore $\tilde{y}_{1}=y_{1}$ . By construction we also have $\tilde{x}_{1}=x_{1}$ , which implies that $\left(\tilde{d}_{1}(1),\ldots,\tilde{d}_{1}(n)\right)$ is the degree sequence of $F_{1}$ . By repeating that argument we obtain by induction $\tilde{y}_{i}=y_{i}$ for all $i\in[n-t]$ . As $E\left(F\right)=\left\{x_{i}y_{i}\mid i\in[n-t]\right\}$ and $E\left(\tilde{F}_{n-t}\right)=\left\{\tilde{x}_{i}\tilde{y}_{i}\mid i\in[n-t]\right\}$ this shows $\tilde{F}_{n-t}=F$ , i.e. $\psi^{-1}(\psi(F))=F$ .

For (iii) we assume that we apply the algorithm $\psi^{-1}$ with input $\mathbf{w}\in\mathcal{S}\left(n,t\right)$ . By induction it follows that for all $i\in\left\{0,\ldots,n-t\right\}$ each component of $\tilde{F}_{i}$ contains at most one vertex $v$ with $\tilde{d}_{i}(v)>0$ . This implies that we never close a cycle when adding the edge $\tilde{x}_{i+1}\tilde{y}_{i+1}$ in $\tilde{F}_{i}$ , which shows that $\psi^{-1}(\mathbf{w})$ is a forest. We saw before that $\tilde{y}_{i}\in[n]\setminus[t]$ for all $i\in[n-t]$ . Thus, if $r\in[t]$ is a root and the component of $\tilde{F}_{i}$ containing $r$ has a vertex $v$ with $\tilde{d}_{i}(v)>0$ , then $v=r$ . This implies that adding the edge $\tilde{x}_{i+1}\tilde{y}_{i+1}$ never connects two components of $\tilde{F}_{i}$ which contain both a root. Hence, $\psi^{-1}(\mathbf{w})\in\mathcal{F}(n,t)$ .

Finally for (iv), we suppose that for given $\mathbf{w}\in\mathcal{S}\left(n,t\right)$ we first apply the algorithm to construct $\psi^{-1}(\mathbf{w})$ and then the algorithm to obtain the Prüfer sequence of $\psi^{-1}(\mathbf{w})$ . We note that the degree sequence of $F_{0}=\psi^{-1}(\mathbf{w})$ equals $\left(\tilde{d}_{0}(1),\ldots,\tilde{d}_{0}(n)\right)$ and therefore $y_{1}=\tilde{y}_{1}$ . By construction $\tilde{x}_{1}$ is the unique neighbour of $\tilde{y}_{1}$ in $F_{0}$ , which implies $x_{1}=\tilde{x}_{1}$ . This yields that the degree sequence of $F_{1}$ is $\left(\tilde{d}_{1}(1),\ldots,\tilde{d}_{1}(n)\right)$ . Repeating that argument we obtain by induction $\tilde{x}_{i}=x_{i}$ for all $i\in[n-t]$ , which proves (iv). ∎

Concentration of maximum degree in random planar graphs

Abstract.

Key words and phrases:

1. Introduction and results

1.1. Motivation

Theorem 1.1 ([4]).

Theorem 1.2 ([4]).

1.2. Main results

Definition 1.3.

Theorem 1.4.

Definition 1.5.

Theorem 1.6.

Corollary 1.7.

Corollary 1.8.

Proposition 1.9.

Theorem 1.10.

1.3. Outline of the paper

2. Preliminaries

2.1. Notations for graphs

Definition 2.1.

Definition 2.2.

2.2. Random variables and asymptotic notation

Definition 2.3.

Definition 2.4.

2.3. Complex part and core

Definition 2.5.

Definition 2.6.

Remark 2.7.

2.4. Conditional random graphs

Definition 2.8.

Lemma 2.9 ([33, Lemma 3.2]).

2.5. Internal structure of a random planar graph

Theorem 2.10 ([32, 34]).

2.6. Properties of ν​(n,k)\nu\left(n,k\right)

Lemma 2.11.

3. Proof strategy

3.1. Decomposition and conditional random graphs

3.2. Random complex part and forests with specified roots

3.3. Erdős-Rényi random graph and the balls-into-bins model

3.4. Double counting

4. Balls into bins

Theorem 4.1.

Proof.

Lemma 4.2.

Proof.

5. Erdős-Rényi random graph and graphs without complex components

Theorem 5.1.

Proof.

Theorem 5.2 ([6]).

Lemma 5.3.

Proof.

6. Random complex part and forests with specified roots

6.1. Prüfer sequences for forests with specified roots

Theorem 6.1.

6.2. Degree sequence and maximum degree of a random forest

Theorem 6.2.

Proof.

Theorem 6.3.

Proof.

6.3. Random complex part

Theorem 6.4.

Proof.

7. Proofs of Theorems 1.4 and 1.6 and Corollaries 1.7 and 1.8

7.1. Proof of Theorem 1.4

7.2. Proof of Theorem 1.6

7.3. Proof of Corollary 1.7

7.4. Proof of Corollary 1.8

8. Non-concentration of the maximum degree: Proof of Theorem 1.10

Theorem 8.1 ([26]).

Lemma 8.2.

Proof.

Definition 8.3.

Lemma 8.4.

Proof.

8.1. Proof of Theorem 1.10

9. Properties of ν​(n,k)\nu\left(n,k\right)

9.1. Well-definedness of ν​(n,k)\nu\left(n,k\right)

9.2. Proof of Lemma 2.11

10. Discussion

Theorem 10.1.

2.6. Properties of $\nu\left(n,k\right)$

9. Properties of $\nu\left(n,k\right)$

9.1. Well-definedness of $\nu\left(n,k\right)$