Phase transitions in graphs on orientable surfaces
Mihyun Kang Michael Moßhammer Philipp Sprüssel




  Let 𝕊_g be the orientable surface of genus g.
  We prove that the component structure of a graph chosen uniformly at random from the class 𝒮_g(n,m) of all graphs on vertex set [n]={1,…,n}
  with m edges embeddable on 𝕊_g features two phase transitions. The first phase 
  transition mirrors the classical phase transition in the Erdős–Rényi random graph G(n,m) chosen 
  uniformly at random from all graphs with vertex set [n] and m edges. It takes place at m=n/2+O(n^2/3),
  when a unique largest component, the so-called giant component, emerges. The second phase transition occurs at
  m = n+O(n^3/5), when the giant component covers almost all vertices of the graph. This kind of phenomenon is 
  strikingly different from G(n,m) and has only been observed for graphs on surfaces.
  Moreover, we derive an asymptotic estimation of the number of graphs in 𝒮_g(n,m) throughout the
  regimes of these two phase transitions.


Dipolar Bose Supersolid Stripes
     R. Bombin, J. Boronat and F. Mazzanti 
    
===========================================







§ INTRODUCTION AND RESULTS





 §.§ Background and motivation


In their series of seminal papers <cit.>,
 and  studied asymptotic stochastic properties of graphs chosen
according to a certain probability distribution—an approach that laid the foundations for the
classical theory of random graphs. The main questions considered by , , and many
others are of the following type. Consider the so-called  random graph G(n,m) chosen
uniformly at random from the class G(n,m) of all graphs on vertex set [n]:={1,…,n}
with m=m(n) edges. What structural properties does G(n,m) have with
high probability (commonly abbreviated as ), that is, with probability tending to one as n
tends to infinity?

One of the most extensively studied properties of random graphs is the component structure.  and
 <cit.> proved that the order (that is, the number of vertices) of the 
components of G(n,m) changes drastically when m is around n/2; this kind of behaviour 
is widely known as a phase transition. The result of  and  states that  a) if 
the average degree t := 2m/n of G(n,m) is smaller than one, then all components have at most
logarithmic order; b) if t=1, the largest component has order n^2/3; c) if t→ c>1, then there 
is a unique component of linear order, while all other components are at most logarithmic. This phenomenon 
became known as the emergence of the giant component and was considered by  and  to 
be `one of the most striking facts concerning random graphs'.

While the result of  and  seems to indicate a `double jump' in the order of the largest 
component from logarithmic to order n^2/3 to linear, Bollobás <cit.> proved that the phase transition is actually `smooth' when
we look more closely at the range of t being around one, that is, when s:=m-n/2 is sublinear. 
Bollobás' result, which was later improved by Łuczak <cit.>, shows that the order of the 
largest component changes gradually, depending on whether s has order at most n^2/3 (known as the critical 
regime) or if s has larger order and s>0 (the supercritical regime) or s<0 (the subcritical
regime). Subsequently, Aldous <cit.> further improved the result for the critical regime
using multiplicative coalescent processes and inhomogeneous Brownian motion.

In the supercritical regime and in the regime t>1, central limit theorems and local limit theorems 
provide stronger concentration results for the order and the size (that is, the number of edges) of the largest component. The methods used for these
results range from counting techniques <cit.> over Fourier analysis <cit.>
to probabilistic methods such as Galton-Watson branching processes <cit.>, two-round
exposure <cit.>, or random walks and martingales <cit.>.

Since the pioneering work of  and , various random graph models have been introduced and studied. 
A particularly interesting model are random planar graphs or, more generally, random graphs that are 
embeddable on a fixed two-dimensional surface. Here, a graph G is called embeddable on a surface
𝕊 if G can be drawn on 𝕊 without crossing edges.

Graphs embeddable on a surface and graphs embedded on a surface—also known as maps—have
been studied extensively since the pioneering work of Tutte (see e.g. <cit.>)
in view of enumeration <cit.>,
random sampling <cit.>, and asymptotic 
properties <cit.>. 
Maps and embeddable graphs have also shown to have important applications in algebra and geometry 
(see e.g. <cit.> for an overview) and statistical physics <cit.>. In some of these applications
(e.g. <cit.>) phase transitions play a crucial role, therefore it is an important
question whether random embeddable graphs undergo similar phase transitions as  random
graphs and if they do, what the critical behaviour close to the point of the phase
transition is.

For the order of the largest component of G(n,m), the critical behaviour is described by the results 
of Bollobás <cit.> and Łuczak <cit.> mentioned above. In order to formally 
state their results, we need to introduce some notation. A connected graph is called tree if it
has no cycles, unicyclic if it contains precisely one cycle, and complex (or multicyclic) otherwise.
Given a graph G, we enumerate its components as _i=_i(G), i=1,2,…, in such a way that
they are ordered from large to small, that is, the orders _1,_2,… of the components satisfy _i≥_j
whenever i<j. We say that _i is the i-th largest component of G.

The results of Bollobás and Łuczak can now be described as follows (for all order 
notation in the following, see <Ref>). If m is smaller than n/2 and satisfies m-n/2=ω(n^2/3),
then  all components of G(n,m) have order o(n^2/3). Once m-n/2 = O(n^2/3), several components of order
Θ_p(n^2/3) appear simultaneously. Finally, if m becomes even larger,
then the largest component _1  has order ω(n^2/3), while every
other component has order o(n^2/3) . If we view this development as a process, this
means that all components of order Θ_p(n^2/3) that appeared when m-n/2 = O(n^2/3)
later merge into a single component that is then the unique component of order ω(n^2/3).
This component is usually referred to as the giant component.


  Let m=1+ n^-1/3n/2, where =(n)=o(n^1/3), and let
  _i=_i(G), i=1,2,…, be the i-th largest component of G=G(n,m).
  
  
  * 
    If →-∞, then for every i∈∖{0}  _i is a tree and has order
    
    2+o1n^2/3/^2log-^3.

  
  * 
    If → c for a constant c∈, then for every i∈∖{0} the order of _i is
    
    Θ_pn^2/3.

    Furthermore, the probability that _i is complex is bounded away both from 0 and 1.
  
  * 
    If →∞, then  the largest component _1 of G is complex and has
    order
    
    (2+o(1)) n^2/3.

    For i≥ 2,  _i is a tree of order o(n^2/3).
  


Returning to embeddable graphs, we call a graph planar if it is embeddable on the sphere and
denote by P(n,m) the graph chosen uniformly at random from the class P(n,m) of all planar graphs with
vertex set [n] and m edges. Kang and Łuczak <cit.> proved that P(n,m)
features a similar phase transition as G(n,m), that is, the giant component emerges at
m = n/2+O(n^2/3).


  Let m=1+ n^-1/3n/2, where =(n)=o(n^1/3), and let
  _i=_i(G), i=1,2,…, be the i-th largest component of G=P(n,m). For every i∈∖{0}
  
    _i =
        2+o1n^2/3/^2log-^3   if →-∞,
    Θn^2/3   if → c∈,
    
          (1+o(1)) n^2/3   if →∞ and i=1,
    Θ(n^2/3)    if →∞ and i≥ 2.



The main difference to the  random graph lies in the case →∞. In this regime,
the largest component of P(n,m) is roughly half as large as the largest component of G(n,m).
On the other hand, the order of the second largest component (or more generally, of the i-th
largest component for every fixed i≥2) is much larger in P(n,m) than in G(n,m).

This behaviour, however, is not the most surprising feature of random planar graphs. Indeed, Kang
and Łuczak <cit.> discovered that there is a second phase transition at
m = n+O(n^3/5), which is when the giant component covers almost all vertices. Such a behaviour
is not observed for  random graphs, where the number of vertices outside the giant component is
linear in n as long as m is linear.


  Let m=2+ n^-2/5n/2, where =(n)=o(n^2/5).
  Then  the largest component _1 of P(n,m) is complex and
  
    n-_1 =
        Θn^3/5   if →-∞,
    Θn^3/5   if → c∈,
    Θ^-3/2n^3/5   if →∞ and =o(n^1/15).



Given that this second phase transition has only been observed for random planar graphs, the
fundamental question that is raised by <Ref> is whether this is an intrinsic
phenomenon of planar graphs.


  Which other classes of graphs feature a phase transition analogous to <Ref>?


Canonical candidates for classes that lie `between' P(n,m) and G(n,m) are
graphs that are embeddable on a surface of fixed positive genus. In this paper, we consider graphs embeddable on the orientable 
surface  with genus g∈. Let _g(n,m) be the class of graphs 
with vertex set [n] and m edges that are embeddable on . (Of course, _0(n,m)=P(n,m).) 
One of the main results of this paper is that for every fixed g,
the answer to <Ref> is positive for the class _g(n,m).

For m=⌊μ n⌋ with μ∈(1,3),  and Noy <cit.>
showed, among several other results, that  P(n,m) has a component that covers all but
finitely many vertices. Observe that <Ref> leaves a gap of order Θ(n^1/3) 
to the `dense' regime considered by  and Noy. Subsequently, Chapuy, Fusy, , Mohar, and
Noy <cit.> proved analogous results in the dense regime for _g(n,m).



 §.§ Main results


This paper is the first to determine the component structure of _g(n,m)
for arbitrary g≥0 in the `sparse' regime m≤(1+o(1))n. In terms of phase transitions,
the component structure of _g(n,m) features particularly interesting phenomena in 
this regime, similar to P(n,m). To derive these phenomena, we use a wide range of complementary 
methods from various fields (see <Ref> for more details). 

With this paper, we strive to provide a deeper
understanding of the evolution of graphs embeddable on  for fixed g. Moreover, we pave
a way to better understand embeddability of random graphs, in particular a) the `typical' genus
of G(n,m) when m=m(n) is given and b) the evolution of graphs on a surface of non-constant 
genus g=g(n).

The main contributions of this paper are fourfold. We determine the order and structure of the
largest components of a graph _g(n,m) chosen uniformly at random from
_g(n,m), where the number m of edges is a) around n/2, b) around n,
or c) in between the previous two regimes. Moreover, we determine d) the asymptotic number of graphs 
in _g(n,m) for all the aforementioned regimes.

Our first main result describes the appearance of the unique giant component in _g(n,m). Similar
to various random graph models including  random graphs and random planar graphs (see
<Ref>), the critical range for the number of edges for the appearance of
the giant component is m=n/2+O(n^2/3). Below this range, the i-th largest component (for each i≥1) of
_g(n,m)  is a tree of order o(n^2/3). In the critical range, several components
of order Θ_p(n^2/3) appear simultaneously. After the critical range, _g(n,m)
 has a unique component of order ω(n^2/3) which in addition is complex and has genus g,
that is, it is embeddable on , but not on g-1.


  Let m=1+ n^-1/3n/2, where =(n)=o(n^1/3), and denote by
  _i=_i(G), i=1,2,…, the i-th largest component of G=_g(n,m). For every i∈∖{0}
   the following holds.
  
  
  * 
    If →-∞, then _i is a tree of order
    
    2+o1n^2/3/^2log-^3.

  
  * 
    If → c for a constant c∈, then the probability that G has
    complex components is bounded away both from 0 and 1.
    The i-th largest component has order
    
    Θ_pn^2/3.

  
  * 
    If →∞, then _1 is complex and has order
    
    n^2/3+O_p(n^2/3).

    For i≥ 2, we have _i = Θ_p(n^2/3).

    Moreover, G has O_p(1) complex components. The probability that G has at least i complex 
    components is bounded away both from 0 and 1. If G has at least i complex
    components, then the i-th largest complex component (by this we mean _i(_G), where
    _G is the union of all complex components of G) has order Θ_p(n^2/3).

    Furthermore, if g≥ 1, then whp _1 is not embeddable on g-1, while all
    other components of G are planar.
 


Comparing the special case of g=0 in <Ref> with <Ref>, the following
discrepancies are apparent. Firstly, in the critical regime → c∈, <Ref><ref>
yields components of order Θ_p(n^2/3) compared to Θ(n^2/3) claimed by
<Ref>. The same holds for the orders of _i for i≥ 2 in the supercritical
regime →∞. Both points are due to minor mistakes in <cit.>; the proofs
given there in fact yield order Θ_p(n^2/3) instead of the claimed Θ(n^2/3). Secondly, the
error term in the order of the giant component given in <Ref><ref> is stronger than
the one from <Ref>. Finally, <Ref><ref> tells us that for
positive genus, the giant component is not only the unique largest component but also the unique
non-planar one.

Our second main result describes the time when the giant component covers almost all vertices. The
critical phase for the number of edges for this phenomenon is m=n+O(n^3/5). Here, the number of
vertices outside the giant component changes from ω(n^3/5) for m below the
critical range to Θ(n^3/5) within the critical range to o(n^3/5) beyond the critical
range.


  Let m=2+ n^-2/5n/2, where =(n)=o(n^2/5).
  Then  the largest component _1 of _g(n,m) is complex. Furthermore, for
  
    r(n) :=
        n^3/5   if -∞,
    
          n^3/5   if  c∈,
    ^-3/2n^3/5   if ∞ and =o((log n)^-2/3n^2/5),

  we have n-_1=O_pr(n) and  n-_1=Ω(r(n)).


The main improvement of <Ref> in comparison to <Ref> (the
corresponding result for g=0) is that <Ref>
only deals with the case ζ = o(n^1/15) and therefore leaves a
gap to the dense regime m=⌊μ n⌋ with μ∈(1,3) that has been
covered in <cit.>.
<Ref> closes this gap up to a factor (log n)^2/3. Additionally, <Ref>
provides a correction of the upper bound given in <cit.> on the
number of vertices outside the giant component. In <cit.>, the
upper bound was obtained with the help of an intermediate result (Theorem 2(iv) in <cit.>) about
the structure of the complex part (see <Ref> for
a definition). However, this intermediate result does not apply in the
regime m∼ n. <Ref> provides a slightly weaker
upper bound that is of larger order than the lower bound (albeit the
orders differ by less than every fixed growing function).

Our third main result covers the case when the number of edges is between the regimes of
the two phase transitions, that is, the average degree of the graph is between one and two. In this
`intermediate' regime, the largest component is complex, has genus g, and its order is
linear both in n and in the average degree of the graph.


  Let m=n/2, where =(n) converges to a constant in
  (1,2), and let _i=_i(G), i=1,2,…, be the i-th largest component of
  G=_g(n,m). Then
  
    _1 = -1n+O_pn^2/3.

  For i≥ 2, we have _i = Θ_p(n^2/3).

  Furthermore, if g≥ 1, then  _1 is not embeddable on g-1, while all other
  components are planar.


In the intermediate regime, or more generally, for m=n/2 with >1,
the classical  random graph G(n,m)  has a largest component of order (1+o(1))β n,
where β is the unique positive solution of the equation

    1-β = e^-αβ.

In particular, as long as >1 is a constant, the largest component of G(n,m) will
leave a linear number of vertices uncovered, see <Ref>.
Indeed, Karp <cit.> proved that the components of G(n,m) can be explored via a
Galton-Watson branching process with offspring distribution Po(); the survival
property of such a process is given by β above, yielding order (1+o(1))β n of the
largest component. For graphs on surfaces, however, there is no such simple approach to explore 
components.



