Stable graphs: distributions and line-breaking construction

Goldschmidt, Christina; Haas, Bénédicte; Sénizergues, Delphin

doi:10.5802/ahl.138

Goldschmidt, Christina; Haas, Bénédicte; Sénizergues, Delphin

Stable graphs: distributions and line-breaking construction

Annales Henri Lebesgue, Volume 5 (2022), pp. 841-904.

Metadata

DOI10.5802/ahl.138

Keywords Random graphs with given degree sequence, configuration model, scaling limit, stable trees, urn models

Abstract

For $α \in (1, 2]$ , the $α$ -stable graph arises as the universal scaling limit of critical random graphs with i.i.d. degrees having a given $α$ -dependent power-law tail behavior. It consists of a sequence of compact measured metric spaces (the limiting connected components), each of which is tree-like, in the sense that it consists of an $ℝ$ -tree with finitely many vertex-identifications (which create cycles). Indeed, given their masses and numbers of vertex-identifications, these components are independent and may be constructed from a spanning $ℝ$ -tree, which is a biased version of the $α$ -stable tree, with a certain number of leaves glued along their paths to the root. In this paper we investigate the geometric properties of such a component with given mass and number of vertex-identifications. We (1) obtain the distribution of its kernel and more generally of its discrete finite-dimensional marginals, and observe that these distributions are themselves related to the distributions of certain configuration models; (2) determine its distribution as a collection of $α$ -stable trees glued onto its kernel; and (3) present a line-breaking construction, in the same spirit as Aldous’ line-breaking construction of the Brownian continuum random tree.

References

[ABAC + 18] Addario-Berry, Louigi; Angel, Omer; Chapuy, Guillaume; Fusy, Éric; Goldschmidt, Christina, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2018), pp. 933-946 | DOI | MR | Zbl

[ABBG10] Addario-Berry, Louigi; Broutin, Nicolas; Goldschmidt, Christina Critical random graphs: limiting constructions and distributional properties, Electron. J. Probab., Volume 15 (2010), 25, pp. 741-775 | DOI | MR | Zbl

[ABBG12] Addario-Berry, Louigi; Broutin, Nicolas; Goldschmidt, Christina The continuum limit of critical random graphs, Probab. Theory Relat. Fields, Volume 152 (2012) no. 3-4, pp. 367-406 | DOI | MR | Zbl

[ABBGM17] Addario-Berry, Louigi; Broutin, Nicolas; Goldschmidt, Christina; Miermont, Grégory The scaling limit of the minimum spanning tree of the complete graph, Ann. Probab., Volume 45 (2017) no. 5, pp. 3075-3144 | DOI | MR | Zbl

[ABS21] Addario-Berry, Louigi; Sen, Sanchayan Geometry of the minimal spanning tree of a random 3-regular graph, Probab. Theory Relat. Fields, Volume 180 (2021) no. 3-4, pp. 553-620 | DOI | MR | Zbl

[AL98] Aldous, David; Limic, Vlada The entrance boundary of the multiplicative coalescent, Electron. J. Probab., Volume 3 (1998), 3 | DOI | MR | Zbl

[Ald91] Aldous, David The continuum random tree. I, Ann. Probab., Volume 19 (1991) no. 1, pp. 1-28 | MR | Zbl

[Ald97] Aldous, David Brownian excursions, critical random graphs and the multiplicative coalescent, Ann. Probab., Volume 25 (1997) no. 2, pp. 812-854 | DOI | MR | Zbl

[BBI01] Burago, Dmitri; Burago, Yuri; Ivanov, Sergei A course in metric geometry, Graduate Studies in Mathematics, 33, American Mathematical Society, 2001 | MR | Zbl

