Search

We study the critical behavior of the component sizes for the configuration model when the tail of the degree distribution of a randomly chosen vertex is a regularly-varying function with exponent $\tau-1$, where $\tau\in (3,4)$. The component sizes are shown to be of the order $n^{(\tau-2)/(\tau-1)}L(n)^{-1}$ for some slowly-varying function $L(\cdot)$. We show that the re-scaled ordered component sizes converge in distribution to the ordered excursions of a thinned L\'evy process. This proves that the scaling limits for the component sizes for these heavy-tailed configuration models are in a different universality class compared to the Erd\H{o}s-R\'enyi random graphs. Also the joint re-scaled vector of ordered component sizes and their surplus edges is shown to have a distributional limit under a strong topology. Our proof resolves a conjecture by Joseph, Ann. Appl. Probab. (2014) about the scaling limits of uniform simple graphs with i.i.d degrees in the critical window, and sheds light on the relation between the scaling limits obtained by Joseph and in this paper, which appear to be quite different. Further, we use percolation to study the evolution of the component sizes and the surplus edges within the critical scaling window, which is shown to converge in finite dimension to the augmented multiplicative coalescent process introduced by Bhamidi et. al., Probab. Theory Related Fields (2014). The main results of this paper are proved under rather general assumptions on the vertex degrees. We also discuss how these assumptions are satisfied by some of the frameworks that have been studied previously., Comment: 43 pages, revision of the paper

Let $\mathcal{G}(N,\frac 1Nt_N)$ be the Erd\H{o}s-R\'enyi graph with connection probability $\frac 1Nt_N\sim t/N$ as $N\to\infty$ for a fixed $t\in(0,\infty)$. We derive a large-deviations principle for the empirical measure of the sizes of all the connected components of $\mathcal{G}(N,\frac 1Nt_N)$, 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.

We study limits of the largest connected components (viewed as metric spaces) obtained by critical percolation on uniformly chosen graphs and configuration models with heavy-tailed degrees. For rank-one inhomogeneous random graphs, such results were derived by Bhamidi, van der Hofstad, Sen [Probab. Theory Relat. Fields 2018]. We develop general principles under which the identical scaling limits as the rank-one case can be obtained. Of independent interest, we derive refined asymptotics for various susceptibility functions and the maximal diameter in the barely subcritical regime., Final published version. 47 pages, 6 figures

The multiplicative coalescent is a mean-field Markov process in which any pair of blocks coalesces at rate proportional to the product of their masses. In Aldous and Limic (Electron. J. Probab. 3 (1998) Paper no. 3) each extreme eternal version of the multiplicative coalescent was described in three different ways, one of which matched its (marginal) law to that of the ordered excursion lengths above past minima of a certain Lévy-type process. ¶ Using a modification of the breadth-first-walk construction from Aldous (Ann. Probab. 25 (1997) 812–854) and Aldous and Limic (Electron. J. Probab. 3 (1998) Paper no. 3), and some new insight from the thesis by Uribe Bravo (Markovian bridges, Brownian excursions, and stochastic fragmentation and coalescence (2007) UNAM), this work settles an open problem (3) from Aldous (Ann. Probab. 25 (1997) 812–854) in the more general context of Aldous and Limic (Electron. J. Probab. 3 (1998) Paper no. 3). Informally speaking, each eternal version is entirely encoded by its Lévy-type process, and contrary to Aldous’ original intuition, the time for the multiplicative coalescent does correspond to the linear increase in the constant part of the drift of the Lévy-type process. In the “standard multiplicative coalescent” context of Aldous (Ann. Probab. 25 (1997) 812–854), this result was first announced by Armendáriz in 2001, while its first published proof is due to Broutin and Marckert (Probab. Theory Related Fields 166 (2016) 515–552), who simultaneously account for the process of excess (or surplus) edge counts.

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 [23, 24, 28, 63] 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\'evy processes "without replacement" [10], 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 finite fractal dimensions and 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\H{o}s-R\'{e}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)$., Comment: 71 pages, 5 figures, To appear in Probability Theory and Related Fields