As our last main result, we derive the asymptotic number of graphs embeddable on .


  For n→∞, the number of graphs in _g(n,m) is asymptotically
  given as follows.
  
  
  * 
    If m = 1+ n^-1/3n/2, where =(n)=o(n^1/3), then
    
    _g(n,m) =
          1+o(1)/π^1/2e^3/4e/1+ n^-1/3^n/2+/2n^2/3n^n/2+/2n^2/3-1/2   if →-∞,
    Θ(1)e^n/2-^2/4n^1/3n^n/2+/2n^2/3-1/2   if → c∈,
    expO()e/1- n^-1/3^n/2-/2n^2/3n^n/2+/2n^2/3-1/2   if →∞.

  
  * 
    If m=n/2, where =(n) converges to a constant in (1,2), then
    
    _g(n,m) =
          expO(n^1/3)e/2-^(2-)n/2n^n/2.

  
  * 
    If m = 2+ n^-2/5n/2, where =(n)=o(n^2/5), then
    
    _g(n,m) =
          expO(^-2/3n^3/5)/e^/2n^3/5n^n+3/10 n^3/5   if →-∞,
    expO(n^3/5)n^n+3/10 n^3/5   if → c∈,
    expO( n^3/5)^-3/4 n^3/5 n^n+3/10 n^3/5   if →∞ and
       =o((log n)^-2/3n^2/5).

  






 §.§ Proof techniques and outline


The techniques used in this paper are novel in comparison to the vast majority of papers on 
random graphs. Classical random graph results are usually proved with the help of probabilistic arguments
such as first and second moment methods, independence of random variables, or martingales. On the other hand, 
papers about random graphs on surfaces, e.g. <cit.>, 
use singularity analysis of generating functions. In contrast, we combine various complementary methods
to prove our results.

The starting point of our proofs are constructive decompositions of graphs, a method mostly used
in enumerative combinatorics. Every graph in
_g(n,m) can be decomposed into its complex components and non-complex components,
which then can further be decomposed into smaller parts. The most important structures occurring in
this decomposition are the so-called core and kernel of the graph. The decomposition
is constructive in the sense that every graph can be constructed in a unique way starting
from its kernel via its core and complex components (see <Ref>).

We interpret the aforementioned constructive decomposition in terms of combinatorial counting, 
in other words, we represent the number of graphs in the class _g(n,m) as a sum of 
subclasses that are involved in the decomposition. We proceed by determining the main contributions 
to the sum using a combinatorial variant of Laplace's method from complex analysis, a technique 
to derive asymptotic estimates of integrals that depend on a parameter n tending to infinity. To 
illustrate how we apply this approach, assume that we want to analyse a sum of the form

    A(n) = ∑_i∈ IB(i)C(n-i),

where i is a parameter related to one of the substructures occurring in the constructive decomposition,
e.g. the order of the core, say. We rewrite A(n) as

    A(n) = ∑_i∈ Iexpf(i)

with f(i)=log(B(i)C(n-i)) and then estimate the exponent f(i) in order to determine the main 
contribution to A(n) in the following sense. We determine a set J⊂ I so that the partial sum 
over all i∈ I∖ J (the tail of the sum) is of smaller order than the total sum (see 
<Ref> for a formal definition). The probabilistic interpretation of this main contribution
is that _g(n,m)  has its corresponding parameter i in the set J. In our example, this
will tell us the `typical' order of the core of _g(n,m).

The exact method how we estimate the value of the tail and compare it to the total value of the sum will
differ from case to case. In some cases, rough bounds provided by maximising techniques will suffice; in
other cases, we need better bounds, which we derive by using Chernoff bounds or by bounding the sums via
integrals. Systematic applications of these techniques enable us to derive the exact ranges of the main 
contributions. From the main contributions, we deduce the orders of components, component structure, and other structural 
properties of _g(n,m) by applying both combinatorial methods (e.g. double counting) and 
probabilistic techniques (e.g. Markov's and Chebyshev's inequalities).

This paper is organised as follows. After presenting the necessary notation and definitions
in <Ref>, we give an overview of the proof strategy in <Ref>; in particular,
we derive the aforementioned representation of _g(n,m) as a sum. In 
<Ref>, we determine the main contributions to this sum using the techniques
mentioned above. From these results, we derive structural properties of _g(n,m) in
<Ref>. <Ref> are devoted to the proofs of our
main results and of the auxiliary results, respectively. Finally, we discuss 
various open questions in <Ref>.



 §.§ Related work


The order of the largest component of the  random graph G(n,m) at the time of the phase
transition has been extensively studied
<cit.>. Most of the results
have been proved using purely probabilistic arguments (e.g. random walks, martingales), leading to 
even stronger results than the ones stated in <Ref>, e.g. about the limiting distribution 
of the order and size of the largest component <cit.>. 
In the case of _g(n,m), the additional condition of the graph being embeddable on  makes it 
virtually impossible to use the same techniques in order to derive such strong results.

Comparing <Ref>, the main differences appear when the giant component arises in the
supercritical regime, that is, when →∞. Firstly, the order of the giant
component is only about half as large in _g(n,m) as it is in G(n,m). Secondly, the
i-th largest component _i for fixed i≥ 2 is much larger in _g(n,m) than in
G(n,m). These two differences are closely related for the following reason. In G(n,m), the
number n' of vertices and m' of edges outside the giant component are such that m' =
(1+'n^-1/3)n'/2 with '→-∞ and thus, G(n',m') only has
small components. In _g(n,m), the smaller order of the giant component enforces m' to
be in the critical regime, where '→ c∈, thus resulting in larger orders
for _i with i≥ 2. Lastly, while each such _i is a tree  for the  random graph,
it has a positive probability to be complex for _g(n,m).

Planar graphs and graphs embeddable on  have been investigated separately for the `sparse'
regime m ≤ n+o(n) <cit.> and for the `dense' regime m = ⌊μ n⌋ with
μ∈(1,3) <cit.>. From a random graph
point of view, in particular when the giant component is considered, the sparse regime is the more
interesting regime. In the sparse regime, Kang and Łuczak <cit.> supplied new
resourceful proof methods—some of which we apply in a somewhat similar fashion in this paper—combining
probabilistic and graph theoretic methods with techniques from enumerative and analytic
combinatorics. On the other hand, minor mistakes in <cit.> led to results that featured
order terms that claimed to be stronger than what has actually been proved. One contribution of
this paper is to correct and strengthen these results from <cit.>.

In the dense regime, Giménez and Noy <cit.> and Chapuy, Fusy, , Mohar, and
Noy <cit.> use techniques from analytic combinatorics to
prove limit laws for graphs embeddable on . The advantage of their techniques is that one
method can be applied to derive a range of various limit laws, e.g. on the number of components,
the order of the largest component, and the chromatic and list-chromatic number. On the other hand,
the techniques are limited to a) the class _g(n) of n-vertex graphs embeddable 
on , in other words, graphs with n vertices and an arbitrary number of edges, or b) the class
_g(n,⌊μ n⌋), where μ is a constant. A random graph chosen from 
the class _g(n) is averaged over all graphs with an arbitrary number of edges and
thus not appropriate when we look at a specific range of m.[In fact, the properties of a
  random graph chosen from _g(n) are dominated by the graphs whose edge density 
  is quite large, more precisely, when μ≈ 2.21 <cit.>.]
On the other hand, the class _g(n,⌊μ n⌋) scales the number m of edges
as a linear function in n, which is not fine enough in order to capture the changes that take place
within the critical windows, which have length Θ(n^2/3) for <Ref> and Θ(n^3/5)
for <Ref>. In terms of critical behaviour these techniques are therefore not applicable.





§ PRELIMINARIES




 §.§ Asymptotic notations


By  we denote the set of non-negative integers.
In order to express orders of components in a random graph when n tends to infinity, we use the
following notation. Recall that an event holds with high probability, or  for short,
if it holds with probability tending to one as n tends to infinity.


  Let X=(X_n)_n∈ be a sequence of random variables and let f→_≥ 0 be a function. For
  c∈^+ and n∈, consider the inequalities
  
    X_n   ≤ c f(n),
    X_n   ≥ c f(n).

  We say that
  
  
  * X_n = O(f) , if there exists c∈^+ such that (<ref>) holds ;
  
  * X_n = o(f) , if for every c∈^+, (<ref>) holds ;
  
  * X_n = Ω(f) , if there exists c∈^+ such that (<ref>) holds ;
  
  * X_n = ω(f) , if for every c∈^+, (<ref>) holds ;
  
  * X_n = Θ(f) , if both X_n = O(f) and X_n = Ω(f) ;
  
  * X_n = O_p(f), if for every δ>0, there exist c_δ∈^+ and N_δ∈
    such that (<ref>) holds for c=c_δ and n≥ N_δ with probability at
    least 1-δ;
  
  * X_n = Θ_p(f), if for every δ>0, there exist c_δ^+,c_δ^-∈^+ and
    N_δ∈ such that for n≥ N_δ with probability at least 1-δ, both
    (<ref>) holds for c=c_δ^+ and (<ref>) holds for c=c_δ^-.
  

The special case of X=O_p(1) is also known as X being bounded in probability.




 §.§ Graphs on surfaces


Given a graph G, we denote its vertex set and its edge set by V(G) and E(G), respectively.
All graphs in this paper are vertex-labelled, that is, V(G)=[n] for some n∈. Let g∈ be fixed.
An embedding of a graph G on , the orientable surface of genus g, is a drawing of
G on  without crossing edges. If G has an embedding on , we call G
embeddable on . Clearly, embeddability is monotone in g, i.e. every graph that is
embeddable on  is also embeddable on g+1. By the genus of a given graph G 
we denote the smallest g∈ for which G is embeddable on . Graphs with genus zero are 
also called planar.

Let  be a connected graph embeddable on . We say that  is unicyclic 
if it contains precisely one cycle and we call  complex (also known as multicyclic) if it contains at least two 
cycles; the latter is the case if and only if  has more edges than vertices. If  
is complex, we call

    ():=E()-V()

the excess of . For a non-connected graph G, we define (G) to be the sum of the
excesses of its complex components (and set (G)=0 as a convention if G has no
complex components). G is called complex if all its components are complex.




 §.§ Complex part, core, and kernel


Let G be any graph. The union _G of all complex components of G is called the
 of G. The core _G of G is defined as the maximal subgraph of
minimum degree at least two of _G. The core can also be obtained from the  by
recursively deleting vertices of degree one (in an arbitrary order). Vice versa, the can be constructed from the core by attaching trees to the vertices of the core. Finally, the
kernel _G of G is constructed from the core _G by replacing all vertices
of degree two in the following way. Every maximal path P in _G consisting of vertices of
degree two is replaced by an edge between the vertices of degree at least three that are adjacent
to the end vertices of P. By this construction, loops and multiple edges can occur. Reversing the construction, 
the core arises from the kernel by subdividing edges.

It is important to note that _G is non-empty as soon as _G is, because each
component of the complex graph _G contains a non-empty core with at least one vertex 
of degree at least three. Furthermore, _G has minimum degree at least three and might 
contain loops and multiple edges. Observe that G is embeddable on  if and only if 
_G is. In particular, G and _G have the same genus. Also observe that 
(G) = (_G) by definition and (_G) = (_G) = (_G), 
because subdividing edges and attaching trees changes the number of vertices and edges by the same 
amount.

Given a graph G with n vertices, we denote the number of vertices of the _G, the core _G, and the kernel _G by n_, n_, and
n_, respectively. The number of edges of _G, _G, and _G 
satisfy

    E(_G) = n_+(G),
          E(_G) = n_+(G),
          E(_G) = n_+(G).

The kernel has minimum degree at least three by definition and thus has at least 3/2n_
edges. A kernel is called cubic if all its vertices have degree three; in that case, it has
precisely 3/2n_ edges. The deficiency of G is defined as

    (G) := 2E(_G)-3n_ = 2(G) - n_.

Clearly, the deficiency is always non-negative and (G)=0 if and only if the kernel
_G is either empty or cubic. The definition of the excess and deficiency of a graph
immediately implies the following relation between the deficiency, the excess, and the number of
vertices and edges of the kernel.


  Given a graph G, the numbers n_ of vertices and m_ of edges in the kernel _G of G are
  
    n_ = 2(G) - (G)
            and    
        m_ = 3(G) - (G).






 §.§ Useful bounds


We will
frequently use the following widely known formulas.

    1+x   =expx-x^2/2+x^3/3+O(x^4)      if x=o(1),   
    
      1+x   ≤expx,         
    
      1+x   ≥expx-x^2/2      if x≥0,

To derive bounds for the factorial n! and the falling factorial (k)_i := k!/(k-i)! we shall use the inequalities

    √(2π n)n/e^n   ≤ n!≤ e√(n)n/e^n,
    
     k^iexp-i^2/2(k-i)   ≤ (k)_i≤ k^iexp-i(i-1)/2k.

For 1≤ k≤ n-1 we will also use refined bounds for the binomial coefficient obtained by 
applying (<ref>) thrice.

    √(2π)n^n+1/2/e^2 k^k+1/2(n-k)^n-k+1/2   ≤nk≤en^n+1/2/2π k^k+1/2(n-k)^n-k+1/2 .

We shall also use the inequality

    1/a+b≥1/a - b/a^2  if a≠0, a+b>0.


Finally, we need some well known inequalities from probability theory. Given a random variable X, we
denote by X its expectation. The variance of X is then defined as 
    σ^2:=X-X^2 = X^2-X^2.

For a non-negative random variable X and any t>0, Markov's inequality states that

    X≥ t≤X/t.

A stronger bound—which additionally holds for arbitrary random variables—is provided by Chebyshev's inequality.
For any random variable X and any t>0, we have

    X-X≥ t≤σ^2/t^2.

In terms of Chernoff bounds, we shall need the two special cases of normal distributions
and binomial distributions. For a normally distributed random variable X, we have, for any given t>0,

    ..X-X≥ t≤ 2exp-t^2/2σ^2.

If X is a binomially distributed random variable, then

    ..X-X≥ t≤ 2exp-t^2/2X+t/3.







§ PROOF STRATEGY




 §.§ Decomposition and construction


Throughout the paper, let g∈ be fixed.
We have seen in <Ref> that any graph that is embeddable on  can be decomposed
into a) its  and b) trees and unicyclic components. The  can then further be
decomposed so as to obtain the core and the kernel. Vice versa, we can construct a graph on 
by performing the reverse constructions.


  The following steps construct every graph embeddable on .
  
  
  
  *  Pick a kernel, i.e. a multigraph with minimum degree at least three
    that is embeddable on ;
  
  *  subdivide the edges of the kernel to obtain a core;
  
  *  to every vertex v of the core, attach a rooted tree T_v (possibly only
    consisting of one vertex) by identifying v with the root of T_v, so as to obtain a
    complex graph;
  
  *  add trees and unicyclic components to obtain a general
    graph embeddable on .
  



To avoid overcounting in <ref> if the kernel has loops or multiple
edges, multigraphs will always be weighted by the compensation factor introduced by Janson,
Knuth, , and Pittel <cit.>, which is defined as follows. Given a multigraph M and an integer i≥
1, denote by e_i(M) the number of (unordered) pairs {u,v} of vertices for which there are
exactly i edges between u and v. Analogously, let ℓ_i(M) denote the number of vertices
x for which there are precisely i loops at x. Finally, let ℓ(M)=∑_i iℓ_i(M) be the
number of loops of M. The compensation factor of M is defined to be

    (M):=2^-ℓ(M)∏_i=1^∞(i!)^-e_i(M)-ℓ_i(M).

In <ref>, the compensation factor enables us
to distinguish multiple edges and loops at the same vertex (because of the factors 1/i!) as well
as the different orientations of loops (because of the factor 2^-ℓ(M)). This fact ensures
that there is no overcounting in <ref>. Indeed, if a core 
has kernel , then  can be constructed from  by subdividing edges in
precisely 1/() different ways; thus, assigning weight () to
 prevents overcounting.

We denote by


  * _g the class of all graphs embeddable on ;

  * _g the class of all s of graphs in _g;

  * _g the class of all cores of graphs in _g;

  * _g the class of all kernels of graphs in _g;

  *  the class of all graphs without complex components.

In other words, _g is the class of all complex graphs embeddable on ;
_g consists of all complex graphs embeddable on  with minimum degree at least two;
and _g comprises all (weighted) multigraphs embeddable on  with minimum degree at least three. 
The empty graph lies in all the classes above by convention.

If n,m∈ are fixed, we write _g(n,m) for the subclass of
_g containing all graphs with exactly n vertices and m edges. By
_g(n,m) we denote a graph chosen uniformly at random from all graphs in
_g(n,m). We use the corresponding notation also for the other classes defined
above.

The construction of graphs in _g from their kernel via the core and as described in <ref>–<ref> can be translated to relations between the numbers of graphs
in the previously defined classes. Starting from _g(n,m),
<ref> immediately gives rise to the identity

    _g(n,m) =
      ∑_n_,lnn__g(n_,n_+l)·(n_,m_),

where n_ = n-n_ and m_ = m-n_-l. Indeed, for each fixed number
n_ of vertices in the  and each fixed excess l


  * the binomial coefficient counts the possibilities which vertices lie in the ,

  * _g(n_,n_+l) counts the s with n_
  vertices and n_+l edges, and

  * (n_,m_) counts all possible arrangements of non-complex
  components.


If _g(n_,n_+l) and (n_,m_)
are known, then we can use (<ref>) to determine _g(n,m).
Determining _g(n_,n_+l) turns out to be quite a challenging task,
to which we devote a substantial part of this paper. The number (n_,m_),
on the other hand, can be determined using known results.




 §.§ Graphs without complex components


The class  of graphs without complex components (i.e. each component is either a tree or unicyclic)
has been studied by Britikov <cit.> and by Janson,
Knuth, , and Pittel <cit.>, who determined the number of graphs in (n,m) for different regimes of m.


  Let m=(1+ n^-1/3)n/2 with =(n)<n^1/3 and
  let ρ(n,m) be such that
  
    (n,m)=n2mρn,m.

  There exists a constant c>0 such that for
  
    f(n,m)=c2/e^2m-nm^m+1/2n^n-2m+1/2/(n-m)^n-m+1/2,

  we have
  
  
  * 
    ρn,m=1+o(1), if -∞;
  
  * 
    for each a∈, there exists a constant b=b(a)>0 such that ρn,m≥ b whenever ≤ a;
  
  * 
    ρn,m≤ n^-1/2f(n,m) if >0 and =o(n^1/12);
  
  * 
    ρn,m≤ f(n,m) if >0.
  


<Ref><ref>, <ref>, and <ref> are proven in 
<cit.> and <cit.>, but <ref> is a slight extension of the results in <cit.> 
which we prove in <Ref> along the following lines. Inspired by the proof of <ref>
in <cit.>, we bound ρ(n,m) by a contour integral and prove that this integral has value at most f(n,m)
for all >0.

Clearly, every graph in  is planar and thus also embeddable on . This fact,
together with <Ref> and <Ref><ref> and <ref> will be enough to
prove <Ref><ref> and <ref>. For all other regimes, <Ref> will
provide a very useful way to bound the number (n,m) in (<ref>).




 §.§ Complex parts


For the number _g(n_,n_+l),
we analyse <ref>–<ref>
in order to derive an identity similar to (<ref>). Firstly, we need to sum over
all possible numbers n_ of vertices in the core; the number of edges in the core is then
given by n_+l. For fixed n_, n_, and l, we have


  * n_n_ choices for which vertices of the  lie in the
  core,

  * _g(n_,n_+l) ways to choose a core, and

  * n_ n_^n_-n_-1 possibilities to attach n_ rooted trees with
  n_ vertices in total to the vertices of the core.

By <ref>, we thus deduce that

    _g(n_,n_+l) = 
      ∑_n_n_n__g(n_,n_+l)n_ n_^n_-n_-1 .


In order to determine _g(n_,n_+l), recall that by <Ref>,
the number of vertices and edges in the kernel depend only on the excess and deficiency of the
graph. Thus, we choose the deficiency d as the summation index. The number of ways to construct a
core from a kernel according to <ref> cannot
be described in an easy fashion like the constructions in <ref>
and <ref>. We will investigate this construction step in more detail
in <Ref>. For a kernel ∈_g(2l-d,3l-d),
consider the number of different ways to subdivide its edges that result in a core with n_
vertices and n_+l edges. Denote by φ_n_,l,d the average of this number, taken over
all kernels in _g(2l-d,3l-d). With this notation, we deduce from <ref> and
<ref> that

    _g(n_,n_+l) =
      ∑_dn_2l-d_g(2l-d,3l-d)φ_n_,l,d.

Recall that the multigraphs in _g are weighted. Accordingly,
_g(2l-d,3l-d) does not denote the number of these multigraphs, but the
sum of their weights.




 §.§ Analysing the sums


In each of (<ref>), (<ref>), and (<ref>), we may assume that the
parameters n_,n_,l,d of the sums only take those values for which the summands are
non-zero.

  We call values for a parameter (or a set of parameters) admissible, if there exists at least one graph 
  satisfying these values for the corresponding parameters.

The definition of the parameters, together with <Ref>, directly yield the following necessary
conditions for admissibility.



  * 0≤ n_≤ n;

  * 0≤ n_≤ n_;

  * 0≤ l≤ m-n_;

  * l=0 if and only if n_=0;

  * 
  l≤ 2n_ + 6(g-1);

  * 0≤ d≤ 2l.


Inequality <ref> is due to Euler's formula applied to the core. These bounds will frequently be used; 
if we use other bounds, we will state them explicitly.

On the first glance, the sole application of (<ref>), (<ref>), and (<ref>)
seems to be to determine the number of graphs with given numbers of vertices and edges in the classes
_g, _g, and _g. However, we shall use these sums to
derive typical structural properties of graphs chosen uniformly at random from one of these classes.

Our plan to derive such properties from the sums (<ref>), (<ref>), and (<ref>) 
is as follows. Once we have determined the values _g(2l-d,3l-d)
and φ_n_,l,d, we consider the parameters n_,n_,l,d of the sums
one after another. For each parameter i, we seek to determine which range for i provides the `most important' 
summands. To make this more precise, let us introduce the following notation.


  For every n∈, let I(n),I_0(n)⊂ be finite index sets with I_0(n)⊆ I(n).
  For each i∈ I(n), let A_i(n)≥ 0. We say that the main contribution to the sum
  
    ∑_i∈ I(n)A_i(n)

   is provided by i∈ I_0(n) if
  
    ∑_i∈ I(n)∖ I_0(n)A_i(n) = o∑_i∈ I(n)A_i(n),

  where n→∞. The sum over i∈ I(n)∖ I_0(n) is then called the tail of
  ∑ A_i(n).


