Search ResultsShowing 1-17 of 17
-
arXiv:2303.10082 (Published 2023-03-17)
Scaling limits and universality: Critical percolation on weighted graphs converging to an $L^3$ graphon
Comments: 65 pages, 1 figure, the universality principle (Theorem 3.4) from arXiv:1411.3417 has now been included in this paperWe develop a general universality technique for establishing metric scaling limits of critical random discrete structures exhibiting mean-field behavior that requires four ingredients: (i) from the barely subcritical regime to the critical window, components merge approximately like the multiplicative coalescent, (ii) asymptotics of the susceptibility functions are the same as that of the Erdos-Renyi random graph, (iii) asymptotic negligibility of the maximal component size and the diameter in the barely subcritical regime, and (iv) macroscopic averaging of distances between vertices in the barely subcritical regime. As an application of the general universality theorem, we establish, under some regularity conditions, the critical percolation scaling limit of graphs that converge, in a suitable topology, to an $L^3$ graphon. In particular, we define a notion of the critical window in this setting. The $L^3$ assumption ensures that the model is in the Erdos-Renyi universality class and that the scaling limit is Brownian. Our results do not assume any specific functional form for the graphon. As a consequence of our results on graphons, we obtain the metric scaling limit for Aldous-Pittel's RGIV model [9] inside the critical window. Our universality principle has applications in a number of other problems including in the study of noise sensitivity of critical random graphs [52]. In [10], we use our universality theorem to establish the metric scaling limit of critical bounded size rules. Our method should yield the critical metric scaling limit of Rucinski and Wormald's random graph process with degree restrictions [56] provided an additional technical condition about the barely subcritical behavior of this model can be proved.
-
arXiv:2009.10696 (Published 2020-09-22)
Geometry of the minimal spanning tree in the heavy-tailed regime: new universality classes
Comments: 57 pages, 3 figuresA major open conjecture 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 [29, 30, 36, 67] is as follows: for a large class of random graph models with degree exponent $\tau\in (3,4)$, the distance between two typical points on the minimal spanning tree (MST) on the giant component in the supercritical regime scales like $n^{(\tau-3)/(\tau-1)}$. In this paper we give the first rigorous proof of this conjecture. We consider a supercritical inhomogeneous random graph model with degree exponent $\tau\in(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^{-(\tau-3)/(\tau-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 $(\tau-1)/(\tau-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.
-
arXiv:2005.02566 (Published 2020-05-06)
Global lower mass-bound for critical configuration models in the heavy-tailed regime
Comments: 25 pagesCategories: math.PRWe establish the global lower mass-bound property for the largest connected components in the critical window for the configuration model when the degree distribution has an infinite third moment. The scaling limit of the critical percolation clusters, viewed as measured metric spaces, was established in [7] with respect to the Gromov-weak topology. Our result extends those scaling limit results to the stronger Gromov-Hausdorff-Prokhorov topology under slightly stronger assumptions on the degree distribution. This implies the distributional convergence of global functionals such as the diameter of the largest critical components. Further, our result gives a sufficient condition for compactness of the random metric spaces that arise as scaling limits of critical clusters in the heavy-tailed regime.
-
arXiv:1908.04403 (Published 2019-08-12)
On breadth-first constructions of scaling limits of random graphs and random unicellular maps
Comments: 37 pages, 7 figuresWe give alternate constructions of (i) the scaling limit of the uniform connected graphs with given fixed surplus, and (ii) the continuum random unicellular map (CRUM) of a given genus that start with a suitably tilted Brownian continuum random tree and make `horizontal' point identifications, at random heights, using the local time measures. Consequently, this can be seen as a continuum analogue of the breadth-first construction of a finite connected graph. In particular, this yields a breadth-first construction of the scaling limit of the critical Erd\H{o}s-R\'enyi random graph which answers a question posed in [2]. As a consequence of this breadth-first construction we obtain descriptions of the radii, the distance profiles, and the two point functions of these spaces in terms of functionals of tilted Brownian excursions.
-
arXiv:1810.03802 (Published 2018-10-09)
Geometry of the minimal spanning tree of a random $3$-regular graph
Comments: 50 pagesThe global structure of the minimal spanning tree (MST) is expected to be universal for a large class of underlying random discrete structures. But very little is known about the intrinsic geometry of MSTs of most standard models, and so far the scaling limit of the MST viewed as a metric measure space has only been identified in the case of the complete graph [4]. In this work, we show that the MST constructed by assigning i.i.d. continuous edge-weights to either the random (simple) $3$-regular graph or the $3$-regular configuration model on $n$ vertices, endowed with the tree distance scaled by $n^{-1/3}$ and the uniform probability measure on the vertices, converges in distribution with respect to Gromov-Hausdorff-Prokhorov topology to a random compact metric measure space. Further, this limiting space has the same law as the scaling limit of the MST of the complete graph identified in [4] up to a scaling factor of $6^{1/3}$. Our proof relies on a novel argument that uses a coupling between the $3$-regular configuration model and the Erd\H{o}s-R\'enyi random graph. The techniques of this paper can be used to establish the scaling limit of the MST in the setting of various different random graph models provided one additional technical condition is verified.
-
arXiv:1703.09908 (Published 2017-03-29)
A probabilistic approach to the leader problem in random graphs
Comments: 20 pagesConsider the classical Erdos-Renyi random graph process wherein one starts with an empty graph on $n$ vertices at time $t=0$. At each stage, an edge is chosen uniformly at random and placed in the graph. After the original fundamental work in [19], Erd\H{o}s suggested that one should view the original random graph process as a "race of components". This suggested understanding functionals such as the time for fixation of the identity of the maximal component, sometimes referred to as the "leader problem". Using refined combinatorial techniques, {\L}uczak [25] provided a complete analysis of this question including the close relationship to the critical scaling window of the Erdos-Renyi process. In this paper, we abstract this problem to the context of the multiplicative coalescent which by the work of Aldous in [3] describes the evolution of the Erdos-Renyi random graph in the critical regime. Further, different entrance boundaries of this process have arisen in the study of heavy tailed network models in the critical regime with degree exponent $\tau \in (3,4)$. The leader problem in the context of the Erdos-Renyi random graph also played an important role in the study of the scaling limit of the minimal spanning tree on the complete graph [2]. In this paper we provide a probabilistic analysis of the leader problem for the multiplicative coalescent in the context of entrance boundaries of relevance to critical random graphs. As a special case we recover {\L}uczak's result in [25] for the Erdos-Renyi random graph.
-
arXiv:1703.07145 (Published 2017-03-21)
Universality for critical heavy-tailed network models: Metric structure of maximal components
Comments: 47 pages, 3 figuresThe aim of this paper is to understand general universality principles for random network models whose component sizes in the critical regime lie in the multiplicative coalescent universality class but with heavy tails resulting in hubs. For the multiplicative coalescent in this regime, limit (random) metric spaces via appropriate tilts of inhomogeneous continuum random trees were derived by Bhamidi et al. (2015). In this paper we derive sufficient uniform asymptotic negligibility conditions for general network models to satisfy in the barely subcritical regime such that, if the model can be appropriately coupled to a multiplicative coalescent as one transitions from the barely subcritical regime through the critical scaling window, then the maximal components belong to the same universality class as in Bhamidi et al. (2015). As a canonical example, we study critical percolation on configuration models with heavy-tailed degrees. Of independent interest, we derive refined asymptotics for various susceptibility functions and maximal diameter in the barely subcritical regime. These estimates, coupled with the universality result, allow us to derive the asymptotic metric structure of the large components through the critical scaling window for percolation.
-
arXiv:1612.00650 (Published 2016-12-02)
Critical configuration models with infinite third-moment degrees
Comments: 39 pagesWe 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 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.
-
arXiv:1608.07153 (Published 2016-08-25)
Geometry of the vacant set left by random walk on random graphs, Wright's constants, and critical random graphs with prescribed degrees
Comments: 38 pages, 4 figuresWe provide an explicit algorithm for sampling a connected uniform random graph with given degree sequence by first sampling a plane tree with a modified degree sequence according to an appropriately defined measure on the space of plane trees with this modified degree sequence. A careful analysis of this algorithm allows us to derive continuum scaling limits for uniform simple connected graphs with given degree sequence under some regularity conditions. By products of this central result include: (a) asymptotics for the number of connected simple graphs with prescribed degree sequence and fixed complexity; (b) 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 optimal assumptions on the degree sequence. As a substantive application we consider the fractal properties of maximal components in the vacant set left by random walks (VSRW), a question that has witnessed substantial interest in the probability community; see, e.g., [21-23, 27, 52, 53]. We answer a question raised by Cerny and Teixeira [21] by obtaining the metric space scaling limit of maximal components in the VSRW on random regular graphs. Assuming one is able to: (a) establish the existence of the critical point for emergence of a giant component for VSRW on random graphs with general prescribed degree sequence, and (b) establish regularity conditions of the degree sequence of the VSRW in the critical regime analogous to those established in [21] for random regular graphs, the results in this paper would imply universality for the metric space structure of maximal components in VSRW on random graphs with a general given degree sequence under appropriate moment conditions on the degree sequence.
-
arXiv:1605.02868 (Published 2016-05-10)
Critical window for the configuration model: finite third moment degrees
Comments: 32 pagesCategories: math.PRWe 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 component sizes are $O(n^{2/3})$ and the re-scaled component sizes converge to the excursions 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 finite dimensions. 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.
-
arXiv:1508.04645 (Published 2015-08-19)
The multiplicative coalescent, inhomogeneous continuum random trees, and new universality classes for critical random graphs
Comments: 61 pages, 5 figuresOne 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. 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)$.
-
arXiv:1411.3417 (Published 2014-11-13)
Scaling limits of random graph models at criticality: Universality and the basin of attraction of the Erdős-Rényi random graph
Comments: 99 pages, 1 figureOver 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_c$ which 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\H{o}s-R\'enyi 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^{2/3}$) and (b) the structure of components (rescaled by $n^{-1/3}$) converge to random fractals related to the continuum random tree. Till date, (a) has been proven for a number of models using different techniques while (b) has been proven for only two models, the classical Erd\H{o}s-R\'enyi random graph and the rank-1 inhomogeneous random graph. The aim of this paper is to develop a general program for proving such results. The program requires three main ingredients: (i) in the critical scaling window, components merge approximately like the multiplicative coalescent (ii) scaling exponents of susceptibility functions are the same as the Erd\H{o}s-R\'enyi random graph and (iii) macroscopic averaging of expected distances between random points in the same component in the barely subcritical regime. We show that these apply to a number of fundamental random graph models including the configuration model, inhomogeneous random graphs modulated via a finite kernel and bounded size rules. Thus these models all belong to the domain of attraction of the classical Erd\H{o}s-R\'enyi random graph. As a by product we also get results for component sizes at criticality for a general class of inhomogeneous random graphs.
-
Continuum limit of critical inhomogeneous random graphs
Comments: 49 pages, 2 figures. Assumption on exponential moments relaxedMotivated by applications, the last few years have witnessed tremendous interest in understanding the structure as well as the behavior of dynamics for inhomogeneous random graph models. In this study we analyze the maximal components at criticality of one famous class of such models, the rank-one inhomogeneous random graph model. 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\H{o}s-R\'enyi random graph components at criticality Addario-Berry, Broutin and Goldschmidt (2012). A key step is the construction of connected components of the random graph through an appropriate tilt of a famous class of random trees called $\mathbf{p}$-trees (studied previously by Aldous, Miermont and Pitman (2004) and by Camarri and Pitman (2000)). 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 (see Braunstein et al., 2003) for such graph models. By asymptotic equivalence (Janson, 2010), the same results are true for the Chung-Lu model and the Britton-Deijfen-Lof model. A crucial ingredient of the proof of independent interest is tail bounds for the height of $\mathbf{p}$-trees. The techniques developed in this paper form the main technical bedrock for proving continuum scaling limits in the critical regime for a wide array of other random graph models (Bhamidi, Broutin, Sen and Wang, 2014) including the configuration model and inhomogeneous random graphs with general kernels which were introduced by Bollobas, Janson and Riordan (2007).
-
On the largest component in the subcritical regime of the Bohman-Frieze process
Kang, Perkins and Spencer showed that the size of the largest component of the Bohman-Frieze process at a fixed time $t$ smaller than $t_c$, the critical time for the process is $L_1(t)=\Omega(\log n/(t_c-t)^2)$ with high probability. They also conjectured that this is the correct order, that is $L_1(t)=O(\log n/(t_c-t)^2)$ with high probability for fixed $t$ smaller than $t_c$. Using a different approach, Bhamidi, Budhiraja and Wang showed that $L_1(t_n)=O((\log n)^4/(t_c-t_n)^2)$ with high probability for $t_n\leq t_c-n^{-\gamma}$ where $\gamma\in(0,1/4)$. In this paper, we improve their result by showing that for any fixed $\lambda>0$, $L_1(t_n)=O(\log n/(t_c-t_n)^2)$ with high probability for $t_n\leq t_c-\lambda n^{-1/3}$. In particular, this settles the conjecture of Kang, Perkins and Spencer. We also prove some generalizations for general bounded size rules.
-
Minimal spanning trees and Stein's method
Comments: 47 pages, 5 figures, convergence rates in the lattice case improved, references addedCategories: math.PRKesten and Lee [36] proved that the total length of a minimal spanning tree on certain random point configurations in $\mathbb{R}^d$ satisfies a central limit theorem. They also raised the question: how to make these results quantitative? However, techniques employed to tackle the same problem for other functionals studied in geometric probability do not apply directly to the minimal spanning tree. Thus the problem of determining the convergence rate in the central limit theorem for Euclidean minimal spanning trees has remained open. In this work, we establish bounds on the convergence rate for the Poissonized version of this problem by using a variation of Stein's method. We also derive bounds on the convergence rate for the analogous problem in the setup of the lattice $\mathbb{Z}^d$. The contribution of this paper is twofold. First, we develop a general technique to compute convergence rates in central limit theorems satisfied by minimal spanning trees on sequence of weighted graphs which includes minimal spanning trees on Poisson points. Secondly, we present a way of quantifying the Burton-Keane argument for the uniqueness of the infinite open cluster. The latter is interesting in its own right and based on a generalization of our technique, Duminil-Copin, Ioffe and Velenik [28] have recently obtained bounds on probability of two-arm events in a broad class of translation-invariant percolation models.
-
The Speed of a Biased Walk on a Galton-Watson Tree without Leaves is Monotonic with Respect to Progeny Distributions for High Values of Bias
Comments: 20 pagesJournal: Annales de l'Institut Henri Poincare-Probabilites et Statistiques 2015 Vol. 51, No. 1, 304-318Categories: math.PRTags: journal articleConsider biased random walks on two Galton-Watson trees without leaves having progeny distributions $P_1$ and $P_2$ (GW$(P_1)$ and GW$(P_2)$) where $P_1$ and $P_2$ are supported on positive integers and $P_1$ dominates $P_2$ stochastically. We prove that the speed of the walk on GW$(P_1)$ is bigger than the same on GW$(P_2)$ when the bias is larger than a threshold depending on $P_1$ and $P_2$. This partially answers a question raised in \citet*{BenArous}.
-
Limiting spectral distribution of sample autocovariance matrices
Comments: Published in at http://dx.doi.org/10.3150/13-BEJ520 the Bernoulli (http://isi.cbs.nl/bernoulli/) by the International Statistical Institute/Bernoulli Society (http://isi.cbs.nl/BS/bshome.htm)Journal: Bernoulli 2014, Vol. 20, No. 3, 1234-1259DOI: 10.3150/13-BEJ520Categories: math.PRKeywords: sample autocovariance matrices, limiting spectral distribution, sample acvm, sample autocovariance matrix, theoretical acvmTags: journal articleWe show that the empirical spectral distribution (ESD) of the sample autocovariance matrix (ACVM) converges as the dimension increases, when the time series is a linear process with reasonable restriction on the coefficients. The limit does not depend on the distribution of the underlying driving i.i.d. sequence and its support is unbounded. This limit does not coincide with the spectral distribution of the theoretical ACVM. However, it does so if we consider a suitably tapered version of the sample ACVM. For banded sample ACVM the limit has unbounded support as long as the number of non-zero diagonals in proportion to the dimension of the matrix is bounded away from zero. If this ratio tends to zero, then the limit exists and again coincides with the spectral distribution of the theoretical ACVM. Finally, we also study the LSD of a naturally modified version of the ACVM which is not non-negative definite.