Search

A well-known open problem on the behavior of optimal paths in random graphs in the strong disorder regime, formulated by statistical physicists, and supported by a large amount of numerical evidence over the last decade (Braunstein et al. in Phys Rev Lett 91(16):168701, 2003; Braunstein et al. in Int J Bifurc Chaos 17(07):2215–2255, 2007; Chen et al. in Phys Rev Lett 96(6):068702, 2006; Wu et al. in Phys Rev Lett 96(14):148702, 2006) is as follows: for a large class of random graph models with degree exponent τ ∈ (3 , 4) , distances in the minimal spanning tree (MST) on the giant component in the supercritical regime scale like n (τ - 3) / (τ - 1) . The aim of this paper is to make progress towards a proof of this conjecture. We consider a supercritical inhomogeneous random graph model with degree exponent τ ∈ (3 , 4) that is closely related to Aldous's multiplicative coalescent, and show that the MST constructed by assigning i.i.d. continuous weights to the edges in its giant component, endowed with the tree distance scaled by n - (τ - 3) / (τ - 1) , converges in distribution with respect to the Gromov–Hausdorff topology to a random compact real tree. Further, almost surely, every point in this limiting space either has degree one (leaf), or two, or infinity (hub), both the set of leaves and the set of hubs are dense in this space, and the Minkowski dimension of this space equals (τ - 1) / (τ - 3) . The multiplicative coalescent, in an asymptotic sense, describes the evolution of the component sizes of various near-critical random graph processes. We expect the limiting spaces in this paper to be the candidates for the scaling limit of the MST constructed for a wide array of other heavy-tailed random graph models. [ABSTRACT FROM AUTHOR]

Let 𝒢(N,1NtN) be the Erdős–Rényi graph with connection probability 1NtN∼t/N as N → ∞ for a fixed t ∈ (0, ∞). We derive a large‐deviations principle for the empirical measure of the sizes of all the connected components of 𝒢(N,1NtN), registered according to microscopic sizes (i.e., of finite order), macroscopic ones (i.e., of order N), and mesoscopic ones (everything in between). The rate function explicitly describes the microscopic and macroscopic components and the fraction of vertices in components of mesoscopic sizes. Moreover, it clearly captures the well known phase transition at t = 1 as part of a comprehensive picture. The proofs rely on elementary combinatorics and on known estimates and asymptotics for the probability that subgraphs are connected. We also draw conclusions for the strongly related model of the multiplicative coalescent, the Marcus–Lushnikov coagulation model with monodisperse initial condition, and its gelation phase transition. [ABSTRACT FROM AUTHOR]

We study the fixation time of the identity of the leader, that is, the most massive component, in the general setting of Aldous's multiplicative coalescent, which in an asymptotic sense describes the evolution of the component sizes of a wide array of near‐critical coalescent processes, including the classical Erdős‐Rényi process. We show tightness of the fixation time in the "Brownian" regime, explicitly determining the median value of the fixation time to within an optimal O(1) window. This generalizes Łuczak's result for the Erdős‐Rényi random graph using completely different techniques. In the heavy‐tailed case, in which the limit of the component sizes can be encoded using a thinned pure‐jump Lévy process, we prove that only one‐sided tightness holds. This shows a genuine difference in the possible behavior in the two regimes. [ABSTRACT FROM AUTHOR]

We provide an explicit algorithm for sampling a uniform simple connected random graph with a given degree sequence. By products of this central result include: (1) continuum scaling limits of uniform simple connected graphs with given degree sequence and asymptotics for the number of simple connected graphs with given degree sequence under some regularity conditions, and (2) scaling limits for the metric space structure of the maximal components in the critical regime of both the configuration model and the uniform simple random graph model with prescribed degree sequence under finite third moment assumption on the degree sequence. As a substantive application we answer a question raised by Černý and Teixeira study by obtaining the metric space scaling limit of maximal components in the vacant set left by random walks on random regular graphs. [ABSTRACT FROM AUTHOR]