We shall determine index sets I_(n), I_(n), I_l(n), I_d(n) so that the main
contributions to the sums in (<ref>), (<ref>), and (<ref>) are
provided by n_∈ I_(n), n_∈ I_(n), l∈ I_l(n), and d∈
I_d(n), respectively. This will yield statements about the size of these values in the following way.
For fixed m=m(n), the index set I_(n), for example, will be of the type [c_1f(n),c_2f(n)] 
for certain constants 0<c_1<c_2 and a certain function f=f(n). This implies
that if G=_g(n,m), then  n_∈ I_(n) and thus n_=Θ(f).

The main challenge is to find the `optimal' intervals 
I_(n), I_(n), I_l(n), I_d(n) in view of <Ref> in the
sense that they should be a) large enough so as to provide the main contribution and b)
as small as possible so as to yield stronger concentration results. To achieve these two
antipodal goals is a difficult task whose solution will differ from case to case.
In order to prove that a given interval indeed provides the main contribution to a sum, 
we bound the tail of the sum using various complementary methods including maximising 
techniques (e.g. <Ref>), Chernoff bounds (<Ref>), 
and approximations by integrals (<Ref>).

Determining the main contributions to (<ref>), (<ref>), and (<ref>)
will yield structural statements like the typical order of the , the core, and the kernel
of G=_g(n,m). In order to derive the component structure of G, we further apply combinatorial techniques
like double counting (e.g. <Ref> and <Ref>) and probabilistic methods such as Markov's 
and Chebyshev's inequalities (<Ref>).





§ KERNELS, CORES, AND S


For the remainder of the paper, let n,m,n_,n_,l,d∈ be such that m=m(n)≤(1+o(1))n
and such that n_, n_, l, and d are admissible (in terms of <Ref>).
Furthermore, set n_=n-n_ and m_=m-n_-l.

The aim of this section is to determine the main contributions (in the sense of <Ref>) to the sums in (<ref>),
(<ref>), and (<ref>). In other words, we derive the typical orders of the
 and the core of G=_g(n,m), as well as the excess and the deficiency of G. These orders
will be the main ingredients for the proofs of Theorems <ref>–<ref>.
For all results in this section, we defer the proofs to <Ref>.



 §.§ Kernels


Throughout this section, we assume l≥1.
As a basis of our analysis of (<ref>), (<ref>), and (<ref>), we
first have to determine the sum _g(2l-d,3l-d)
of weights of the multigraphs in _g(2l-d,3l-d). 
We start with the case when the kernel is cubic (or equivalently, d=0). The number of cubic kernels was determined in <cit.> by Fang and 
the authors of the present paper.


  The number of cubic multigraphs with 2l vertices and 3l edges embeddable on , weighted by
  their compensation factor, is given by
  
    _g(2l,3l)=1+Ol^-1/4e_g l^5g/2-7/2γ_^2l(2l)! ,

  where γ_=79^3/4/54^1/2≈ 3.606 and e_g>0 is a constant depending
  only on g.


The number of connected cubic kernels will be of interest as well.


  The number of connected multigraphs in _g(2l,3l), weighted by
  their compensation factor, is
  
    1+Ol^-1/4c_g l^5g/2-7/2γ_^2l(2l)! ,

  where γ_ is as in <Ref> and c_g>0 is a constant depending only on g.


In particular, <Ref> imply that _g(2l,3l) is connected with
probability tending to c_g/e_g>0; in other words, the probability that a random cubic kernel
is connected is bounded away from zero.

Before we consider kernels with non-zero deficiency, we shall look at the structure of cubic kernels.
We aim to find the giant component of _g(n,m) and prove that it is complex, hence finding the giant
component of the kernel would be a basis for a complex giant component in _g(n,m).
Moreover, we would like this giant component to have genus g. The following result from <cit.>
provides us with a component of genus g in a cubic kernel.


  If g≥ 1, then _g(2l,3l)  has one component of genus g and all its other
  components are planar.


Intuitively, the non-planar component provided by <Ref> should be the largest
component of the kernel, ideally even large enough to be the giant component. The following result shows that this
component indeed covers almost all vertices in the kernel.


  Let g≥ 1. Denote by (G) the subgraph of G=_g(2l,3l) consisting of all planar
  components. Then (G) = O_p(1). Furthermore, (G) is even and there exist constants
  c^+,c^-∈^+ such that for every fixed integer i≥ 1 and sufficiently large l,
  
    c^-i^-7/21-i/l^5g/2-7/2≤(G)=2i≤
        c^+i^-7/21-i/l^5g/2-7/2.



For the case g=0, <cit.> provides an analogous statement to (<ref>)
for the number of vertices outside the giant component of _0(2l,3l).

Let us now look at general (not necessarily cubic) kernels. For such
kernels, we are not able to give a precise formula for their number, but we can bound their number
by comparing them to cubic kernels via a double counting argument.


  Let k∈ be fixed. For ∈_g, denote by
  
  
  * 𝒫_1 the property that  has precisely k components;
  
  * 𝒫_2 the property that, if g≥1, then each component of  has genus strictly 
    smaller than g.
  
  For i=1,2, denote by _g(n_,m_;𝒫_i) the subclass of
  _g(n_,m_) of kernels that have property 𝒫_i. Then
  
    _g(2l-d,3l-d)/_g(2l,3l)≤6^d/d!  and  _g(2l-d,3l-d;𝒫_i)/_g(2l,3l;𝒫_i)≤6^d/d! for i=1,2.

  If in addition d≤2/7l, then also
  
    _g(2l-d,3l-d)/_g(2l,3l)≥1/216^dd!  and  _g(2l-d,3l-d;𝒫_i)/_g(2l,3l;𝒫_i)≥1/216^dd! for i=1,2.



<Ref> has two main applications. On one hand, together with <Ref>,
<Ref> provides a way to bound the value _g(2l-d,3l-d) in
(<ref>). On the other hand, <Ref> will also
enable us to extend the structural results from <Ref> to kernels with
a fixed constant deficiency d (see <Ref>).




 §.§ Core and deficiency


We first determine the main contributions to the sums in (<ref>) and (<ref>).
By definition, _g(0,0)=1. Thus, throughout this section we will assume that
both n_≥1 and l≥1 (recall that l=0 if and only if n_=0).
Observe that (<ref>), (<ref>), and the identity

    n_n_n_2l-d =
      (n_)_n_/(2l-d)!(n_-2l+d)!

imply that

    _g(n_,n_+l) = 
      ∑_n_,d(n_)_n__g(2l-d,3l-d)φ_n_,l,d   n_ n_^n_-n_-1/(2l-d)!(n_-2l+d)! .


The factor _g(2l-d,3l-d) in (<ref>) can be bounded using <Ref> 
and <Ref>. The term φ_n_,l,d, however, is still unknown. Recall that this value
denotes the average number, over all ∈_g(2l-d,3l-d), of
different ways to subdivide the edges of  that result in a core with n_ vertices
and n_+l edges.


  There exists a function ν=ν(n_,l,d) such that
  
    φ_n_,l,d = (n_-2l+d)!n_+ν l -13l-d-1

  and -5≤ν≤ 1.


Let us now determine the value of the sum in (<ref>) over n_, as well as its main contribution. 
To this end, we apply <Ref> to (<ref>), gather all parts
of the equation that depend on n_, and denote the sum over these values by Σ_.

  
    There exists a function τ=τ(l,d) such that
    
    
  * 1/216≤τ≤6 for all 0≤ d≤⌊2l/7⌋;
    
  * 0≤τ≤6 for all ⌊2l/7⌋ < d≤2l;
    
    and
    
    _g(n_,n_+l)=n_^n_-1_g(2l,3l)/(2l)!   ∑_d=0^2l2ldτ^d/(3l-d-1)!Σ_,

    where
    
    Σ_=Σ_(n_,l,d):=∑_n_(n_)_n_/n_^n_n_(n_+ν l-1)_3l-d-1.

  

  The strategy to determine the main contribution to Σ_ is roughly
  as follows. Using inequalities from <Ref>, we bound
  Σ_(n_,l,d) from above by a sum of the type
  
    ∑_n_expA(n_,n_,l,d).

  The derivative of A(n_,n_,l,d) with respect to n_ will show to have a zero at n_ =
  (1+o(1))n_, where
  
    n_ = √(n_(3l-d)).

  We then substitute n_ = n_ + r and prove that the resulting sum—up to
  a scaling factor—corresponds to a normally distributed random variable to which the Chernoff
  bound (<ref>) applies. Finally, for n_ from the range of the main 
  contribution to the upper bound, we derive a similar lower bound, which will enable us to derive 
  the main contribution to Σ_.
  
  
    Let f_=f_(n_,l,d) be such that
    
    Σ_(n_,l,d) = √(n_)n_(3l-d)/e^(3l-d)/2expf_.

    
    
  * 
      There exist constants a_^+,b_^+∈ such that
      
    f_≤ a_^+ + b_^+√(l^3/n_).

    
  * 
      For every function ϵ(n_)=o(1), there exist constants N_∈, a_^-,b_^-∈ such that
      whenever n_≥ N_ and 7/2d≤ l≤ϵ n_, then
      
    f_≥ a_^- + b_^-√(l^3/n_).

    
  * 
      For every 0<δ<1/2, whenever
      n_,l→∞ and 7/2d≤ l≤ϵ n_, where ϵ=ϵ(n_)=o(1) is given, the main contribution to
      Σ_ is provided by
      
    n_∈ I_^δ(n_,l,d) := {k∈ | k-n_ < δn_}.

    
  

  Our next aim is to analyse the sum over d in (<ref>). To this end, observe that for
  
    Σ_d = Σ_d(n_,l) := ∑_d2ld(3l-d)^(3l-d+2)/2e^d/2τ^d/(3l-d)!n_^d/2exp(f_),

  (<ref>) and (<ref>) yield
    
    _g(n_,n_+l)=n_^n_+3l/2-1/2_g(2l,3l)/e^3l/2(2l)!Σ_d.


We determine the value of Σ_d, as well as its main contribution, in a similar fashion as for Σ_.
  
  

  Let f_d=f_d(n_,l) be such that
  
    Σ_d = (3l)^-(3l-1)/2e^3lexpf_d.

  
  
  * 
    There exist constants a_d^+∈ and b_d^+∈ such that
    
    f_d≤ a_d^+ + b_d^+√(l^3/n_).
 
  
  * 
    For every function ϵ(n_)=o(1), there exist constants
    N_∈ and a_d^-,b_d^-∈ such that
    
    f_d≥ a_d^- + b_d^-√(l^3/n_),

    whenever n_≥ N_ and l≤ϵ  n_.
  
  * 
    There exists a constant β_d^+∈^+ such that for n_,l→∞ and l=o(n_), the main contribution to
    Σ_d is provided by
      
      
  * d∈ I_d(n_,l) := {0} if l=o(n_^1/3);
      
  * d∈ I^h_d(n_,l) := { k∈| k≤ h(n_)} for every fixed function h=h(n_)=ω(1) if
        l=Θ(n_^1/3);
      
  * d∈ I_d(n_,l) := { k∈| k ≤β_d^+√(l^3/n_)}
         if l=ω(n_^1/3).
      
  


  Interpreted in a probabilistic sense, <Ref> immediately
  yield the typical order of a core of a complex graph, as well as the typical deficiency.


    For every function ϵ(n_)=o(1), if n_,l→∞ and
    l≤ϵ  n_, then  =_g(n_,n_+l) has a core with √(3n_ l)(1+o(1)) vertices.
    Furthermore, the deficiency of  is given by
    
    () =
          
            0    if l = o(n_^1/3),
    
            O_p(1)    if l = Θ(n_^1/3),
    
            O√(l^3/n_)   if l = ω(n_^1/3).



Observe that <Ref> requires n_ and l to be growing and l to be of smaller
order than n_. We shall later see that this will  be the case for the of _g(n,m).

In addition to <Ref>, which tells us the deficiency and the order of the core of
_g(n_,n_+l), <Ref> also enables us to express
the number of complex graphs that are embeddable on .


  For all positive admissible values n_,l, we have
  
    _g(n_,n_+l)=n_^n_+3l/2-1/2_g(2l,3l)e^3l/2/(3l)^(3l-1)/2(2l)!expf_d.



This finalises our analysis of (<ref>) and (<ref>).




 §.§ Complex part and excess


In this section we derive the main contributions with respect to n_ and l to the double 
sum (<ref>).
In the previous section, we had to distinguish the cases n_=0 and n_>0 in order
to determine the number of complex graphs. Similarly, it will turn out that our asymptotic formulas will be quite different
depending on whether the number m_=m-n_-l of edges outside the complex part is zero or not.
In order to keep expressions simple, we will deal with the special cases n_=0 and m_=0
separately.

To this end, define _g^*(n,m) to be the subclass of _g(n,m) consisting
of all graphs for which the complex part is non-empty and the non-complex part has at least one edge.
After bounding _g^*(n,m), we shall see that the two special cases n_=0 and m_=0 are `rare' in the sense that almost all graphs in
_g(n,m) are also in _g^*(n,m).


  For every m=m(n) as in <Ref><ref>, <Ref>, or <Ref> we have
  
    _g(n,m)∖_g^*(n,m)=o_g^*(n,m).