We introduce the multiplicative coalescent with linear deletion, a continuous-time Markov process describing the evolution of a collection of blocks. Any two blocks of sizes $x$ and $y$ merge at rate $xy$, and any block of size $x$ is deleted with rate $\lambda x$ (where $\lambda\geq 0$ is a fixed parameter). This process arises for example in connection with a variety of random-graph models which exhibit self-organised criticality. We focus on results describing states of the process in terms of collections of excursion lengths of random functions. For the case $\lambda=0$ (the coalescent without deletion) we revisit and generalise previous works by authors including Aldous, Limic, Armendariz, Uribe Bravo, and Broutin and Marckert, in which the coalescence is related to a "tilt" of a random function, which increases with time; for $\lambda>0$ we find a novel representation in which this tilt is complemented by a "shift" mechanism which produces the deletion of blocks. We describe and illustrate other representations which, like the tilt-and-shift representation, are "rigid", in the sense that the coalescent process is constructed as a projection of some process which has all of its randomness in its initial state. We explain some applications of these constructions to models including mean-field forest-fire and frozen-percolation processes., Comment: 45 pages, 6 figures. Updated references

We investigate the component sizes of the critical configuration model, as well as the related problem of critical percolation on a supercritical configuration model. We show that, at criticality, the finite third moment assumption on the asymptotic degree distribution is enough to guarantee that the sizes of the largest connected components are of the order $n^{2/3}$ and the re-scaled component sizes (ordered in a decreasing manner) converge to the ordered excursion lengths of an inhomogeneous Brownian Motion with a parabolic drift. We use percolation to study the evolution of these component sizes while passing through the critical window and show that the vector of percolation cluster-sizes, considered as a process in the critical window, converge to the multiplicative coalescent process in the sense of finite dimensional distributions. This behavior was first observed for Erd\H{o}s-R\'enyi random graphs by Aldous (1997) and our results provide support for the empirical evidences that the nature of the phase transition for a wide array of random-graph models are universal in nature. Further, we show that the re-scaled component sizes and surplus edges converge jointly under a strong topology, at each fixed location of the scaling window., Comment: 33 pages. Minor improvements

We modify the definition of Aldous' multiplicative coalescent process and introduce the multiplicative coalescent with linear deletion (MCLD). A state of this process is a square-summable decreasing sequence of cluster sizes. Pairs of clusters merge with a rate equal to the product of their sizes and clusters are deleted with a rate linearly proportional to their size. We prove that the MCLD is a Feller process. This result is a key ingredient in the description of scaling limits of the evolution of component sizes of the mean field frozen percolation model and the so-called rigid representation of such scaling limits., Comment: 23 pages, 1 figure

We find scaling limits for the sizes of the largest components at criticality for rank-1 inhomogeneous random graphs with power-law degrees with power-law exponent \tau. We investigate the case where $\tau\in(3,4)$, so that the degrees have finite variance but infinite third moment. The sizes of the largest clusters, rescaled by $n^{-(\tau-2)/(\tau-1)}$, converge to hitting times of a "thinned" L\'{e}vy process, a special case of the general multiplicative coalescents studied by Aldous [Ann. Probab. 25 (1997) 812-854] and Aldous and Limic [Electron. J. Probab. 3 (1998) 1-59]. Our results should be contrasted to the case \tau>4, so that the third moment is finite. There, instead, the sizes of the components rescaled by $n^{-2/3}$ converge to the excursion lengths of an inhomogeneous Brownian motion, as proved in Aldous [Ann. Probab. 25 (1997) 812-854] for the Erd\H{o}s-R\'{e}nyi random graph and extended to the present setting in Bhamidi, van der Hofstad and van Leeuwaarden [Electron. J. Probab. 15 (2010) 1682-1703] and Turova [(2009) Preprint]., Comment: Published in at http://dx.doi.org/10.1214/11-AOP680 the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)