One major open conjecture in the area of critical random graphs, formulated by statistical physicists, and supported by a large amount of numerical evidence over the last decade (Braunstein et al. in Phys Rev Lett 91(16):168701, 2003; Wu et al. in Phys Rev Lett 96(14):148702, 2006; Braunstein et al. Int J Bifurc Chaos 17(07):2215-2255, 2007; Chen et al. in Phys Rev Lett 96(6):068702, 2006) is as follows: for a wide array of random graph models with degree exponent $$\tau \in (3,4)$$ , distances between typical points both within maximal components in the critical regime as well as on the minimal spanning tree on the giant component in the supercritical regime scale like $$n^{(\tau -3)/(\tau -1)}$$ . In this paper we study the metric space structure of maximal components of the multiplicative coalescent, in the regime where the sizes converge to excursions of Lévy processes 'without replacement' (Aldous and Limic Electron in J Probab 3(3):59, 1998), yielding a completely new class of limiting random metric spaces. A by-product of the analysis yields the continuum scaling limit of one fundamental class of random graph models with degree exponent $$\tau \in (3,4)$$ where edges are rescaled by $$n^{-(\tau -3)/(\tau -1)}$$ yielding the first rigorous proof of the above conjecture. The limits in this case are compact 'tree-like' random fractals with a dense collection of hubs (infinite degree vertices), a finite number of which are identified with leaves to form shortcuts. In a special case, we show that the Minkowski dimension of the limiting spaces equal $$(\tau -2)/(\tau -3)$$ a.s., in stark contrast to the Erdős-Rényi scaling limit whose Minkowski dimension is 2 a.s. It is generally believed that dynamic versions of a number of fundamental random graph models, as one moves from the barely subcritical to the critical regime can be approximated by the multiplicative coalescent. In work in progress, the general theory developed in this paper is used to prove analogous limit results for other random graph models with degree exponent $$\tau \in (3,4)$$ . Our proof makes crucial use of inhomogeneous continuum random trees (ICRT), which have previously arisen in the study of the entrance boundary of the additive coalescent. We show that tilted versions of the same objects using the associated mass measure, describe connectivity properties of the multiplicative coalescent. Since convergence of height processes of corresponding approximating $$\mathbf {p}$$ -trees is not known, we use general methodology in Athreya et al. (2014) and develop novel techniques relying on first showing convergence in the Gromov-weak topology and then extending this to Gromov-Hausdorff-Prokhorov convergence by proving a global lower mass-bound. [ABSTRACT FROM AUTHOR]

Over the last few years a wide array of random graph models have been postulated to understand properties of empirically observed networks. Most of these models come with a parameter t (usually related to edge density) and a (model dependent) critical time t that specifies when a giant component emerges. There is evidence to support that for a wide class of models, under moment conditions, the nature of this emergence is universal and looks like the classical Erdős-Rényi random graph, in the sense of the critical scaling window and (a) the sizes of the components in this window (all maximal component sizes scaling like n) and (b) the structure of components (rescaled by n) converge to random fractals related to the continuum random tree. The aim of this note is to give a non-technical overview of recent breakthroughs in this area, emphasizing a particular tool in proving such results called the differential equations technique first developed and used extensively in probabilistic combinatorics in the work of Wormald [52, 53] and developed in the context of critical random graphs by the authors and their collaborators in [10-12]. [ABSTRACT FROM AUTHOR]