By <Ref>, we can determine the main contributions to (<ref>) by deriving the
main contributions to the corresponding sum for _g^*(n,m), namely

    _g^*(n,m) =
      ∑_n_,lnn__g(n_,n_+l)·(n_,m_),

where n_ and l take all admissible values with n_>0 and m_>0.

In order to analyse (<ref>), we derive an upper bound for the sum over n_ and
subsequently also for the sum over l. These upper bounds indicate which intervals I_(n) and I_l(n)
for n_ and l, respectively, `should' provide the main contribution to (<ref>). For
n_ and l from these intervals, we then derive lower bounds and prove that the lower bound for
n_∈ I_(n) and l∈ I_l(n) is much larger than the tails of the upper bound, thus 
proving that the main contribution to (<ref>) is indeed provided by n_∈ I_(n)
and l∈ I_l(n).

Applying (<ref>), <Ref>, <Ref>, and <Ref>
to (<ref>), we have

    _g^*(n,m) = Θ(1)n^n+1/2e/2^m∑_l l^5g/2-3-3l/2ϕ^l∑_n_ρ(n_,m_) ψ(n_,l),

where ϕ=2√(e)γ_^23^-3/2 and

    ψ(n_,l) = (2/e)^n_n_^3l/2-1n_^2m_-n_-1/2m_^-m_-1/2expf_d.


Consider the sum

    Σ_=Σ_(n,m,l):=∑_n_ρ(n_,m_) ψ(n_,l),

where we sum over all values of n_ that are admissible in _g^*(n,m).
We shall see in <Ref> that for fixed l>0, the main contribution to Σ_ is
centred around

    n_ = 2m-n-2l.

The corresponding numbers of vertices and edges in the non-complex components are given by

    n_ = 2(n-m+l)
          and    m_ = n-m+l.

The bounds for Σ_ will depend on whether l is `small' or `large', more precisely, whether

    9m_^23l/2-1≤n_^3

is satisfied (if so, l is considered small) or not (if so, l is large). 


  Define
  M_=M_(n,m,l) by
  
    M_ =
        2/e^2m-nn_^3l/2-1m_^-m_-1   if (<ref>) holds,
    2/e^2m-nl^l/2-1/3m_^-m_+l-5/3   otherwise.

  Then
  
    Σ_≤ n^3/2expO(l)M_.

  Furthermore, for every fixed positive valued function ϵ=ϵ(n)=o(1) and every δ>0,
  there exists N∈ such that for all n≥ N
  
    Σ_≤Θ(1)n^3/2e/2^2l(1+δ)^lM_,

  whenever
  
    9m_^23l/2-1≤ϵn_^3.


For the case that m is larger than n/2 by only a small margin, we prove a stronger bound
with the help of <Ref><ref> and a more careful analysis of the sums involved.

  Let m=(1+ n^-1/3)n/2 with =o(n^1/12) and →∞.
  Then we have
  
    Σ_≤ n^2/3expO(l)M_.



In <Ref>, the exact bound depends on whether (<ref>) is satisfied or violated. 
Correspondingly, we set

    Σ_l := ∑_l l^5g/2-3-3l/2ϕ^lΣ_(n,m,l),

where l takes all admissible values for which (<ref>) holds, and

    Σ̃_l := ∑_l l^5g/2-3-3l/2ϕ^lΣ_(n,m,l),

where l takes all admissible values for which (<ref>) is violated. Heuristically, Σ_l should be the larger
of the two sums, because l^-3l/2 should be the dominating term and this term is small when l is large (which is 
the case when (<ref>) is violated). We shall see in <Ref> that Σ̃_l is indeed negligible.

Accordingly, we focus on Σ_l for the moment.
Applying the bound (<ref>), we have Σ_l ≤Σ_l^+, where

    Σ_l^+ = 2/e^2m-n∑_l l^5g/2-3-3l/2ϕ^ln_^3l/2-1m_^-m_exp(O(l)).

The main contribution to Σ_l^+ should be centred around its largest summand. We approximate the largest
summand by ignoring polynomial terms and replacing the term exp(O(l)) by (e/2)^2l (which we saw in <Ref> 
to be a good approximation when (<ref>) holds). The remaining terms attain their largest value at the unique solution l_0 of the equation

    l_0 = ϕ^2/3(2m-n-2l_0)/e^1/32^4/3(n-m+l_0)^2/3 ,     m-n<l_0<m-n/2 .

Before we proceed to prove that the main contribution to _g^*(n,m) is indeed provided by
l `close to' l_0 (and thus the `typical excess' of a graph in _g^*(n,m) is close
to l_0), let us take a closer look at the value l_0. We introduce
the following notation for the seven different cases of m(n) from our main results.



  :
  m(n)=(1+ n^-1/3)n/2 with =(n)=o(n^1/3) and →-∞, the first subcritical regime;

  :
  m(n)=(1+ n^-1/3)n/2 with → c_∈, the first critical regime;

  :
  m(n)=(1+ n^-1/3)n/2 with =o(n^1/3) and →∞, the first supercritical regime;

  :
  m(n)=n/2 with =(n)→ c_∈(1,2), the intermediate regime;

  :
  m(n)=(2+ n^-2/5)n/2 with =(n)=o(n^2/5) and →-∞, the second subcritical regime;

  :
  m(n)=(2+ n^-2/5)n/2 with → c_∈, the second critical regime;

  :
  m(n)=(2+ n^-2/5)n/2 with =o((log n)^-2/3n^2/5) and →∞, the second supercritical regime.


The union of the first three cases will also be referred to as the first phase transition, while the union
of the last three cases is called the second phase transition. In  and , our main results
will follow from well-known results. Thus, for the rest of this section, we assume that we are in one of the other
five cases.

The definition of l_0 immediately yields its asymptotic order.

  The value l_0 defined in (<ref>) is positive and  satisfies
  
    l_0 =
        Θ()    in ,
    Θ(n^1/3)    in ,
    Θ^-2/3n^3/5   in ,
    Θ(n^3/5)    in ,
    1/2 n^3/5 + Θ^-3/2n^3/5   in .

  Furthermore, in , we have 0<l_0-1/2 n^3/5=Θn^3/5.


In general, l_0 will not be an integer and thus in particular not admissible. Set

    l_1 := ⌈ l_0 ⌉.

Now (<ref>) and <Ref> yield

    l_1 = (1+o(1))ϕ^2/3(2m-n-2l_1)/e^1/32^4/3(n-m+l_1)^2/3 .

From <Ref> we deduce that all l 'close to' l_1 are admissible and use this fact to derive a lower bound on _g^*(n,m).

  Let c>1 be given and suppose that l∈ with l_0/c≤ l ≤ c l_0 and
  
    0 < m_ =
        Θ(n^3/5)    in ,
    Θ^-3/2n^3/5   in .

  Then l is admissible. Furthermore, there exists 
  
    ñ_ = n_ + Om_^2/3

  such that
  
    Σ_(n,m,l) ≥Θ(1)e/2^2lm_^2/3expf_d(ñ_,l)M_(n,m,l).

  In particular, for every δ>0 and n large enough,
 
    _g^*(n,m)≥Θ(1)n^n+1/2e/2^m+2l_1l_1^-3l_1/2ϕ^l_1(n-m+l_1)^2/3(1-δ)^l_1M_(l_1,n,m).


The bound in <Ref> enables us to show that Σ̃_l is negligible.

  For n→∞, we have
  
    n^n+1/2e/2^m Σ̃_l = o_g^*(n,m).





