Consider the Erdős–Renyi random graph on (n ) vertices where each edge is present independently with probability ( n ), with ( >0 ) fixed. For large (n ), a typical random graph locally behaves like a Galton–Watson tree with Poisson offspring distribution with mean ( ). Here, we study large deviations from this typical behavior within the framework of the local weak convergence of finite graph sequences. The associated rate function is expressed in terms of an entropy functional on unimodular measures and takes finite values only at measures supported on trees. We also establish large deviations for other commonly studied random graph ensembles such as the uniform random graph with given number of edges growing linearly with the number of vertices, or the uniform random graph with given degree sequence. To prove our results, we introduce a new configuration model which allows one to sample uniform random graphs with a given neighborhood distribution, provided the latter is supported on trees. We also introduce a new class of unimodular random trees, which generalizes the usual Galton Watson tree with given degree distribution to the case of neighborhoods of arbitrary finite depth. These generalized Galton Watson trees turn out to be useful in the analysis of unimodular random trees and may be considered to be of interest in their own right.
Large deviations in random graphs is a rapidly growing topic. For dense graphs, e.g. @math with fixed @math , a thorough treatment has been given recently by Chatterjee and Varadhan @cite_12 , in the framework of the cut topology introduced by Lov 'a sz and coauthors, see Borgs, Chayes, Lov 'a sz, S 'o s and Vesztergombi @cite_25 - @cite_14 . In the sparse regime, only a few partial results are known. O'Connell @cite_7 , Biskup, Chayes and Smith @cite_11 and Puhalskii @cite_4 have proven large deviation asymptotics for the connectivity and for the size of the connected components. Large deviations for degree sequences of Erd o s-R 'enyi graphs has been studied in Doku-Amponsah and M "o rters @cite_23 and Boucheron, Gamboa and L 'eonard [Theorem 7.1] BGL2002 . Closer to our approach, large deviations in the local weak topology were obtained for critical multi-type Galton-Watson trees by Dembo, M "o rters and Sheffield @cite_6 . Finally, large deviations for other models of statistical physics on Erd o s-R 'enyi graphs have been considered in Rivoire @cite_17 and Engel, Monasson, and Hartmann @cite_28 .
@cite_14 @cite_4 @cite_7 @cite_28 @cite_17 @cite_6 @cite_23 @cite_25 @cite_12 @cite_11
2028633127 2124280121 2161506909 2012184276
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 this paper we determine the percolation threshold for an arbitrary sequence of dense graphs (G n ). Let λn be the largest eigenvalue of the adjacency matrix of G n , and let G n (p n ) be the random subgraph of G n obtained by keeping each edge independently with probability p n . We show that the appearance of a giant component in G n (p n ) has a sharp threshold at p n = 1 λ n . In fact, we prove much more: if (G n ) converges to an irreducible limit, then the density of the largest component of G n (c n) tends to the survival probability of a multi-type branching process defined in terms of this limit. Here the notions of convergence and limit are those of Borgs, Chayes, Lovasz, S6s and Vesztergombi. In addition to using basic properties of convergence, we make heavy use of the methods of Bollobas, Janson and Riordan, who used multi-type branching processes to study the emergence of a giant component in a very broad family of sparse inhomogeneous random graphs. In this article we propose new methods for computing the asymptotic value for the logarithm of the partition function (free energy) for certain statistical physics models on certain type of finite graphs, as the size of the underlying graph goes to infinity. The two models considered are the hard-core (independent set) model when the activity parameter λ is small, and also the Potts (q-coloring) model. We only consider the graphs with large girth. In particular, we prove that asymptotically the logarithm of the number of independent sets of any r-regular graph with large girth when rescaled is approximately constant if r ≤ 5. For example, we show that every 4-regular n-node graph with large girth has approximately (1.494…)n-many independent sets, for large n. Further, we prove that for every r-regular graph with r ≥ 2, with n nodes and large girth, the number of proper q ≥ r + 1 colorings is approximately @math n, for large n. We also show that these results hold for random regular graphs with high probability (w.h.p.) as well. As a byproduct of our method we obtain simple algorithms for the problem of computing approximately the logarithm of the number of independent sets and proper colorings, in low degree graphs with large girth. These algorithms are deterministic and use certain correlation decay properties for the corresponding Gibbs measures, and its implications to uniqueness of the Gibbs measures on the infinite trees, as well as some simple cavity trick which is well known in the physics and the Markov chain sampling literature.© 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008 Preliminary version of this paper appeared in Proceedings of the Seventeenth ACM-SIAM Symposium on Discrete Algorithms 2006. ArXive version. 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.).