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
2028633127 2949962875 2952056253 2399682168
Random graph models with limited choice have been studied extensively with the goal of understanding the mechanism of the emergence of the giant component. One of the standard models are the Achlioptas random graph processes on a fixed set of (n ) vertices. Here at each step, one chooses two edges uniformly at random and then decides which one to add to the existing configuration according to some criterion. An important class of such rules are the bounded-size rules where for a fixed (K 1 ), all components of size greater than (K ) are treated equally. While a great deal of work has gone into analyzing the subcritical and supercritical regimes, the nature of the critical scaling window, the size and complexity (deviation from trees) of the components in the critical regime and nature of the merging dynamics has not been well understood. In this work we study such questions for general bounded-size rules. Our first main contribution is the construction of an extension of Aldous’s standard multiplicative coalescent process which describes the asymptotic evolution of the vector of sizes and surplus of all components. We show that this process, referred to as the standard augmented multiplicative coalescent (AMC) is ‘nearly’ Feller with a suitable topology on the state space. Our second main result proves the convergence of suitably scaled component size and surplus vector, for any bounded-size rule, to the standard AMC. This result is new even for the classical Erdős–Renyi setting. The key ingredients here are a precise analysis of the asymptotic behavior of various susceptibility functions near criticality and certain bounds from (The barely subcritical regime. Arxiv preprint, 2012) on the size of the largest component in the barely subcritical regime. In sparse principal component analysis we are given noisy observations of a low-rank matrix of dimension @math and seek to reconstruct it under additional sparsity assumptions. In particular, we assume here each of the principal components @math has at most @math non-zero entries. We are particularly interested in the high dimensional regime wherein @math is comparable to, or even much larger than @math . In an influential paper, johnstone2004sparse introduced a simple algorithm that estimates the support of the principal vectors @math by the largest entries in the diagonal of the empirical covariance. This method can be shown to identify the correct support with high probability if @math , and to fail with high probability if @math for two constants @math . Despite a considerable amount of work over the last ten years, no practical algorithm exists with provably better support recovery guarantees. Here we analyze a covariance thresholding algorithm that was recently proposed by KrauthgamerSPCA . On the basis of numerical simulations (for the rank-one case), these authors conjectured that covariance thresholding correctly recover the support with high probability for @math (assuming @math of the same order as @math ). We prove this conjecture, and in fact establish a more general guarantee including higher-rank as well as @math much smaller than @math . Recent lower bounds berthet2013computational, ma2015sum suggest that no polynomial time algorithm can do significantly better. The key technical component of our analysis develops new bounds on the norm of kernel random matrices, in regimes that were not considered before. We give an approximation algorithm for non-uniform sparsest cut with the following guarantee: For any @math , given cost and demand graphs with edge weights @math respectively, we can find a set @math with @math at most @math times the optimal non-uniform sparsest cut value, in time @math provided @math . Here @math is the @math 'th smallest generalized eigenvalue of the Laplacian matrices of cost and demand graphs; @math (resp. @math ) is the weight of edges crossing the @math cut in cost (resp. demand) graph and @math is the sparsity of the optimal cut. In words, we show that the non-uniform sparsest cut problem is easy when the generalized spectrum grows moderately fast. To the best of our knowledge, there were no results based on higher order spectra for non-uniform sparsest cut prior to this work. Even for uniform sparsest cut, the quantitative aspects of our result are somewhat stronger than previous methods. Similar results hold for other expansion measures like edge expansion, normalized cut, and conductance, with the @math 'th smallest eigenvalue of the normalized Laplacian playing the role of @math in the latter two cases. Our proof is based on an l1-embedding of vectors from a semi-definite program from the Lasserre hierarchy. The embedded vectors are then rounded to a cut using standard threshold rounding. We hope that the ideas connecting @math -embeddings to Lasserre SDPs will find other applications. Another aspect of the analysis is the adaptation of the column selection paradigm from our earlier work on rounding Lasserre SDPs [GS11] to pick a set of edges rather than vertices. This feature is important in order to extend the algorithms to non-uniform sparsest cut. We develop a new technique for constructing sparse graphs that allow us to prove near-linear lower bounds on the round complexity of computing distances in the CONGEST model. Specifically, we show an @math lower bound for computing the diameter in sparse networks, which was previously known only for dense networks [, SODA 2012]. In fact, we can even modify our construction to obtain graphs with constant degree, using a simple but powerful degree-reduction technique which we define. Moreover, our technique allows us to show @math lower bounds for computing @math -approximations of the diameter or the radius, and for computing a @math -approximation of all eccentricities. For radius, we are unaware of any previous lower bounds. For diameter, these greatly improve upon previous lower bounds and are tight up to polylogarithmic factors [, SODA 2012], and for eccentricities the improvement is both in the lower bound and in the approximation factor [Holzer and Wattenhofer, PODC 2012]. Interestingly, our technique also allows showing an almost-linear lower bound for the verification of @math -spanners, for @math .