<Ref> implies that the main contribution to _g^*(n,m) is provided by the same
intervals that provide the main contribution to Σ_l. After determining lower bounds for the summands
in (<ref>), our aim is to determine the `optimal' intervals in view of <Ref>. In other
words, we are looking for intervals I_(n) and I_l(n) such that a) the lower bound, summed over
I_(n) and I_l(n), is much larger than the `tail' of the upper bound and b) I_(n) and I_l(n)
are as small as possible. To that end, in the second phase transition, we need an auxiliary result that tells us
that f_d (defined in <Ref>) does not change `too much' if we fix l and change n_ by a 
small fraction.


  Suppose that m(n) lies in , , or . Let positive valued functions h=h(n)=ω(1) and ϵ=ϵ(n)=o(1)
  satisfying hϵ=ω(1) be given. Then for all δ>0, there exists 
  N∈ such that for all n>N, n_ = (1+o(1))n, and h ≤ l ≤n_/h, we have
  
    f_d((1-ϵ)n_,l)-f_d(n_,l)≤δϵ l.



With this auxiliary result, we can now determine the desired intervals I_(n) and I_l(n) that
provide the main contribution to _g^*(n,m).


  There exist constants β_l^+,β_l^-∈^+ and functions 
  η_l^+,η_l^-: (1,2)→^+, and ϑ_l^+,ϑ_l^-→^+ 
   with 
   
    β_l^+>β_l^-,      η_l^+(x)>η_l^-(x),      ϑ_l^+(x)>ϑ_l^-(x)>x/2

  for all x∈ such that the following holds.
 
  For every fixed function h=h(n)=ω(1), the main contribution to (<ref>) is provided by
  l∈ I_l(n) and n_∈ I_^h(n,l), where
  
    I_l(n) =
        { k∈|β_l^-≤ k ≤β_l^+}   in ,
    { k∈|η_l^-(c_)n^1/3≤ k ≤η_l^+(c_)n^1/3}   in ,
    { k∈|β_l^-^-2/3n^3/5≤ k ≤β_l^+^-2/3n^3/5}   in ,
    { k∈|ϑ_l^-(c_)n^3/5≤ k ≤ϑ_l^+(c_)n^3/5}   in ,
    { k∈|β_l^-^-3/2n^3/5≤ k - 1/2 n^3/5≤β_l^+^-3/2n^3/5}   in ,

  and
  
    I_^h(n,l) = { k∈|k-n_≤ h m_^2/3}.







§ INTERNAL STRUCTURE


In the <Ref>, we have determined the main contributions to _g^*(n,m) and
thus, by <Ref>, also the main contributions to _g(n,m). Interpreting
these results in a probabilistic sense, we deduce the typical orders n_,n_ of the  and the core of
G=_g(n,m), respectively, as well as its typical excess (G) and deficiency (G). 
All results in this section are proved in <Ref>.

The , for instance, grows from
order n^2/3 in the first supercritical regime to linear order in the intermediate regime. The number m_ of edges
outside the  is about half the number n_ of vertices outside the .


  Let G=_g(n,m). Then n_, n_, (G), and (G)  lie in the following ranges.
  

  
            

    n_     n^2/3+O_p(n^2/3)     -1n+O_pn^2/3

    n_     Θ n^1/3     Θn^2/3

    (G)     Θ     Θn^1/3

    (G)     0     O_p(1)
  
  

  Furthermore, 
  
    m_ = n_/2+O_p(n_^2/3).



In the second phase transition, the  covers almost all vertices and thus, it is more
convenient to consider the number n_=n-n_ of vertices outside the .


  Let G=_g(n,m). Then n_, n_, (G), and (G)
    lie in the following ranges.
  

    
                  

      n_     n^3/5+O_p^2/3n^2/5     Θn^3/5     Θ^-3/2n^3/5 

      n_     Θ^-1/3n^4/5     Θn^4/5     Θ^1/2n^4/5 

      (G)     Θ^-2/3n^3/5     Θn^3/5     1/2 n^3/5+Θ^-3/2n^3/5 

      (G)     O^-1n^2/5     On^2/5     O^3/2n^2/5
    
  

  Furthermore, we have
  
    n_ = 2(G) -  n^3/5 + O_p2(G) -  n^3/5^2/3

  and
  
    m_ = n_/2+O_p(n_^2/3).



As an immediate corollary of <Ref>, we deduce the typical order of the
kernel of G=_g(n,m).


  The number n_ of vertices and m_=3/2n_+(G) of edges of
  the kernel of G=_g(n,m) lie in the following ranges .
  

  
                        

    n_     Θ()     Θ(n^1/3)     Θ^-2/3n^3/5     Θn^3/5     1/2 n^3/5+Θ^-3/2n^3/5

    (G)     0     O_p(1)     O^-1n^2/5     On^2/5     O^3/2n^2/5
  
  



<Ref> and <Ref> tell us the orders of the , the core, and the kernel.
What we are ultimately looking for, however,
are orders of components. <Ref> cover the case of cubic kernels, which
are precisely the kernels of _g(n,m) in . However, we are not interested in the
properties a kernel has if we pick it uniformly at random from the class of all kernels. We are
rather looking for properties of the kernel of _g(n,m), where the randomness lies
in _g(n,m).
Clearly, we cannot expect the probability distribution on the class of kernels given by this
construction to be uniform.

However, by a double counting argument, we prove that the aforementioned probability distribution does not differ
`too much' from the uniform distribution if we are in  or . From this, we use 
Markov's inequality (<ref>) to deduce that in these regimes, the kernel _G,
the core _G, and the complex part _G of G=_g(n,m) have a component of genus g 
that covers almost all vertices, while all other components are planar. 
Recall that H_i(G') denotes the i-th largest component of a graph G'.
Denote by R(G') the graph G'∖ H_1(G').


  Let G=_g(n,m), where m=m(n) lies in  or .
  
  
  * 
    _G, _G, and _G have the same number k=O_p(1) of components;
  
  * 
    for every i≥2, the probability that _G, _G, and _G
    have at least i components is bounded away both from 0 and 1;
  
  * 
     H_1(_G), H_1(_G), and H_1(_G) have genus g;
  
  * 
     R(_G), R(_G), and R(_G) are planar;
  
  * 
    if _G, _G, and _G have at least i≥ 2 components, then
    
    H_i(_G) = Θ_p(1),
            H_i(_G) = Θ_pn^1/3,
            H_i(_G) = Θ_pn^2/3;

  
  * 
    R(_G)=O_p(1);
  
  * 
    R(_G)=O_p(n^1/3);
  
  * 
    R(_G)=O_p(n^2/3).
  


For the second phase transition, the proof method of <Ref> fails. For these cases, we prove 
the existence of the giant component by different means in <Ref>.

From <Ref>,
we deduce the typical order of the largest components of the , the core, and the kernel of _g(n,m),
respectively.


  For G=_g(n,m), the largest components of the  _G, the core _G, 
  and the kernel _G, respectively, have the following order.

  
            

    H_1(_G)     n^2/3+O_p(n^2/3)     -1n+O_pn^2/3

    H_1(_G)     Θ n^1/3     Θn^2/3

    H_1(_G)     Θ     Θn^1/3
  
















































§ PROOFS OF MAIN RESULTS


In this section, we prove the main results (<Ref>) of this paper,
as well as the structural results from <Ref>.



 §.§ Proof of <Ref>


In , i.e. m=(1+ n^-1/3)n/2 with =o(n^1/3)
and →-∞, the  random graph G(n,m)  is embeddable on  by <Ref>.
Thus, <Ref><ref> follows immediately from <Ref><ref>.


In , i.e. → c_∈, <Ref><ref> implies that
G(n,m) has no complex components with positive probability. Thus, <Ref><ref> 
yields the second statement of <Ref><ref>. By <cit.>, the probability that G(n,m) is 
planar, and thus in particular embeddable on , is larger than the probability that G(n,m) has no complex components. 
Hence the first statement of <Ref><ref> follows as well.


In , i.e. =o(n^1/3) and →∞, by 
<Ref><ref>–<ref> and <Ref>, the  of G=_g(n,m)  has one component that 
has genus g and order n^2/3+O_p(n^2/3), while all other components are planar and 
have order Θ_p(n^2/3). By <Ref><ref> and <ref>,
it remains to show that for each i≥ 1, the  largest non-complex component has order Θ_pn^2/3. By <Ref><ref>
and the fact that m_ = n_/2+O_pn_^2/3, there is a positive probability that
G(n_,m_) has no complex component and therefore the claim follows from
<Ref><ref>.







 §.§ Proof of <Ref>


Let m(n) be a function from the second phase transition, that is, m(n)=(2+ n^-2/5)n/2 
with = (n) = o(n^2/5). Again, we denote the number n-n_ of
vertices outside the  of a given graph G∈_g(n,m) by n_ and the number 
of edges outside the  by m_. We claim that n_-H_1(_G) = O_p(n_). 
In other words, for every δ>0 we need to find a constant c_δ so 
that n_-H_1(_G)≤ c_δ n_ with probability greater than 1-δ 
for sufficiently large n. Fix δ >0 and denote by E_g(n,m) the subclass of 
_g(n,m) of those graphs G for which n_-H_1(_G) > c_δ n_ 
with c_δ := 5/δ. We have to prove that E_g(n,m) < δ_g(n,m) 
for sufficiently large n.
 
Suppose that there exists an infinite set I⊂ such that 
E_g(n,m)≥δ_g(n,m) for all n∈ I. We use double counting 
in order to derive a contradiction from this assumption. Let n∈ I be fixed
and pick a graph G∈E_g(n,m). <Ref> together with the assumption
E_g(n,m)≥δ_g(n,m) yields that

    m_ = m-m_  = n_/2+O_pn_^2/3.

By definition, H_1(_G) < n_-5/δn_. Thus, there is a partition 
(A,B) of the vertices in _G such that each component is contained either in A or in 
B and that A≥B≥5/δn_. Now we perform the following operation. 
We delete one edge from the non-complex components and instead add an edge between A 
and B. The resulting graph is still embeddable on  and thus lies in _g(n,m).
The number of choices for this operation is therefore

    m_A·B
      ≥ (1+o(1))5/4δn_^2n_.

The reverse operation is to delete an edge uv from the  that separates u and v and add an edge outside the 
 (not creating any new complex components). There are less than n_ choices for uv, because any spanning 
tree of a component has to contain all edges of that component that are feasible for uv. Thus, there are less than 
n_^2n_ possibilities for the reverse operation, yielding

    (1+o(1))5/4δn_^2n_E_g(n,m) < n_^2n__g(n,m)

and thus

    E_g(n,m) < (1+o(1))4δ/5_g(n,m)
      < δ_g(n,m)

for sufficiently large n∈ I, a contradiction.

We have thus proved that 
n_-H_1(_G) = O_p(n_), which in turn implies that 
n-H_1(_G) = O_p(n_). <Ref> now follows from <Ref> 
and the trivial fact that n-H_1(_G)≥ n_.









 §.§ Proof of <Ref>


Analogously to the proof of the case  of <Ref>, <Ref> follows from <Ref><ref>,
<Ref><ref>, <Ref>, and <Ref>.




main4

In <ref>, the cases  and  follow directly from <Ref><ref>
and <ref>, respectively, and Stirling's formula, applied to the binomial coefficient
n2m.

For all other regimes, <Ref> provides a lower bound. On the other hand, <Ref> and
<Ref> tell us that the main contribution to _g(n,m) is provided by an interval I_l(n) that is
centred around l_1=⌈ l_0⌉. Moreover, by (<ref>), there exist constants 0<c^-<c^+ such that

    c^-2m-n-2l/(n-m+l)^2/3≤ l ≤ c^+2m-n-2l/(n-m+l)^2/3

for all l∈ I_l(n). The length of I_l(n) is O(l_0). Let l_2∈ I_l(n) be the index that maximises the 
summand. Applying <Ref> and (<ref>), we observe that the resulting upper bound differs from the lower bound from 
<Ref> by a factor of the type exp(O(l_0)). Now <Ref> follows by inserting the values for l_0 from
<Ref> into the lower bound from <Ref>.






 §.§ Proof of <Ref>


The results on the excess and the order of the complex part follow from <Ref>. Observe that
(G) = o(n_) for all regimes and thus <Ref> is applicable, yielding
the order n_ of the core and the deficiency (G). Finally, by <Ref> we
know that

    n_ = 2(n-m+(G))+ O_p(n-m+(G))^2/3

and

    m_ = n-m+(G)+ O_p(n-m+(G))^2/3,

which yields the last statements of <Ref>.



kernelsize

<Ref> follows directly from <Ref> and the values of (G) and (G)
stated in <Ref>.



generalstructure

  Given a fixed kernel , call a subdivision of  good if it is a simple
  graph (and thus a valid core). We first prove that the fraction of good subdivisions
  among all subdivisions of  is bounded away from zero.

  To this end, suppose that  is a kernel with 2l-d vertices and 3l-d
  edges and that we want to subdivide its edges k times (with k≥ 6l-2d) in order to construct a core  with
  k+2l-d vertices. We subdivide  in the following way. First, decide which labels the
  vertices of  should have in ; there are k+2l-d2l-d choices for this.
  Let I be the set of the remaining k labels. We recursively subdivide edges of 
  and assign the smallest remaining label in I to the new vertex. The number of choices increases by one in each recursion step and
  thus we have (k+3l-d-1)_k choices in total. This way, we construct each subdivision precisely
  once. Hence the total number of subdivisions of  is
  
    2l-d+k2l-d(k+3l-d-1)_k .

  In order to give a lower bound on the number of good subdivisions, we change our construction
  slightly by introducing a preliminary step. After choosing the labels for the vertices in ,
  we subdivide each edge of  twice and then choose labels from I for the new vertices;
  there are (k)_6l-2d choices for this. After this step, we proceed as before, with the
  additional rule that an edge may only be subdivided if none of its end vertices is a vertex of
  . Similar to our first construction, there are (k-3l+d-1)_k-6l+2d choices for this
  part of the construction. Every graph obtained by this type of subdivision is simple and no graph
  is constructed more than once. Thus, the total number of good subdivisions is at least
  
    2l-d+k2l-d(k)_6l-2d(k-3l+d-1)_k-6l+2d .

  The fraction of good subdivisions among all subdivisions of  is thus at least
  
    (k)_6l-2d(k-3l+d-1)_k-6l+2d/(k+3l-d-1)_k≥(k-3l+d/k-6l+2d)^-6l+2d(<ref>)≥exp-2(3l-d)^2/k-6l+2d.

  Substituting l=(G), d=(G), and k=n_-3l+d from <Ref>
  (and observing that these values satisfy k≥ 6l-2d ) yields that the fraction of good subdivisions is bounded away from zero.

  To make this more precise, denote by
  (_G) the proportion of subdivisions of _G that lie in 
  _g(n_,n_+l). We have shown that for every δ>0 there exists an ε>0
  such that
  
    1-δ≤(_G)    ≤ 1  in ,
    ε≤(_G)    ≤ 1  with probability at least 1-δ in .

  Recall the construction steps <ref>–<ref>: the core _G is 
  constructed from _G by subdividing edges; the  _G is obtained from _G by attaching rooted trees to all vertices; 
  adding trees and unicyclic components to _G yields G.
  Let X be an event that depends on the choice of ∈_g.
  From the above construction, (<ref>), and the fact that the kernel of G=_g(n,m) has
  a growing number of vertices by <Ref>, we deduce that
  
    ε≤X  holds for =_G/X  holds for =_g(2l-d,3l-d)≤1/ε,

  provided that the denominator is non-zero.

  To prove <ref>, observe that the kernel, the core, and the  of a graph have the 
  same number k of components by construction. <Ref> (for g≥ 1) and
  <cit.> (for g=0) tell us that the cubic kernel _g(2l,3l) has O_p(1) components.
  Thus by (<ref>), we have k=O_p(1) if
  the kernel is cubic, which is the case  in  by <Ref>. In , we
  have (G)=O_p(1). Thus, we apply <Ref> and deduce that k=O_p(1). By analogous
  arguments, we deduce <ref>, <ref>, and the statements about _G from
  <ref>, <ref>, and <ref>.

  The observation that subdividing edges (when constructing _G) and attaching trees (constructing _G) 
  does not change the genus of any component proves the remaining statements of <ref> and <ref>.

  In order to prove <ref>, <ref> and <ref>, let A_ be any fixed component 
  of _G. Denote by A_ and A_ the corresponding components of _G and _G, respectively.
  Observe that
  
  
  * in a random (not necessarily good) subdivision of the kernel,
    the expected number of subdivisions of any given edge e is n_/n_-1;
  
  * if we attach a rooted forest to the core in order to construct the , the
    expected order of the tree attached to any given vertex v is n_/n_.
  
  By <Ref>, we have n_/n_ = Θ(n^1/3) and n_/n_ =
  Θ(n^1/3) . Therefore, (<ref>) and Markov's inequality (<ref>), applied to the 
  random variables A_ and A_, imply that 
  
    A_=O_p(n^1/3)A_    and    A_=O_p(n^1/3)A_

  for every fixed component A_. On the other hand, there are O_p(1) components, which proves <ref> and <ref>.

  It remains to prove the lower bound for _i(_G) and _i(_G) in <ref>.
  For an edge e of _G, denote by X_e the random variable of subdivisions of e. Both the expectation X_e and 
  the variance σ^2 have order Θ(n^1/3). Therefore, Chebyshev's inequality (<ref>) implies that 
  
    X_e ≤1/2X_e = O(n^-1/3).

  Thus, for a fixed component A_≠_1(_G), a union bound over all O_p(1) edges in A_ 
  proves that A_=Θ_p(n^1/3)A_. By another union bound, this is true for all O_p(1) components
  (apart from _1(_G)), proving _i(_G)=Θ_p(n^1/3) for all i≥ 2.

  Similarly, for a vertex v of _G, denote by Y_v the number of vertices in the tree attached to v when we construct
  _G. Again, both the expectation and the variance have order Θ(n^1/3) and we deduce
  
    Y_v ≤1/2Y_v = O(n^-1/3)

  from Chebyshev's inequality (<ref>). This implies that, for any given δ>0, there exists an ε>0 such that with probability at
  least 1-δ, every component A_ contains at least ε n^1/3 vertices v with Y_v > ε n^1/3, which yields
  A_≥ε^2n^2/3. This proves <ref> and thus finishes the proof of <Ref>.

compsizesfirst

<Ref> is an immediate consequence of <Ref>.








§ PROOFS OF AUXILIARY RESULTS


In this section we prove all results from <Ref>.




 §.§ Proof of <Ref>


It remains to prove <ref>. From Lemma 3, (10.11), and (10.12) in <cit.>,
we deduce that

    ρ(n,m)= 2^2m-ne^nm!n!/(n-m)!n^2m2π i∮√(1-z)expn k(z) z/z,

where the contour of the integral is a closed curve around the origin with z≤1 and

    k(z)=z-1-m/nlog(z)+1-m/nlog(2-z).

We use the contour consisting of a) the line segment from 1 to i, b) the semicircle of radius one 
with negative real value, and c) the line segment from -i to 1.
Along this contour we have exp(k(z))≤ 1 and thus 

    ρ(n,m)   ≤2^2m-ne^nm!n!/(n-m)!n^2m2π∮√(1-z)/z z
       (<ref>)≤e^2(π+2√(2))/√(2)π^3/22/e^2m-nm^m+1/2n^n-2m+1/2/(n-m)^n-m+1/2 ,

proving the lemma.






cubic:lc-size

We abbreviate the class of cubic kernels embeddable on  by A_g and the subclass of 
A_g of connected cubic kernels by B_g. Clearly, every graph in A_g has an even number of vertices.
We first prove (<ref>).


By <Ref> there exist positive constants a_g^-,a_g^+,b_g^-,b_g^+ such that for all l 

    a_g^-≤A_g(2l)/(2l)^5g/2-7/2γ_^2l(2l)!≤ a_g^+
          and    
      b_g^-≤B_g(2l)/(2l)^5g/2-7/2γ_^2l(2l)!≤ b_g^+.


