Largest component of subcritical random graphs with given degree sequence. (English) Zbl 1517.05158

Summary: We study the size of the largest component of two models of random graphs with prescribed degree sequence, the configuration model (CM) and the uniform model (UM), in the (barely) subcritical regime. For the CM, we give upper bounds that are asymptotically tight for certain degree sequences. These bounds hold under mild conditions on the sequence and improve previous results of H. Hatami and M. Molloy [Random Struct. Algorithms 41, No. 1, 99–123 (2012; Zbl 1247.05218)] on the barely subcritical regime. For the UM, we give weaker upper bounds that are tight up to logarithmic terms but require no assumptions on the degree sequence. In particular, the latter result applies to degree sequences with infinite variance in the subcritical regime.


05C80 Random graphs (graph-theoretic aspects)
05C82 Small world graphs, complex networks (graph-theoretic aspects)
60C05 Combinatorial probability
60F05 Central limit and other weak theorems


Zbl 1247.05218
Full Text: DOI arXiv Link


[1] B. Bollobás. A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. Europ. J. Combin., 1(4):311-316, 1980. doi: 10/ggktcq. · Zbl 0457.05038
[2] B. Bollobás and O. Riordan. An old approach to the giant component problem. J. Combin. Theory (Series B), 113:236-260, 2015. doi: 10/gjs3rw. · Zbl 1315.05123
[3] S. Dhara, R. van der Hofstad, J. S. van Leeuwaarden, S. Sen, et al. Critical window for the configuration model: finite third moment degrees. Electron. J. Probab., 22:1-33, 2017. doi: 10/f9vx9f. · Zbl 1387.60016
[4] S. Dhara, R. van der Hofstad, J. S. van Leeuwaarden, and S. Sen. Heavy-tailed configuration models at criticality. Ann. Inst. H. Poincaré Probab. Statist., 56(3):1515-1558, 2020. doi: 10/jwkb. · Zbl 1475.60020
[5] R. A. Doney. One-sided local large deviation and renewal theorems in the case of infinite mean. Probability theory and related fields, 107(4):451-465, 1997. · Zbl 0883.60022
[6] R. Durrett. Random graph dynamics. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2007. doi: 10/fdc2wd. · Zbl 1116.05001
[7] R. Durrett. Probability: theory and examples. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019. doi: 10/gn7c6z. · Zbl 1440.60001
[8] P. Erdős and A. Rényi. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5(1):17-60, 1960. doi: 10/gqf5nk. · Zbl 0103.16301
[9] D. A. Freedman. On tail probabilities for martingales. Ann. Probab., 3(1):100-118, 1975. doi: 10/fdvpst. · Zbl 0313.60037
[10] A. Frieze and M. Karoński. Introduction to random graphs. Cambridge University Press, 2016. doi: 10/ggm2gw. · Zbl 1328.05002
[11] H. Hatami and M. Molloy. The scaling window for a random graph with a given degree sequence. Random Structures Algorithms, 41:99-123, 2012. doi: 10/f32jjv. · Zbl 1247.05218
[12] R. van der Hofstad. Random Graphs and Complex Networks. Volume 1. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2016. doi: 10/ggv8q7.
[13] R. van der Hofstad, S. Janson, and M. Luczak. Component structure of the configuration model: barely supercritical case. Random Structures Algorithms, 55(1):3-55, 2019. doi: 10/gjfc6r. · Zbl 1425.05145
[14] S. Janson. The largest component in a subcritical random graph with a power law degree distribution. Ann. Appl. Probab., 18(4):1651-1668, 2008. doi: 10.1214/07-AAP490. · Zbl 1149.60007
[15] S. Janson. The probability that a random multigraph is simple. Comb., Probab. Comput., 18(1-2):205-225, 2009. doi: 10/bg4m2c. · Zbl 1216.05145
[16] S. Janson and M. J. Luczak. A new approach to the giant component problem. Random Structures Algorithms, 34:197-216, 2009. doi: 10/fhwrsx. · Zbl 1177.05110
[17] S. Janson, T. Łuczak, and A. Ruciński. Random graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons, 2011. doi: 10/d8w6m8.
[18] F. Joos, G. Perarnau, D. Rautenbach, and B. Reed. How to determine if a random graph with a fixed degree sequence has a giant component. Probability Theory and Related Fields, 170(1-2):263-310, 2018. doi: 10/gcwv6j. · Zbl 1379.05102
[19] A. Joseph. The component sizes of a critical random graph with pre-described degree sequence. Ann. Appl. Probab., 24:2560-2594, 2014. doi: 10/f6kvfn. · Zbl 1318.60015
[20] M. Molloy and B. Reed. A critical point for random graphs with a given degree sequence. Random Structures Algorithms, 6:161-180, 1995. doi: 10/c57q6j. · Zbl 0823.05050
[21] A. Mukhin. Local limit theorems for distributions of sums of independent random vectors. Theory of Probability & Its Applications, 29(2):369-375, 1985. doi: 10/bzq7gg. · Zbl 0557.60019
[22] A. Mukhin. Local limit theorems for lattice random variables. Theory of Probability & Its Applications, 36(4):698-713, 1992. doi: 10/dsb956. · Zbl 0776.60027
[23] A. Nachmias and Y. Peres. Critical percolation on random regular graphs. Random Structures Algorithms, 36:111-148, 2010. doi: 10/fss9pk. · Zbl 1209.05228
[24] V. V. Petrov. Sums of independent random variables. Springer-Verlag, New York-Heidelberg, 1975. doi: 10/hgck. · Zbl 0322.60042
[25] B. G. Pittel. On the largest component of a random graph with a subpower-law degree sequence in a subcritical phase. Ann. Appl. Probab., 18(4):1636-1650, 2008. doi: 10/dv9jq9. · Zbl 1149.05043
[26] O. Riordan. The phase transition in the configuration model. Comb., Probab.Comput., 21:265-299, 2012. doi: 10/gkqqb8 · Zbl 1241.05134
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.