Let @math be the orientable surface of genus @math . We prove that the component structure of a graph chosen uniformly at random from the class @math of all graphs on vertex set @math with @math edges embeddable on @math features two phase transitions. The first phase transition mirrors the classical phase transition in the Erdős--Renyi random graph @math chosen uniformly at random from all graphs with vertex set @math and @math edges. It takes place at @math , when a unique largest component, the so-called , emerges. The second phase transition occurs at @math , when the giant component covers almost all vertices of the graph. This kind of phenomenon is strikingly different from @math and has only been observed for graphs on surfaces. Moreover, we derive an asymptotic estimation of the number of graphs in @math throughout the regimes of these two phase transitions.
Planar graphs and graphs embeddable on @math have been investigated separately for the sparse' regime @math @cite_49 and for the dense' regime @math with @math @cite_47 @cite_53 . 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 @cite_49 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 @cite_49 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 @cite_49 .
@cite_47 @cite_49 @cite_53
2057857650 2018165282
Let P (n;M) be a graph chosen uniformly at random from the family of all labeled planar graphs with n vertices and M edges. In the paper we study the component structure of P (n;M). Combining counting arguments with analytic techniques, we show that there are two critical periods in the evolution of P (n;M). The first one, of width ( n 2=3 ), is analogous to the phase transition observed in the standard random graph models and takes place for M = n=2 +O(n 2=3 ), when the largest complex component is formed. Then, for M = n + O(n 3=5 ), when the complex components covers nearly all vertices, the second critical period of width n 3=5 occurs. Starting from that moment increasing of M mostly affects the density of the complex components, not its size. A graph is planar if it can be embedded in the plane, or in the sphere, so that no two edges cross at an interior point. A planar graph together with a particular embedding is called a map. There is a rich theory of counting maps, started by Tutte in the 1960's. However, in this paper we are interested in counting graphs as combinatorial objects, regardless of how many nonequivalent topological embeddings they may have. As we are going to see, this makes the counting considerably more difficult.