By <Ref>, the elements of A_g(2l)  have a unique non-planar component. 
Therefore the probability that (G) has exactly 2i vertices is given by 

    (G)= 2i=(1+o(1))2l2iB_g2l-2i·A_02i/A_g2l

and we can therefore conclude that (<ref>) holds.

It remains to show that for every δ>0 there exists a constant c_δ such that 
(G)>2c_δ<δ for sufficiently large l.
By <Ref>, (<ref>), and the fact that g≥1, we have for any c_δ∈_>0

    (G)>2c_δ≤ (1+o(1))∑_i=c_δ+1^l-3 c_g^+ i^-7/21-i/l^-1.

The summand (as a function in i) has a unique minimum at i=7l/9. Therefore,

    (G)≥ 2c_δ   ≤ (1+o(1))c_g^+∫_c_δ^l-2x^-7/21-x/l^-1 x
       = 2/5+o(1)c_g^+c_δ^-5/2(1+O(l^-1/2)) < δ

for c_δ and l large enough, as desired.



kernelpumping

For ∈_g2l,3l and ∈_g2l-d,3l-d, we say that 
 contracts to  if for each vertex in  with label 
i∈{2l-d+1,…,2l} we can choose an edge e_i={i,v_i} so that contracting these edges results in 
 (the contracted vertices obtain the smaller of the two labels). We say that 
e_2l-d+1,…,e_2l are the contracted edges. Denote by _g^Δ=4(2l-d,3l-d) the subclass
of _g(2l-d,3l-d) consisting of multigraphs with maximum degree four. 
We say that a contraction of  to  has degree four if ∈_g^Δ=4(2l-d,3l-d).

If  contracts to , then
the compensation factor defined in (<ref>) satisfies

    w() ≤ w() ≤ 6^d w().


Each ∈_g(2l,3l) contracts in at most 3^d ways, because  is 
cubic and hence there are at most 3^d choices for the edges e_2l-d+1,…,e_2l.
Vice versa, we claim that every fixed ∈_g2l-d,3l-d
is obtained by at least d!2^-d different contractions from graphs in _g2l,3l. 
By recursively splitting vertices of  of degree at least four into two new adjacent vertices of 
degree at least three each, not increasing the genus throughout the process, we obtain a weighted multigraph 
∈_g2l,3l that contracts to . The new vertices can be labelled in d! ways,
of which at least 2^-dd! result in distinct multigraphs in _g2l,3l.
Together with (<ref>), this proves the upper bound 

    _g(2l-d,3l-d)/_g(2l,3l)≤6^d/d!.

The corresponding bound for _g(2l-d,3l-d;P_i) follows analogously observing that
the two constructions above do neither change the number of components nor increase the genus of any component.

For the lower bound, we claim that the elements of _g(2l,3l) have at least 6^-d contractions of degree four on average.
Indeed, first observe that ∈_g2l,3l contracts to ∈_g^Δ=4(2l-d,3l-d) 
if and only if the contracted edges form a matching in . By choosing the edges of the matching
recursively, we see that  contains at least 2^dd!^-1∏_j=0^d-1(2l-6j) matchings of size d.

Denote by A() the class of all weighted multigraphs that are isomorphic to . 
If we choose A∈A() and a matching M of size d in A uniformly at random, then the 
probability that every edge in M has precisely one end vertex with label in {2l-d+1,…,2l} is 
2^d/2ld. Therefore, the average number of contractions of degree four of graphs in A() is at least

    ∏_j=0^d-1(2l-6j)/2^dd!·2^d/2ld≥2l-6d/2l-d^d ≥ 6^-d,

where the last inequality uses the fact that d≤2l-d/6. The fact that the classes A() partition
_g(2l,3l) proves that ∈_g(2l,3l) has at least 6^-d contractions of degree four
on average.

Vice versa, let ∈_g^Δ=42l-d,3l-d. By recursively splitting the d vertices of 
degree four in , we see that  can be obtained by at most 42^dd!=6^dd! contractions 
of degree four. Together with (<ref>), we deduce that

    _g(2l-d,3l-d)/_g(2l,3l)≥1/216^dd!.

The corresponding bound for _g(2l-d,3l-d;P_i) follows analogously.





 §.§ Remark


Observe that the proof of <Ref> applies to any class F of (multi-) graphs that is a) closed under taking minors
and b) weakly addable, that is, if G is obtained by adding an edge between two distinct components of F∈F,
then also G∈F. For more details, see <Ref>.


binsandballs

  Let ∈_g(2l-d,3l-d).
  We subdivide the edges of  by inserting n_-2l+d vertices and then assign labels to these new vertices
  in one of (n_-2l+d)! possible ways so as to obtain a core with n_ vertices.

  Call a distribution of n_-2l+d new vertices to the edges of  feasible if
  the resulting graph has no loops or multiple edges. The number
  n_+l-13l-d-1 of all distributions is clearly an upper
  bound for the number of feasible distributions. On the other 
  hand, a distribution is feasible if and only if each loop is subdivided at least twice and for every multiple
  edge, at most one of its edges is not subdivided. Denote by s_ the minimal number of times that
  we need to subdivide the edges of  in order to obtain a simple graph. Then
  n_+l-s_-13l-d-1 is a lower bound on the number of feasible
  distributions.
  
  By construction, s_≤ 2(3l-d) ≤ 6l and we thus deduce that
  
    min_-5≤ν≤1(n_-2l+d)!n_+ν l -13l-d-1≤φ_n_,l,d≤
        (n_-2l+d)!n_+l -13l-d-1.

  Now the lemma follows from the intermediate value theorem and the fact that the function
  xk for fixed k∈ is continuous for x∈.



complex:bounds

<Ref> follows directly from (<ref>), <Ref>,
the intermediate value theorem, and the fact that x^d is continuous.



lem:SigmaC

We first derive an upper bound for Σ_, as well as the main contribution to this upper bound.
We substitute n_=n_+r (recall that n_=√(n_(3l-d))).
Applying (<ref>) to (<ref>), and then using (<ref>) and (<ref>)
we deduce that

    Σ_≤Σ_^+ := ∑_rexp(-r^2/2n_+rA_1+A_2),

where

    A_1=   1-2n_/2n_+3l-d-1/n_+(3l-d-1)(3l-d-2)/2(n_+ l-1)^2 ,
    
     A_2=   (3l-d)logn_-1/2+√(3l-d/4n_)+(3l-d-1)l-1/n_-3l-d-2/2(n_+l-1).


