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.
The theme of this work is an "inside-out" approach to the enumeration of graphs. It is based on a well-known decomposition of a graph into its 2-core, i.e. the largest subgraph of minimum degree 2 or more, and a forest of trees attached. Using our earlier (asymptotic) formulae for the total number of 2-cores with a given number of vertices and edges, we solve the corresponding enumeration problem for the connected 2-cores. For a subrange of the parameters, we also enumerate those 2-cores by using a deeper inside-out notion of a kernel of a connected 2-core.Using this enumeration result in combination with Caley's formula for forests, we obtain an alternative and simpler proof of the asymptotic formula of Bender, Canfield and McKay for the number of connected graphs with n vertices and m edges, with improved error estimate for a range of m values.As another application, we study the limit joint distribution of three parameters of the giant component of a random graph with n vertices in the supercritical phase, when the difference between average vertex degree and 1 far exceeds n-1 3. The three parameters are defined in terms of the 2-core of the giant component, i.e. its largest subgraph of minimum degree 2 or more. They are the number of vertices in the 2-core, the excess (#edges - #vertices) of the 2-core, and the number of vertices not in the 2-core. We show that the limit distribution is jointly Gaussian throughout the whole supercritical phase. In particular, for the first time, the 2-core size is shown to be asymptotically normal, in the widest possible range of the average vertex degree. We study the behavior of a random graph process (G(n, M))02 n for M(n) = n 2 + s and ∣s∣3n−;2 → ∞. Among others we find the number of components in G(n, M) and estimate the number of vertices and edges in the kth largest component of G(n, M), for any natural number k, Moreover, it is shown that, with probability 1 –o(1), when M(n) = n 2 + s, s3n−2 →−∞, then during a random graph process in some step M1 > M a “new” largest component will emerge, whereas when s3n−2→∞, the largest component of G(n, M) remains largest until the very end of the process. © 1990 Wiley Periodicals, Inc. In this paper we give a simple new proof of a result of Pittel and Wormald concerning the asymptotic value and (suitably rescaled) limiting distribution of the number of vertices in the giant component of G(n,p) above the scaling window of the phase transition. Nachmias and Peres used martingale arguments to study Karp@?s exploration process, obtaining a simple proof of a weak form of this result. We use slightly different martingale arguments to obtain a much sharper result with little extra work. Consider the random graph models G(n, #edges = M) and G(n, Prob(edge) = p) with M = M(n) = (1 + )n-1 3)n 2 and p = p(n) = (1 +An-1 3) n . For 1 > -1 define an i-component of a random graph as a component which has exactly I more edges than vertices. Call an i-component with I > 1 a complex component. For both models, we show that when A is constant, the expected number of complex components is bounded, almost surely (a.s.) each of these components (if any exist) has size of order n2 3, and the maximum value of I is bounded in probability. We prove that a.s. the largest suspended tree in each complex component has size of order n2 3, and deletion of all suspended trees results in a "smoothed" graph of size of order n 3, with the maximum vertex degree 3. The total number of branching vertices, i.e., of degree 3, is bounded in probability. Thus, each complex component is almost surely topologically equivalent to a 3-regular multigraph of a uniformly bounded size. Lengths of the shortest cycle and of the shortest path between two branching vertices of a smoothed graph are each of order n 3. We find a relatively simple integral formula for the limit distribution of the numbers of complex components, which implies, in particular, that all values of the "complexity spectrum" have positive limiting probabilities. We also answer questions raised by Erdos and Renyi back in 1960. It is proven that there exists p(A), the limiting planarity probability, with 0 < p(A) < 1, p(-oo) = 1, p(oo) = 0. In particular, G(n, M) (G(n, p), resp.) is almost surely nonplanar iff (M n 2)n-213 -* 00 ((np I)n-1 3) -+ oo, resp.). Recently, in [Random Struct Algorithm 41 2012, 441-450] we adapted exploration and martingale arguments of Nachmias and Peres [ALEA Lat Am J Probab Math Stat 3 2007, 133-142], in turn based on ideas of Martin-Lof [J Appl Probab 23 1986, 265-282], Karp [Random Struct Alg 1 1990, 73-93] and Aldous [Ann Probab 25 1997, 812-854], to prove asymptotic normality of the number L1 of vertices in the largest component L1 of the random r-uniform hypergraph in the supercritical regime. In this paper we take these arguments further to prove two new results: strong tail bounds on the distribution of L1, and joint asymptotic normality of L1 and the number M1 of edges of L1 in the sparsely supercritical case. These results are used in [Combin Probab Comput 25 2016, 21-75], where we enumerate sparsely connected hypergraphs asymptotically. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 325-352, 2017 Let H d (n,p) signify a random d -uniform hypergraph with n vertices in which each of the @math possible edges is present with probability p = p(n) independently, and let H d (n,m) denote a uniformly distributed d -uniform hypergraph with n vertices and m edges. We derive local limit theorems for the joint distribution of the number of vertices and the number of edges in the largest component of H d (n,p) and H d (n,m) in the regime @math , resp. d(d−1)m n >1+ϵ, where ϵ>0 is arbitrarily small but fixed as n → ∞. The proofs are based on a purely probabilistic approach. We establish central and local limit theorems for the number of vertices in the largest component of a random d-uniform hypergraph Hd(n,p) with edge probability p = c- @math , where c > (d - 1)-1 is a constant. The proof relies on a new, purely probabilistic approach. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2010 