The last few years have witnessed tremendous interest in understanding the structure as well as the behavior of dynamics for inhomogeneous random graph models to gain insight into real-world systems. In this study we analyze the maximal components at criticality of one famous class of such models, the rank-one inhomogeneous random graph model (Norros and Reittu, Adv Appl Probab 38(1):59-75, 2006; Bollobás et al., Random Struct Algorithms 31(1):3-122, 2007, Section 16.4). Viewing these components as measured random metric spaces, under finite moment assumptions for the weight distribution, we show that the components in the critical scaling window with distances scaled by $$n^{-1/3}$$ converge in the Gromov-Haussdorf-Prokhorov metric to rescaled versions of the limit objects identified for the Erdős-Rényi random graph components at criticality in Addario-Berry et al. (Probab. Theory Related Fields, 152(3-4):367-406, 2012). A key step is the construction of connected components of the random graph through an appropriate tilt of a fundamental class of random trees called $$\mathbf {p}$$ -trees (Camarri and Pitman, Electron. J. Probab 5(2):1-18, 2000; Aldous et al., Probab Theory Related Fields 129(2):182-218, 2004). This is the first step in rigorously understanding the scaling limits of objects such as the minimal spanning tree and other strong disorder models from statistical physics (Braunstein et al., Phys Rev Lett 91(16):168701, 2003) for such graph models. By asymptotic equivalence (Janson, Random Struct Algorithms 36(1):26-45, 2010), the same results are true for the Chung-Lu model (Chung and Lu, Proc Natl Acad Sci 99(25):15879-15882, 2002; Chung and Lu, Ann Combin 6(2):125-145, 2002; Chung and Lu, Complex graphs and networks, 2006) and the Britton-Deijfen-Martin-Löf model (Britton et al., J Stat Phys 124(6):1377-1397, 2006). A crucial ingredient of the proof of independent interest are tail bounds for the height of $$\mathbf {p}$$ -trees. The techniques developed in this paper form the main technical bedrock for the general program developed in Bhamidi et al. (Scaling limits of random graph models at criticality: Universality and the basin of attraction of the Erdős-Rényi random graph. arXiv preprint, 2014) for proving universality of the continuum scaling limits in the critical regime for a wide array of other random graph models including the configuration model and inhomogeneous random graphs with general kernels (Bollobás et al., Random Struct Algorithms 31(1):3-122, 2007). [ABSTRACT FROM AUTHOR]

We revisit the discrete additive and multiplicative coalescents, starting with n particles with unit mass. These cases are known to be related to some 'combinatorial coalescent processes': a time reversal of a fragmentation of Cayley trees or a parking scheme in the additive case, and the random graph process $$(G(n,p))_p$$ in the multiplicative case. Time being fixed, encoding these combinatorial objects in real-valued processes indexed by the line is the key to describing the asymptotic behaviour of the masses as $$n\rightarrow +\infty $$ . We propose to use the Prim order on the vertices instead of the classical breadth-first (or depth-first) traversal to encode the combinatorial coalescent processes. In the additive case, this yields interesting connections between the different representations of the process. In the multiplicative case, it allows one to answer to a stronger version of an open question of Aldous (Ann Probab 25:812-854, 1997): we prove that not only the sequence of (rescaled) masses, seen as a process indexed by the time $$\lambda $$ , converges in distribution to the reordered sequence of lengths of the excursions above the current minimum of a Brownian motion with parabolic drift $$(B_t+\lambda t - t^2/2, t\ge 0)$$ , but we also construct a version of the standard augmented multiplicative coalescent of Bhamidi et al. (Probab Theory Relat, 2013) using an additional Poisson point process. [ABSTRACT FROM AUTHOR]

The percolation phase transition and the mechanism of the emergence of the giant component through the critical scaling window for random graph models, has been a topic of great interest in many different communities ranging from statistical physics, combinatorics, computer science, social networks and probability theory. The last fewyears have witnessed an explosion of models which couple random aggregation rules, that specify how one adds edges to existing configurations, and choice, wherein one selects from a "limited" set of edges at random to use in the configuration. While an intense study of such models has ensued, understanding the actual emergence of the giant component and merging dynamics in the critical scaling window has remained impenetrable to a rigorous analysis. In this work we take an important step in the analysis of such models by studying one of the standard examples of such processes, namely the Bohman-Frieze model, and provide first results on the asymptotic dynamics, through the critical scaling window, that lead to the emergence of the giant component for such models. We identify the scaling window and show that through this window, the component sizes properly rescaled converge to the standard multiplicative coalescent. Proofs hinge on a careful analysis of certain infinite-type branching processes with types taking values in the space of cadlag paths, and stochastic analytic techniques to estimate susceptibility functions of the components all the way through the scaling window where these functions explode. Previous approaches for analyzing random graphs at criticality have relied largely on classical breadth-first search techniques that exploit asymptotic connections with Brownian excursions. For dynamic random graph models evolving via general Markovian rules, such approaches fail and we develop a quite different set of tools that can potentially be used for the study of critical dynamics for all bounded size rules. [ABSTRACT FROM AUTHOR]

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\ge 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-Rényi setting. The key ingredients here are a precise analysis of the asymptotic behavior of various susceptibility functions near criticality and certain bounds from Bhamidi et al. (The barely subcritical regime. Arxiv preprint, ) on the size of the largest component in the barely subcritical regime. [ABSTRACT FROM AUTHOR]