Evaluating the `Gaussian' sum in (<ref>) we obtain

    Σ_^+ ≤√(2π n_)expA_2+n_ A_1^2/2.

The existence of the constants a_^+,b_^+ from <ref> now follows from

    exp(A_2) ≤n_(3l-d)/e^(3l-d)/2expO√(l^3/n_)

and the observation that n_ A_1^2 = Ol^2/n_, which is O√(l^3/n_), because l=O(n_).

In order to prove <ref>, suppose that 7/2d≤ l≤ϵ n_ = o(n_); then also l=o(n_). In (<ref>),
we set n_=n_-ν l+1+s. If we let the parameter s=r+ν l-1 take only values for which n_∈ I_^δ(n_,l,d)
with fixed 0<δ<1/2, then

    Σ_≥∑_s (n_)_n_/n_^n_n_n_+s_3l-d-1.

The interval I_^δ(n_,l,d) has length 2δn_ > 2δ√(n_) and hence
we can choose for s an interval I_s of length δ√(n_) in which s<δn_ holds. 

We use (<ref>) for both falling factorials 
and obtain

    Σ_≥n_^3l-d∑_s 1+s/n_^3l-d-11+s+1+ν l/n_expB_1,

where

    B_1 = -n_-ν l+1+s^2/2(n_-n_+ν l-1-s)-(3l-d-1)^2/2(n_-3l+d+1+s).

Observe that 1+s/n_=Θ(1) and 1+s+1+ν l/n_=Θ(1). Using (<ref>), we deduce that

    1+s/n_^3l-dexpB_1≥exp-3l-d/2 + O√(l^3/n_) + O(1).

Now (<ref>) and (<ref>), together with I_s=δ√(n_) prove <ref>.



It remains to prove <ref>. First observe that 
if we take the sum (<ref>) over all r∈ and normalise, we obtain a normally distributed random
variable X with mean n_ A_1 = O(l) and variance n_. Applying the Chernoff bound (<ref>) to X, we deduce

    ∑_r-n_ A_1 > δ/2n_exp-r^2/2n_+rA_1+A_2≤
      2exp-δ^23l-d/8Σ_^+.

Note that r-n_ A_1<δ/2n_ implies that n_∈ I_^δ(n_,l,d)
for sufficiently large n_ and l=o(n_), because then n_ A_1=o(n_). Therefore,

    ∑_n_∉ I_^δ(n_)_n_/n_^n_n_(n_+ν l-1)_3l-d-1/∑_n_∈ I_^δ(n_)_n_/n_^n_n_(n_+ν l-1)_3l-d-1≤exp-δ^23l-d/8+Θ(1)+Θ√(l^3/n_).

Now δ^23l-d/8 = Θ(l), √(l^3/n_)=o(l), and the fact that l→∞ finish the proof of <ref>.



lem:SigmaD

We start by proving <ref>. We apply

    (3l-d)^(3l-d+2)/2/(3l-d)!(<ref>)≤e^3l-d/√(2π)(3l-d)^-3l-d-1/2(<ref>)≤e^3l-d/2/√(2π)(3l)^-3l-d-1/2

and <Ref> to deduce that

    Σ_d    ≤expa_^++b_^+√(l^3/n_)/√(2π)e^3l(3l)^-3l-1/2∑_d=0^2l2ld108l/n_^d/2,

proving <ref> with a_d^+=a_^+-1/2log(2π) and b_d^+=b_^++2√(108).

For <ref>, first note that we have a lower bound for Σ_d if we restrict the sum (<ref>) to 
0≤ d≤⌊2l/7⌋. By analogous arguments as for the upper bound, we deduce that

    Σ_d≥expa_^-+b_^-√(l^3/n_)/ee^3l(3l)^-3l-1/2∑_d=0^2l/72ld3l/216^2en_^d/2.

The sum above can be extended to a sum Y=∑_d=0^2l2ldy^d with y=o(1). Normalising this sum results in
a binomially distributed random variable X=Bi(2l,p) with p=y/1+y and X=Θ√(l^3/n_). 
If X→0, then the main contribution to Y is provided by the term with d=0. Otherwise, the Chernoff bound 
(<ref>) yields that the main contribution to X—and thus also to Y—is provided by an interval contained in the range 0≤ d≤2l/7.
Thus, with (<ref>) we deduce that

    Σ_d    ≥expa_^-+b_^-√(l^3/n_)/e(1+o(1))e^3l(3l)^-3l-1/2exp√(3)/108√(e)√(l^3/n_)-√(3)l^2/216√(e)n_.

Observing that l^2/n_=o(√(l^3/n_)), we have thus proved <ref> for any choice of
a_d^-<a_^–1 and b_d^-<b_^-+√(3)/108√(e).

In order to prove <ref>, it remains to show that the tail of Σ_d has smaller order than its total value, that is

    e^b_d^+√(l^3/n_)∑_d∉I_d2ld6 √(3l)/√(n_)^d=oe^b_d^-√(l^3/n_).

Write

    Z = ∑_d=0^2l2ld6 √(3l)/√(n_)^d.

For √(l^3/n_)→ 0, the exponential terms in (<ref>) are both 1+o(1) and the sum on the left hand side is
o(1), because its range does not include the main contribution of the binomial sum Z, which is located at d=0.

If √(l^3/n_)→ c∈^+, then both exponential terms in (<ref>) are Θ(1).
For any fixed h=h(n_)=ω(1), we deduce from (<ref>), applied to the normalised sum Z,

    ∑_d>h2ld6 √(3l)/√(n_)^d ≤exp-ch

for some constant c>0, which proves (<ref>).

Finally, if √(l^3/n_)→∞, we can choose β_d^+ sufficiently large so that 
(<ref>) yields

    ∑_d>β_d^+√(l^3/n_)2ld6 √(3l)/√(n_)^d ≤exp-(b_d^+-b_d^-+1)√(l^3/n_),

which proves (<ref>) also in this last case.



coredeficiency

The typical range for d(G) follows directly from <Ref><ref>. Substituting
this deficiency in the formulas for the main contribution for n_ from <Ref> yields the 
typical order of the core.



complex:number

This follows directly from (<ref>) and (<ref>).



lem:exceptional

We prove <Ref> using the lower bound on _g^*(n,m) from <Ref>.
It is important to note that vice versa, the proof of <Ref> does not rely on <Ref>.

Suppose first n_=0, i.e. the complex part is empty and the graph only consists of trees and unicyclic 
components. In this case <Ref><ref> implies that the number of such graphs satisfies

    (n,m)≤Θ(1)n^m2^m-ne^n-m^2/n.

Comparing this to the lower bound from <Ref> shows that

    (n,m)/_g^*(n,m)≤ e^-l_1 = o(1).


The remaining case is m_=0, i.e.m=n_+l ≥ n_+1 (recall that n_>0 implies l>0). The number of such graphs is given by

    ∑_n_≤ m-1nn__g(n_,m).

The case n_=m-1 in the sum above is of smaller order than the lower bound for _g^*(n,m)
from <Ref>. For every n_<m-1, <Ref> implies that

    nn__g(n_,m)/nn__g(n_,m-1)n-n_2
      = Θ(1)n_^3/2(m-n_)^-3/2(n-n_)^-2.

In  and , the right hand side of (<ref>) is O(n^-1/2).
Observing that the denominator is a summand of
_g^*(n,m), we deduce that

    ∑_n_≤ m-1nn__g(n_,m) = o_g^*(n,m)    in  and .

Suppose now that we are in the second phase transition and write I_l=[p_l,q_l]. For n_< m-p_l, the right hand side of (<ref>) is o(1)
and thus

    ∑_n_< m-p_lnn__g(n_,m) = o_g^*(n,m).

For n_≥ m-p_l, or equivalently l ≤ p_l, we have

    ∑_n_ = m-p_l^m-2nn__g(n_,m-1)n-n_2≤exp(-f(n))_g^*(n,m),

where f=ω(log n) is a positive valued function. From this, we deduce that

    ∑_n_ = m-p_l^m-2nn__g(n_,m)(<ref>)≤Θn^3/2exp(-f(n))_g^*(n,m) = o_g^*(n,m).

This concludes the proof of <Ref>.




lem:SigmaQ

In Σ_=∑_n_ρψ (see (<ref>) for the definition of ψ), we substitute 
n_ = n_+r.
We then have n_ = n-n_ = n_-r and
m_ = m-n_-l = m_-r.

With this substitution, we obtain

    ψ=2/e^n_+r(n_+r)^3l/2-1(n_-r)^-r-1/2(m_-r)^-m_+r-1/2expf_d.

Because n_,l are admissible, we have l = O(n_) and thus

    f_d ≤ a_d^++b_d^+√(l^3/n_) = O(l).

If in addition (<ref>) holds, then l=on_ and thus, for every fixed
h(n)=ω(1),

    f_d ≤ a_d^+ + o(1) l,

whenever r ≥ -n_+hl.
In either case, we distinguish whether r>0 or r≤0.

Let Σ_r>0 be the part of Σ_ consisting of the summands with r>0.
We bound ρ(n_,m_) from above by 1. Additionally we claim that

    2/e^r(n_-r)^-r(m_-r)^-m_+r < m_^-m_exp-r^3/24m_^2.

Indeed, for r≥0, the quotient of the two sides in (<ref>) has a unique maximum at r=0, where we have equality.
Furthermore, there exists a constant c>0 with

    (n_-r)^-1/2(m_-r)^-1/2≤ cm_^-1expr^3/216m_^2.

Now (<ref>), (<ref>), and (<ref>) yield

    Σ_r>0≤2/e^n_m_^-m_-1expO(l)∑_r (n_+r)^3l/2-1exp-r^3/27m_^2.

If in addition (<ref>) holds, we can replace exp(O(l)) by (1+o(1))^l.
The summand above is maximised at the (not necessarily integral) unique positive solution r_0 of

    r_0^3+r_0^2n_=9m_^23l/2-1.


Suppose first that (<ref>) holds, that is,
n_^3≥ 9m_^23l/2-1. Then 

    1/2√(9m_^23l/2-1/n_)≤ r_0≤√(9m_^23l/2-1/n_)

and thus

    (n_+r_0)^3l/2-1exp-r_0^3/27m_^2   (<ref>)≤n_^3l/2-1expr_03l/2-1/n_-r_0^3/27m_^2
       (<ref>),(<ref>)≤n_^3l/2-1expO(l).

Summing over 1≤ r≤m_-1, we deduce that

    Σ_r>0≤2/e^n_n_^3l/2-1m_^-m_expO(l),

which proves (<ref>) for Σ_r>0 if (<ref>) holds.
If the stronger condition (<ref>) is satisfied, the factor expO(l) improves to expO√(ϵ) l=expo(1) l,
proving (<ref>) for Σ_r>0.

Now consider the case n_^3<9m_^23l/2-1. Then

    1/2√(9m_^23l/2-1)≤ r_0≤ 2√(9m_^23l/2-1)

and hence

    (n_+r_0)^3l/2-1exp-r_0^3/27m_^2≤
      (3r_0)^3l/2-1expO(l).

Summing over less than m_ values for r, we deduce that

    Σ_r>0≤2/e^n_r_0^3l/2-1m_^-m_expO(l).

Together with (<ref>), this proves (<ref>) for Σ_r>0 in the case that (<ref>) is violated. 

Finally, consider the part Σ_r≤0 of Σ_ consisting of the summands with r≤0.
Observe that -n_+1≤ r≤0; in particular, the case r≤ 0 only occurs if n_>0. We use <Ref><ref> as 
an upper bound for ρ=ρ(n_-r,m_-r) to deduce

    ρψ≤ c2/e^n_(n_+r)^3l/2-1m_^-m_-1/2exp(f_d).

We bound the factor exp(f_d) by (<ref>).
Furthermore, (n_+r)^3l/2-1≤n_^3l/2-1, because r≤ 0. 
Summing over r, we deduce that

    Σ_r≤0≤ c2/e^n_n_^3l/2m_^-m_-1/2exp(O(l)).

This proves (<ref>) for Σ_r≤0, independent of whether (<ref>) is satisfied.

Finally, suppose that (<ref>) holds. Then in (<ref>), we bound the factor exp(f_d) by
(<ref>) for r≥ r_1 := -n_+hl and deduce by analogous arguments as above that

    ∑_r=r_1^0ρψ≤Θ(1)2/e^n_n_^3l/2m_^-m_-1/2(1+o(1))^l.

For r<r_1, observe that Euler's formula yields r ≥ r_2 := -n_+Θ(l). In this range, the summand
ρψ is maximised at the upper bound r=r_1-1; this yields

    ∑_r=r_2^r_1-1ρψ≤Θ(1)2/e^n_hl^3l/2m_^-m_-1/2(1+o(1))^l.

If we choose h to be growing slowly enough so that hl = o(n_), then this proves (<ref>) for
Σ_r<0.

The trivial observation Σ_ = Σ_r>0+Σ_r≤0 finishes the proof.





lem:SigmaQ:small

Like in the proof of <Ref>, we distinguish the cases r>0 and r≤0 as well as
whether (<ref>) holds or not.

First consider Σ_r>0 when (<ref>) holds. Then (<ref>) implies r_0≤n_, which yields

    ∑_r=1^n_n_+r^3l/2-1exp-r^3/27m_^2   ≤n_^3l/21+r_0/n_^3l/2-1exp-r_0^3/27m_^2
       ≤n_^3l/2exp(O(l)).

The sum over the remaining values for r is bounded by the integral

    ∫_n_^∞2r^3l/2-1exp-r^3/27m_^2 r
      ≤m_^lΓl/2exp(O(l))
      = m_^ll^l/2exp(O(l)).

Now (<ref>), (<ref>), and the fact
that n_ = 2m-n-2l <  n^2/3 prove (<ref>) for Σ_r>0.

If (<ref>) is violated, we split Σ_r>0 into the sums for 1≤ r≤ r_0 and r_0<r.
Observe that (<ref>) implies n_<2r_0. Thus, the sum for 1≤ r≤ r_0 is smaller than
m_^ll^l/2exp(O(l)), while the sum for r_0<r is bounded by the integral

    ∫_r_0^∞3r^3l/2-1exp-r^3/27m_^2 r
      ≤m_^ll^l/2exp(O(l)) < m_^ll^l/2-1/3exp(O(l)).

Now (<ref>) for Σ_r>0 follows from (<ref>)
and the trivial fact that m_ = O(n).

For r≤0, observe that m_ = n_/2-r/2. Furthermore, we have n_≤n_ = O( n^2/3) and thus

    r = O( n^2/3)
          and    
      n_ = (1+o(1))n.

By the assumption = o(n^1/12), <Ref><ref> applies to
ρ(n_,m_) and summing over -n_+1≤ r≤ 0 yields

    Σ_r≤0≤ c2/e^n_n_^3l/2n_^-1/2m_^-m_-1/2exp(O(l)).

Now (<ref>) follows for Σ_r≤0 analogously to the proof of <Ref>, with
the additional fact n_ = O( n^2/3).






sizesl0

By (<ref>), l_0 is positive.
We prove the order of l_0 separately for each of the five regimes.

: In this regime, we have

    l_0=ϕ^2/3( n^2/3-2l_0)/e^1/32^4/3n/2- n^2/3+l_0^2/3.

The denominator is of order Θ(n^2/3). Thus, in order for the equality to be true, the numerator must 
be of order n^2/3 and thus l_0=Θ().

: Here, the denominator is still of order n^2/3 and 
the numerator is of order Θ(n) and thus l_0=Θ(n^1/3).

: The numerator is of order Θ(n) and thus

    l_0=Θ(n)/(l_0-1/2 n^3/5)^2/3.

If l_0=Ω( n^3/5), then we have
l_0=Θn/l_0^2/3 and thus l_0=Θ(n^3/5)=o( n^3/5), a contradiction.
Therefore, l_0=o( n^3/5) and 

    l_0=Θn/( n^3/5)^2/3=Θ^-2/3n^3/5.


: The numerator has order Θ(n). For the 
 denominator we have a contradiction similar to the previous case if l_0 is not Θ(n^3/5). 
 Furthermore, the denominator has order Θn^3/5.

: The numerator is Θ(n) and we obtain a contradiction if there is no cancellation 
 in the denominator. Thus we set l_0=1/2 n^3/5+r with r=o( n^3/5) and deduce that 
r=Θ^-3/2n^3/5.





nQandl:lower

By <Ref>, we have 0<l=o(n_) and 0<n_<n. Thus, n_ and
m_ are also positive. Therefore, we have
_g(n_,n_+l) ≠∅ and (n_,m_)
≠∅, showing that the given value l and n_ = n_ are admissible. Recall that

    Σ_ = ∑_n_ρ(n_,m_)ψ(n_,l).

Observe that (at least) all n_ with n_≤ n_≤n_ + m_ -1
are admissible in this sum. For each such n_, we have m_≤n_/2 and thus
<Ref><ref> yields

    Σ_≥Θ(1)∑_n_=n_^n_+m_-1ψ(n_,l).

Set n_ = n_ + r. There exists a c>0 such that

    ψ(n_+r,l) ≥2/e^n_n_+r^3l/2-1m_^-m_-1expf_d-r^3/12m_^2

holds for 0≤ r≤ cm_. The factor n_+r^3l/2-1exp-r^3/12m_^2
is increasing until the unique positive solution r_0 of

    r_0^3+r_0^2n_=4m_^23l/2-1.

The assumptions on the size of l imply that l
satisfies (<ref>), which in turn yields r_0=Θm_^2/3. Therefore, for 1≤ r≤ r_0, we have

    ψ(n_+r,l) ≥2/e^n_n_^3l/2-1m_^-m_-1expf_d(n_+r,l)-1/12m_^2.

Let ñ_ = n_+r be the value that minimises
f_d(n_+r,l) for 1≤ r≤ r_0; then ñ_ = n_+O(m_^2/3), since
r ≤ r_0. This proves the 
lower bound for Σ_. The lower bound for _g^*(n,m) follows directly 
from (<ref>), the bound for Σ_, and the fact that l_1 is admissible.





lem:caseB

First observe that there exists l_b>0 such that (<ref>) is violated precisely when l≥ l_b. In the
first supercritical regime, we have l_b=Θ^3, in all other regimes l_b=Θ(n).

By <Ref>, we have

    Σ̃_l≤∑_l n^3/2 l^-l+5g/2-10/3(n-m+l)^m-n-5/3expO(l),

where the sum is taken over all l≥ l_b. The sum on the right hand side is bounded from above by
a geometric sum ∑_lexp-cl with c>0 and thus

    Σ̃_l≤ (1+o(1)) n^3/2 l_b^-l_b+5g/2-10/3(n-m+l_b)^m-n-5/3expO(l_b).

Comparing this with the lower bound for _g^*(n,m) from <Ref> and implementing
(<ref>), we deduce that

    n^n+1/2e/2^mΣ̃_l/_g^*(n,m)≤2m-n-2l_1n^1/6l_b^-l_b+5g/2-10/3n-m+l_b/n-m+l_1^m-nexpO(l_b).

The right hand side is o(1), unless we are in the first supercritical regime and  (and thus also
l_b) is too small for the term l_b^-l_b to compensate the polynomial terms in n. For this to be the case,
we would in particular have =on^1/12. For such , we have the stronger upper bound 
for Σ̃_l provided by <Ref>, which is smaller than the one from <Ref> by a
factor of ^-1n^5/6. Thus, for these , we have

    n^n+1/2e/2^mΣ̃_l/_g^*(n,m)   ≤2m-n-2l_1n^-2/3l_b^-l_b+5g/2-10/3n-m+l_b/n-m+l_1^m-nexpO(l_b)
       ≤^2l_b^-l_bexpO(l_b),

which is o(1), because l_b=Θ^3.





lem:boundfd

We first show that for d=o(l) we have

    f_(d,(1-ϵ)n_,l)-f_(n_,l,d) = o(ϵ l).

By (<ref>), we have

    Σ_(d,(1-ϵ)n_,l)/Σ_(n_,l,d)=(1-ϵ)^3l-d+1/2expf_(d,(1-ϵ)n_,l)-f_(n_,l,d).


We can also compare the summands of the two terms Σ_(d,(1-ϵ)n_,l) and 
Σ_(n_,l,d) separately. Denote the summands by

    s(n_,d,n_,l) = (n_)_n_/n_^n_n_(n_+ν l-1)_3l-d-1 .

Then we have for 1≤ n_ = o(n_)

    s(n_,d,(1-ϵ)n_,l)/s(n_,d,n_,l)
          =(1-ϵ)n_n_/(1-ϵ)^n_n_n_
       (<ref>)=Θ(1)1+ϵ n_/(1-ϵ)n_-n_^(1-ϵ)n_-n_1-n_/n_^ϵ n_
       (<ref>)=Θ(1)exp-(1+o(1))ϵ n_^2/2n_.

There exists an interval I that contains the ranges of the main contribution to both Σ_(n_,l,d) 
and Σ_(d,(1-ϵ)n_,l), such that n_=(1+o(1))√(n_(3l-d)), and thus in particular n_ = o(n_), 
for all n_∈ I. Then for n_∈ I and d=o(l),

    s(n_,d,(1-ϵ)n_,l)/s(n_,d,n_,l) = Θ(1)exp-3/2+o(1)ϵ l.

Summing over n_∈ I, we deduce that

    Σ_(d,(1-ϵ)n_,l)
      = Θ(1)exp-3/2+o(1)ϵ lΣ_(n_,l,d).

Combining this with (<ref>) and the condition ϵ l=ω(1) yields (<ref>).

<Ref> yields

    Σ_d((1-ϵ)n_,l)/Σ_d(n_,l)=expf_d((1-ϵ)n_,l)-f_d(n_,l).

Suppose that J is an interval that contains the ranges of the main contributions to both Σ_d(n_,l) and
Σ_d((1-ϵ)n_,l), such that d≤ d_0=o(l) for all d∈ J. Denote the summands of Σ_d(n_,l) by

    s_d(n_,l) = 2ld(3l-d)^(3l-d+2)/2e^d/2τ^d/(3l-d)!n_^d/2exp(f_(n_,l,d)).

Recall that τ=τ(d,l) does not depend on n_. With 
(<ref>), we have

    s_d((1-ϵ)n_,l)/s_d(n_,l)=(1-ϵ)^-d/2expo(ϵ l)

for d∈ J. Summing over J and comparing with (<ref>) proves the lemma.


nQandl

Let us write I_l(n)=[p_l(n),q_l(n)] and I_^h(n,l) = [p_(n,l),q_(n,l)]. Without loss of
generality p_l<l_1<q_l.
We first prove that the main contribution with respect to l is provided by l∈ I_l(n). To that
end, we bound the tail of the sum (the part with l∉ I_l(n)) from above and prove that this upper bound
has smaller order than the lower bound from <Ref>.

Observe that for l∈ I_l(n), we have

    lm_^2/3/n_ = Θ(1).


For this proof, let s_l(n,m) be the summand of the sum Σ_l, i.e. Σ_l=∑_l s_l(n,m), and 
s_(n,m,l) be the summand of Σ_=∑_n_s_(n,m,l). We need to show
that

    T := n^n+1/2e/2^m∑_l∉I_l(n)s_l(n,m) = o_g^*(n,m).



By <Ref>, we may take our sum only over l that satisfy (<ref>). 
If l_2 denotes the index where s_l(n,m) takes its maximal value outside I_l(n), then

    ∑_l∉I_l(n)s_l(n,m) ≤ n  s_l_2(n,m).

In , (<ref>) is violated for all l≥ l_b = Θ(^3) and thus we have the stronger bound

    ∑_l∉I_l(n)s_l(n,m) ≤Θ(^3) s_l_2(n,m).

By <Ref>, there exists a constant α>1 such that

    s_l(n,m) ≤ n^3/22/e^2m-nM(l,n,m;α),

where

    M(l,n,m;α) = l^-3l/2e^2ϕ/4^l2m-n+2l^3l/2-1n-m+l^m-n-l-1α^l.

By choosing β_l^- (respectively η_l^- or ϑ_l^-) small enough and β_l^+ (respectively η_l^+ or 
ϑ_l^+) large enough, we may assume that M(l,n,m;α) is strictly increasing (with respect to l) for l≤ p_l and
strictly decreasing for l≥ q_l. For l≤ p_l, (<ref>) is satisfied and thus (<ref>) holds for every
α=1+δ, where δ>0 is any given constant. Thus,

    s_l_2(n,m) ≤ n^3/22/e^2m-nmax{M(p_l,n,m;1+δ),M(q_l,n,m;α)}.

In , when =on^1/12, <Ref> together with analogous arguments gives us an upper bound

    s_l_2(n,m) ≤ n^2/32/e^2m-nmax{M(p_l,n,m;α),M(q_l,n,m;α)}.


If m is such that (<ref>) applies and if the maximum in (<ref>) is M(q_l,n,m;α), 
then (<ref>) and (<ref>) yield (for large enough β_l^+)

    T/_g^*(n,m)≤^4 e^-l_1,

which is o(1) by <Ref> and the fact that →∞. If (<ref>) does not apply and
the maximum in (<ref>) is M(q_l,n,m,α), then (<ref>), (<ref>), and <Ref> imply that
if we choose β_l^+, η_l^+, or ϑ_l^+ large enough, respectively, then

    T/_g^*(n,m)≤
      n^5/2 e^-l_1,

which is o(1).

If the maximum in (<ref>) or (<ref>) is M(p_l,n,m,1+δ) or M(p_l,n,m,α), respectively, then analogous 
considerations show that we can choose β_l^-, η_l^-, and ϑ_l^- so that for every m=m(n) there exists a constant c>0 such that

    T/_g^*(n,m)≤^4 exp-cl_1   in  for =o(n^1/12),
    
        n^5/2exp-c^-3/2n^3/5   in ,
    
        n^5/2exp-cl_1   otherwise.

In  and , the fact that we have α=1+δ is essential for deducing the above bound. In all regimes—using
that =o(log n)^-2/3n^3/5 in —we deduce that
this upper bound is o(1).
This proves that the main contribution to Σ_l is indeed provided by l∈ I_l(n).

It remains to prove that for each l∈ I_l(n), the main contribution to Σ_ is provided by n_∈
I_^h(n,m,l). We substitute n_=n_+r.

First consider the case n_<p_ = n_ - hm_^2/3, i.e. r< -hm_^2/3.
We shall split the sum into the three parts -vm_^2/3≤ r ≤ -hm_^2/3, -wm_^2/3≤
r ≤ -vm_^2/3, and r≤-wm_^2/3, where

    v := m_^1/24    and    
      w :=
      ^1/2   in ,
    
        lm_^-2/9   otherwise.

Observe that the interval -wm_^2/3≤ r ≤ -vm_^2/3 is empty in  if
< m_^1/12. Furthermore,

    w = ω√(l^3/n_)    and    
      w = on_/m_^2/3(<ref>)= o(l).


By (<ref>) and <Ref>, in each of the three intervals,

    ∑ρψ/Σ_(n,m,l)≤Θ(1)m_^-1/6∑ s_r(n,m,l)

with

    s_r(n,m,l) = 1+r/n_^3l/2-1expf_d(n_+r,l)-f_d(ñ_,l).


Recall that for (<ref>), <Ref><ref> was used to bound ρ.
Observe that for -vm_^2/3≤ r ≤ -hm_^2/3, <Ref><ref> is 
applicable and thus (<ref>) holds with a factor of m_^-2/3 instead of m_^-1/6.
Furthermore, we claim that f_d(n_+r,l)-f_d(ñ_,l) = orl/n_. Indeed, in 
 and , the left hand side is O(1) and the claim follows by observing that rl/n_=Ω(h) by (<ref>). 
In the second phase transition, 
such r satisfy the conditions of <Ref> with ϵ=Θr/n_ and thus the claim follows. 
Therefore, there exists a constant c>0 such that

    ∑_r=-vm_^2/3^-hm_^2/3ρψ/Σ_(n,m,l)   ≤Θ(1)m_^-2/3∑_r=-vm_^2/3^-hm_^2/3exp3/2-o(1)rl/n_
       (<ref>)≤Θ(1)∫_h^∞e^-cx x = Θ(1)exp-ch = o(1).

Observe that in , if =o(n^1/24), then r>-n_>-vm_^2/3 and thus the interval
-vm_^2/3≤ r ≤ -hm_^2/3 covers all cases for negative r. From now on, we may thus assume that
=Ω(n^1/24), which implies w=Ω(n^1/48).

Now consider the interval -wm_^2/3≤ r ≤ -vm_^2/3. In this regime, we still have
f_d(n_+r,l)-f_d(ñ_,l) = orl/n_ and thus

    ∑_r=-wm_^2/3^-vm_^2/3ρψ/Σ_(n,m,l)≤Θ(1)m_^1/2exp-cv = o(1).


Finally, suppose that r ≤ -wm_^2/3. In this regime,

    s_r ≤exp3l/2-1log1+r/n_+c_1√(l^3/n_+r)-c_2√(l^3/ñ_).

The right hand side has its maximum (with respect to r) at r=-wm_^2/3. For this r, the first summand 
is negative and has order w by (<ref>). The other two summands are o(w) by (<ref>). Thus, there exists
a constant c>0 such that

    ∑_r≤-wm_^2/3ρψ/Σ_(n,m,l)≤Θ(1)nexp-cw,

which is o(1), because w=Ω(n^1/48). This finishes the proof for r<0.


Suppose now that n_>q_ = n_ + hm_^2/3, 
i.e. r>hm_^2/3. By (<ref>), (<ref>), and <Ref> we conclude that

    ∑ρψ/Σ_(n,m,l)≤Θ(1)m_^-2/3∑_r>hm_^2/3exp3lr/2n_+f_d(n_+r,l)-f_d(ñ_,l)-r^3/27m_^2.

Note that for all r in this sum, rl/n_=or^3/m_^2. We claim 
that additionally

    f_d(n_+r,l)-f_d(ñ_,l)=or^3/m_^2.

Indeed, this difference is O(1) in  and , while r^3/m_^2≥ h^3=ω(1).
In the second phase transition, the claim follows immediately if r≥√(l)m_^2/3. If
hm_^2/3<r<√(l)m_^2/3, the conditions of <Ref> are satisfied with ϵ=Θr/n_ and 
thus f_d(n_+r,l)-f_d(ñ_,l)=orl/n_=or^3/m_^2.
Therefore, we deduce that

    ∑ρψ/Σ_(n,m,l)   ≤Θ(1)m_^-2/3∑_r>hm_^2/3exp-r^3/30m_^2
       ≤Θ(1)∫_h^∞exp-x^3 x
      ≤Θ(1)exp(-h).

This finishes the proof also for r>0.










§ DISCUSSION AND OPEN PROBLEMS


Comparing the range for m that we cover in Theorems <ref>–<ref> with the `dense' regime
m=⌊μ n⌋ for 1<μ<3 considered in <cit.>,
a gap of order (log n)^2/3 becomes apparent—a significant improvement of <cit.>, where the gap
had order n^1/3. The order term ^-3/2n^3/5 in <Ref> becomes constant when
=Θ(n^2/5), which matches the results from <cit.>
that the giant component covers all but finitely many vertices in the dense regime. Therefore, we expect <Ref>
to hold for all m=(1+o(1))n.