[BBSW14] Bhamidi, Shankar; Broutin, Nicolas; Sen, Sanchayan; Wang, Xuan Scaling limits of random graph models at criticality: universality and the basin of attraction of the Erdős–Rényi random graph (2014) (preprint, https://arxiv.org/abs/1411.3417v1, to appear inAnnals of Probability)

[BBW14] Bhamidi, Shankar; Budhiraja, Amarjit; Wang, Xuan The augmented multiplicative coalescent, bounded size rules and critical dynamics of random graphs, Probab. Theory Relat. Fields, Volume 160 (2014) no. 3-4, pp. 733-796 | DOI | MR | Zbl

[BC78] Bender, Edward A.; Canfield, E. Rodney The asymptotic number of labeled graphs with given degree sequences, J. Comb. Theory, Ser. A, Volume 24 (1978) no. 3, pp. 296-307 | DOI | MR | Zbl

[BDHS20a] Bhamidi, Shankar; Dhara, Souvik; van der Hofstad, Remco; Sen, Sanchayan Global lower mass-bound for critical configuration models in the heavy-tailed regime (2020) (preprint https://arxiv.org/abs/2005.02566v1)

[BDHS20b] Bhamidi, Shankar; Dhara, Souvik; van der Hofstad, Remco; Sen, Sanchayan Universality for critical heavy-tailed network models: Metric structure of maximal components, Electron. J. Probab., Volume 25 (2020), 47 | MR | Zbl

[BDW18] Broutin, Nicolas; Duquesne, Thomas; Wang, Minmin Limits of multiplicative inhomogeneous random graphs and Lévy trees: The continuum graphs (2018) (to appear in The Annals of Applied Probability, preprint, https://arxiv.org/abs/1804.05871v1)

[BDW21] Broutin, Nicolas; Duquesne, Thomas; Wang, Minmin Limits of multiplicative inhomogeneous random graphs and Lévy trees: Limit theorems, Probab. Theory Relat. Fields, Volume 181 (2021) no. 4, pp. 865-973 | DOI | Zbl

[BHL10] Bhamidi, Shankar; van der Hofstad, Remco; van Leeuwaarden, Johan S. H. Scaling limits for critical inhomogeneous random graphs with finite third moments, Electron. J. Probab., Volume 15 (2010), 54, pp. 1682-1703 | DOI | MR | Zbl

[BHL12] Bhamidi, Shankar; van der Hofstad, Remco; van Leeuwaarden, Johan S. H. Novel scaling limits for critical inhomogeneous random graphs, Ann. Probab., Volume 40 (2012) no. 6, pp. 2299-2361 | DOI | MR | Zbl

[BHS18] Bhamidi, Shankar; van der Hofstad, Remco; Sen, Sanchayan The multiplicative coalescent, inhomogeneous continuum random trees, and new universality classes for critical random graphs, Probab. Theory Relat. Fields, Volume 170 (2018) no. 1-2, pp. 387-474 | DOI | MR | Zbl

[Bol80] Bollobás, Béla A probabilistic proof of an asymptotic formula for the number of labelled regular graphs, Eur. J. Comb., Volume 1 (1980) no. 4, pp. 311-316 | DOI | MR | Zbl

[BS20] Bhamidi, Shankar; Sen, Sanchayan Geometry of the vacant set left by random walks on random graphs, Wright’s constants, and critical random graphs with prescribed degrees, Random Struct. Algorithms, Volume 56 (2020) no. 3, pp. 676-721 | DOI | MR | Zbl

[BSW17] Bhamidi, Shankar; Sen, Sanchayan; Wang, Xuan Continuum limit of critical inhomogeneous random graphs, Probab. Theory Relat. Fields, Volume 169 (2017) no. 1-2, pp. 565-641 | DOI | MR | Zbl

[CD09] Chatterjee, Shirshendu; Durrett, Rick Contact processes on random graphs with power law degree distributions have critical value 0, Ann. Probab., Volume 37 (2009) no. 6, pp. 2332-2356 | DOI | MR | Zbl

[CH13] Curien, Nicolas; Haas, Bénédicte The stable trees are nested, Probab. Theory Relat. Fields, Volume 157 (2013) no. 3-4, pp. 847-883 | DOI | MR | Zbl

[CH17] Curien, Nicolas; Haas, Bénédicte Random trees constructed by aggregation, Ann. Inst. Fourier, Volume 67 (2017) no. 5, pp. 1963-2001 | DOI | Numdam | MR | Zbl

[Cha97] Chaumont, Loïc Excursion normalisée, méandre et pont pour les processus de Lévy stables, Bull. Sci. Math., Volume 121 (1997) no. 5, pp. 377-403 | MR | Zbl

[CK14] Curien, Nicolas; Kortchemski, Igor Random stable looptrees, Electron. J. Probab., Volume 19 (2014), 108 | MR | Zbl

[CKG20] Conchon-Kerjan, Guillaume; Goldschmidt, Christina The stable graph: the metric space scaling limit of a critical random graph with i.i.d. power-law degrees (2020) (preprint, https://arxiv.org/abs/2002.04954v1, to appear in Ann. Probab.)

[DHLS17] Dhara, Souvik; van der Hofstad, Remco; van Leeuwaarden, Johan S. H.; Sen, Sanchayan Critical window for the configuration model: finite third moment degrees, Electron. J. Probab., Volume 22 (2017), 16 | DOI | MR | Zbl

[DHLS20] Dhara, Souvik; van der Hofstad, Remco; van Leeuwaarden, Johan S. H.; Sen, Sanchayan Heavy-tailed configuration models at criticality, Ann. Inst. Henri Poincaré, Probab. Stat., Volume 56 (2020) no. 3, pp. 1515-1558 | MR | Zbl

[Die15] Dieuleveut, Daphné The vertex-cut-tree of Galton–Watson trees converging to a stable tree, Ann. Appl. Probab., Volume 25 (2015) no. 4, pp. 2215-2262 | DOI | MR | Zbl

[DLG02] Duquesne, Thomas; Le Gall, Jean-François Random trees, Lévy processes and spatial branching processes, Astérisque, 281, Société Mathématique de France, 2002 | MR | Zbl

[DLG05] Duquesne, Thomas; Le Gall, Jean-François Probabilistic and fractal aspects of Lévy trees, Probab. Theory Relat. Fields, Volume 131 (2005) no. 4, pp. 553-603 | DOI | MR | Zbl

[DLG09] Duquesne, Thomas; Le Gall, Jean-François On the re-rooting invariance property of Lévy trees, Electron. Commun. Probab., Volume 14 (2009), pp. 317-326 | DOI | MR | Zbl

[Duq03] Duquesne, Thomas A limit theorem for the contour process of conditioned Galton–Watson trees, Ann. Probab., Volume 31 (2003) no. 2, pp. 996-1027 | DOI | MR | Zbl

[GH15] Goldschmidt, Christina; Haas, Bénédicte A line-breaking construction of the stable trees, Electron. J. Probab., Volume 20 (2015), 16 | DOI | MR | Zbl

[HM12] Haas, Bénédicte; Miermont, Grégory Scaling limits of Markov branching trees with applications to Galton–Watson and random unordered trees, Ann. Probab., Volume 40 (2012) no. 6, pp. 2589-2666 | MR | Zbl

[HMPW08] Haas, Bénédicte; Miermont, Grégory; Pitman, Jim; Winkel, Matthias Continuum tree asymptotics of discrete fragmentations and applications to phylogenetic models, Ann. Probab., Volume 36 (2008) no. 5, pp. 1790-1837 | DOI | MR | Zbl

[Hof13] van der Hofstad, Remco Critical behavior in inhomogeneous random graphs, Random Struct. Algorithms, Volume 42 (2013) no. 4, pp. 480-508 | DOI | MR | Zbl

[Hof17] van der Hofstad, Remco Random graphs and complex networks. Vol. 1, Cambridge Series in Statistical and Probabilistic Mathematics, 43, Cambridge University Press, 2017 | DOI | MR | Zbl

[HPW09] Haas, Bénédicte; Pitman, Jim; Winkel, Matthias Spinal partitions and invariance under re-rooting of continuum random trees, Ann. Probab., Volume 37 (2009) no. 4, pp. 1381-1411 | DOI | MR | Zbl

[Jam15] James, Lancelot F. Generalized Mittag–Leffler distributions arising as limits in preferential attachment models (2015) (https://arxiv.org/abs/1509.07150)

[Jan06] Janson, Svante Limit theorems for triangular urn schemes, Probab. Theory Relat. Fields, Volume 134 (2006) no. 3, pp. 417-452 | DOI | MR | Zbl

[JKŁP93] Janson, Svante; Knuth, Donald E.; Łuczak, Tomasz; Pittel, Boris The birth of the giant component, Random Struct. Algorithms, Volume 4 (1993) no. 3, pp. 231-358 | DOI | MR | Zbl

[Jos14] Joseph, Adrien The component sizes of a critical random graph with given degree sequence, Ann. Appl. Probab., Volume 24 (2014) no. 6, pp. 2560-2594 | DOI | MR | Zbl

[Kor17] Kortchemski, Igor Sub-exponential tail bounds for conditioned stable Bienaymé–Galton–Watson trees, Probab. Theory Relat. Fields, Volume 168 (2017) no. 1-2, pp. 1-40 | DOI | MR | Zbl

[LGLJ98] Le Gall, Jean-François; Le Jan, Yves Branching processes in Lévy processes: the exploration process, Ann. Probab., Volume 26 (1998) no. 1, pp. 213-252 | DOI | MR | Zbl

[Mar08] Marchal, Philippe A note on the fragmentation of a stable tree, Fifth Colloquium on Mathematics and Computer Science (Discrete Mathematics and Theoretical Computer Science Proceedings AI), The Association. Discrete Mathematics & Theoretical Computer Science (DMTCS), Nancy, 2008, pp. 489-499 | MR | Zbl

[Mie05] Miermont, Grégory Self-similar fragmentations derived from the stable tree. II. Splitting at nodes, Probab. Theory Relat. Fields, Volume 131 (2005) no. 3, pp. 341-375 | DOI | MR | Zbl

[Mie09] Miermont, Grégory Tessellations of random maps of arbitrary genus, Ann. Sci. Éc. Norm. Supér., Volume 42 (2009) no. 5, pp. 725-781 | DOI | Numdam | MR | Zbl

[MR95] Molloy, Michael; Reed, Bruce A critical point for random graphs with a given degree sequence, Random Struct. Algorithms, Volume 6 (1995) no. 2-3, pp. 161-179 | DOI | MR | Zbl

[NP10] Nachmias, Asaf; Peres, Yuval Critical percolation on random regular graphs, Random Struct. Algorithms, Volume 36 (2010) no. 2, pp. 111-148 | DOI | MR | Zbl

[Pit06] Pitman, Jim Combinatorial stochastic processes; Lectures from the 32nd Summer School on Probability Theory held in Saint-Flour, July 7–24, 2002, Lecture Notes in Mathematics, 1875, Springer, 2006 | MR | Zbl

[Rio12] Riordan, Oliver The phase transition in the configuration model, Comb. Probab. Comput., Volume 21 (2012) no. 1-2, pp. 265-299 | DOI | MR | Zbl

[RW18] Ross, Nathan; Wen, Yuting Scaling limits for some random trees constructed inhomogeneously, Electron. J. Probab., Volume 23 (2018), 5 | DOI | MR | Zbl

[Rém85] Rémy, Jean-Luc Un procédé itératif de dénombrement d’arbres binaires et son application à leur génération aléatoire, RAIRO Inform. Théor., Volume 19 (1985), pp. 179-195 | DOI | MR | Zbl

[Sén19] Sénizergues, Delphin Random gluing of metric spaces, Ann. Probab., Volume 47 (2019) no. 6, pp. 3812-3865 | MR | Zbl

[Sén21] Sénizergues, Delphin Geometry of weighted recursive and affine preferential attachment trees, Electron. J. Probab., Volume 26 (2021), 80 | DOI | MR | Zbl

[Sén22] Sénizergues, Delphin Growing random graphs with a preferential attachment structure, ALEA, Lat. Am. J. Probab. Math. Stat., Volume 19 (2022) no. 1, pp. 259-309 | DOI | MR | Zbl

[Tur13] Turova, Tatyana S. Diffusion approximation for the components in critical inhomogeneous random graphs of rank 1, Random Struct. Algorithms, Volume 43 (2013) no. 4, pp. 486-539 | DOI | MR | Zbl

[Wor78] Wormald, Nicholas Some problems in the enumeration of labelled graphs, Ph. D. Thesis, University of Newcastle, Australia (1978)

Metadata

Abstract

References

Cited by