The gap of order (log n)^2/3 originates from the fact that we can only determine the number of kernels up to an
exponential error term (see <Ref>) in the second phase transition. We thus believe that the key to closing
the gap would be to determine the number of kernels more exactly.


  What is the exact value of _g(2l-d,3l-d) for any admissible l,d∈?


Solving <Ref> would pave the way to prove <Ref> for all m=(1+o(1))n. Moreover, it might open
the possibility to prove an analogous version of <Ref> in the second phase transition, thus rendering
the additional double counting argument in the proof of <Ref> unnecessary; observe that this double counting argument
is responsible for the fact that the upper and lower bound on the order of n-_1 are not quite the same.
We believe that these bounds should actually be of the same order.


  Let m=2+ n^-2/5n/2, where =(n)=o(n^2/5).
  Then  the largest component _1 of _g(n,m) is complex and satisfies
  
    n-_1 =
        Θn^3/5   if →-∞,
    Θn^3/5   if → c∈,
    Θ^-3/2n^3/5   if →∞.



Observe that in contrast to <Ref>, <Ref> does neither provide a statement about the genus of
the largest component nor does it state the order of the i-th largest component for i≥2. 
By <cit.>, the largest
component of _g(n,⌊μ n⌋) has genus g,
thus it is to be expected that this also holds throughout the second phase transition.


  Let m=(1+o(1))n. Then the giant component of _g(n,m)  is not embeddable on g-1 
  and all other components are planar.


In view of <Ref>, an analogous statement to <Ref> for general kernels would be
necessary. Similarly, proving <Ref> for arbitrary kernels would open the possibility to determine the order
of the i-th largest component for i≥2.


  For i≥2, what is the order of the i-th largest component in the second phase transition?


In view of enumeration of graphs embeddable on , <Ref> provides an asymptotic result. Observe that the error terms
in <Ref> become larger the bigger m is. In particular, if we increase  to Θ(n^2/5) in
<Ref><ref>, then the main term of _g(n,m) becomes n^n—which matches the results
from <cit.> for the dense regime m=⌊μ n⌋ with μ∈(1,3)—but the
error term has order expO(n). It should be possible to improve the error terms to being smaller than (1±δ)^l_0 for 
every δ>0 (with l_0 defined as in (<ref>)) by a careful analysis of 
<Ref>, yet even better bounds would still be desirable.


  Find asymptotic expressions for _g(n,m) with better error terms than in <Ref>.


It is important to note that the results in this paper apply to more general graph classes than _g(n,m).
Indeed, the constructive decomposition that yields (<ref>), (<ref>), and (<ref>) relies on
the fact that a graph is in _g if and only if its kernel is in the corresponding class _g
of multigraphs. The only other ingredients of the proof that are specifically tailored for graphs on  are 
<Ref>, and <Ref>. Recall that we saw in
<Ref> that <Ref> holds for any class of multigraphs that is weakly addable (that is, closed
under adding an edge between two components) and closed under taking minors.


  Let X be a graph class and Y be a class of (weighted) multigraphs of minimum degree at least three.
  Suppose that
  
  
  * 
    a graph lies in X if and only if its kernel is in Y;
  
  * 
    there are constants c,γ>0 and k∈ such that
    
    Y(2l,3l) = (1+o(1))c l^kγ^2l(2l)!;

  
  * 
    there is a constant 0<q≤1 with
    
    Y(2l,3l)  is connected l→∞⟶ q;

  
  * 
    _1(Y(2l,3l))=2l-O_p(1) and for each fixed i∈∖{0}, the probability
    that _1(Y(2l,3l))=2l-2i is bounded away from both 0 and 1;
  
  * 
    Y is weakly addable and closed under taking minors.
  
  Then analogous statements to Theorems <ref>–<ref> hold for X.


Obvious candidates for the classes X and Y would be (multi)graphs on non-orientable surfaces.
For such classes, <ref> and <ref> in <Ref> are automatically satisfied, 
<ref> and <ref> would follow if <Ref> also hold for
non-orientable surfaces, and <ref> holds if <Ref> is true for non-orientable surfaces.


  Prove analogous versions of <Ref> and <Ref> for non-orientable
  surfaces.


One striking difference between _g(n,m) and G(n,m) is the order and the structure of the i-th largest 
component for i≥2 in  and . In _g(n,m), the second largest component is much 
larger than in G(n,m); Θ_p(n^2/3) versus o(n^2/3). 
Moreover, the i-th largest component of G(n,m) is a tree . In contrast, _g(n,m) with
positive probability has both tree components and complex components of order Θ_p(n^2/3). It would thus 
be interesting to know whether there is a hierarchy in the size of the largest tree component and the second largest 
complex component.


  Given i≥2, what is the probability that the i-th largest component of _g(n,m) is a tree?


For G(n,m), the giant component is in fact far better understood than it is stated in <Ref>. Central limit theorems
and local limit theorems provide much stronger concentration results about the order (i.e. the number of vertices) and the size (i.e. the number of edges) of the giant 
component <cit.> and give
more insight into the global and local structure of the giant component and its core.


  Derive central and local limit theorems for the giant component of _g(n,m).


As mentioned in <Ref>, the component structure of G(n,m) is closely related to a Galton-Watson branching 
process. More precisely, the local structure of G(n,αn/2) converges to that of a Galton-Watson tree with offspring 
distribution Po(α) in the sense of Benjamini-Schramm local weak convergence <cit.>.
For _g(n,m), the additional constraint of the graph being embeddable on , exploration via a simple Galton-Watson
type process is not possible. This naturally raises the question if the local structure of _g(n,m) can be described
in terms of the Benjamini-Schramm local weak convergence.


  What is the limit of the local structure of _g(n,m) in the sense of the Benjamini-Schramm local weak convergence?


The core, which plays a central role in our constructive decomposition, is also known as the 2-core. More generally, 
given k≥ 2, the k-core of a graph G is the largest subgraph of G of minimum degree at least k. Like the core,
the k-core can be constructed by a peeling process that recursively removes vertices of degree less than k. The order 
and size of the k-core of G(n,m) has been determined in a seminal paper by Pittel, Spencer, and Wormald <cit.>.
Following Pittel, Spencer, and Wormald, the k-core has been extensively studied <cit.>.
The most striking results in this area are the astonishing theorem by  <cit.> that the k-core for k≥ 3 jumps to linear 
order at the very moment it becomes non-empty, the central limit theorem by Janson and Luczak <cit.>, and the local
limit theorem by Coja-Oghlan, Cooley, Kang, and Skubch <cit.> that described—in addition to the order and size—several
other parameters of the k-core of G(n,m). In <cit.>, the same authors used a 5-type branching process in order to determine
the local structure of the k-core. In terms of global structure, <cit.> provides a randomised algorithm that constructs
a random graph with given order and size of the k-core.


  What are the local and global structure of the k-core of _g(n,m)?


One of the main difficulties regarding _g(n,m) is that while graph properties such as having a component of
a certain order are monotone for G(n,m) (that is, for every fixed n, the probability that G(n,m) has this property
is monotone for 0≤ m≤n2), this is not necessarily the case for _g(n,m). Indeed, monotonicity
of graph properties in G(n,m) usually follows immediately from the equivalence between G(n,m) and the random graph
process, where we add one random edge at a time. For graphs on surfaces, however, not all edges are allowed to be added 
in the corresponding process. Thus, the process is fundamentally different from _g(n,m). For instance, in the 
dense regime m=⌊μ n⌋ with μ>1, we know by <cit.> that the probability that 
P(n,m) is connected is bounded away from both 0 and 1. The planar graph process, however, is connected in that regime <cit.>. Knowing which graph properties are monotone for _g(n,m) would yield a significant improvement
to the complexity of the arguments.


  Which graph properties are monotone for _g(n,m)?


The constructive decomposition and generating functions of cubic planar graphs and their relation to 
the core of sparse planar graphs by Kang and Łuczak <cit.> have been strengthened by Noy, 
Ravelomanana, and Rué <cit.> to yield an answer to a challenging open question of  and 
 <cit.> about the limiting probability of G(n,m) being planar at the critical phase
, that is, for every constant ∈, the limit
p() of the probability that Gn,1+ n^-1/3n/2 is
planar. For graphs embeddable on a surface of positive genus, they gave a general strategy of how
to determine the corresponding probability. However, determining the exact limiting probability
for g≥ 1 is still an open problem.

Furthermore, for m beyond , we know that G(n,m)  is not embeddable on any surface of fixed genus. 
This immediately raises the question what genus g we need in order to embed G(n,m) on .


  Let m=m(n) and g=g(n) be given.
  
  
  * 
    When is the limiting probability of G(n,m) being embeddable on  positive?
  
  * 
    When is G(n,m) embeddable on  ?
  
  * 
    What is the expected genus of G(n,m)?
  


Another interesting direction, which might provide insight into the answer of <Ref>, is to
consider _g(n,m) for genus g=g(n) that tends to infinity with n. If g grows `fast enough' (e.g.as n2), then _g(n,m) will coincide with G(n,m) and will thus exhibit the emergence of
the giant component, but not the second phase transition described in <Ref>. For `slowly' growing g, on
the other hand, it is to be expected that the second phase transition does take place.


  For which functions g=g(n) does _g(n,m) feature two phase transitions analogous to <Ref>?





plain



