Hostname: page-component-745bb68f8f-hvd4g Total loading time: 0 Render date: 2025-02-06T14:15:56.376Z Has data issue: false hasContentIssue false
  • English
  • Français

Critical Window for Connectivity in the Configuration Model

Part of: Combinatorial probability Combinatorics Graph theory

Published online by Cambridge University Press:  29 May 2017

LORENZO FEDERICO  and
REMCO VAN DER HOFSTAD
LORENZO FEDERICO
Affiliation:
Department of Mathematics and Computer Science, Eindhoven University of Technology, PO Box 513, 5600 MB Eindhoven, The Netherlands (e-mail: l.federico@tue.nl, r.w.v.d.hofstad@tue.nl)
REMCO VAN DER HOFSTAD
Affiliation:
Department of Mathematics and Computer Science, Eindhoven University of Technology, PO Box 513, 5600 MB Eindhoven, The Netherlands (e-mail: l.federico@tue.nl, r.w.v.d.hofstad@tue.nl)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We identify the asymptotic probability of a configuration model CMn(d) producing a connected graph within its critical window for connectivity that is identified by the number of vertices of degree 1 and 2, as well as the expected degree. In this window, the probability that the graph is connected converges to a non-trivial value, and the size of the complement of the giant component weakly converges to a finite random variable. Under a finite second moment condition we also derive the asymptotics of the connectivity probability conditioned on simplicity, from which follows the asymptotic number of simple connected graphs with a prescribed degree sequence.

MSC classification

Primary: 05C80: Random graphs 05A16: Asymptotic enumeration
Secondary: 05C30: Enumeration in graph theory 05C40: Connectivity 60C05: Combinatorial probability
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 26 , Issue 5 , September 2017 , pp. 660 - 680
Copyright
Copyright © Cambridge University Press 2017 

References

[1] Arratia, R. and Gordon, L. (1989) Tutorial on large deviations for the binomial distribution. Bull. Math. Biol. 51 125–131.Google Scholar
[2] Bollobás, B. (2001) Random Graphs, second edition, Vol. 73 of Cambridge Studies in Advanced Mathematics, Cambridge University Press.Google Scholar
[3] van der Hofstad, R. (2017) Random Graphs and Complex Networks, Vol. 1, Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press.Google Scholar
[4] Janson, S. (2008) The largest component in a subcritical random graph with a power law degree distribution. Ann. Appl. Probab. 18 1651–1668.Google Scholar
[5] Janson, S. (2009) The probability that a random multigraph is simple. Combin. Probab. Comput. 18 205–225.Google Scholar
[6] Janson, S. (2014) The probability that a random multigraph is simple, II. J. Appl. Probab. 51A 123–137.Google Scholar
[7] Janson, S. and Luczak, M. J. (2009) A new approach to the giant component problem. Random Struct. Alg. 34 197–216.Google Scholar
[8] Janson, S., Łuczak, T. and Ruciński, A. (2000) Random Graphs, Wiley-Interscience.CrossRefGoogle Scholar
[9] Łuczak, T. (1992) Sparse random graphs with a given degree sequence. In Random Graphs (Poznań 1989), Vol. 2, Wiley-Interscience, pp. 165–182.Google Scholar
[10] Molloy, M. and Reed, B. (1995) A critical point for random graphs with a given degree sequence. In Proc. Sixth International Seminar on Random Graphs and Probabilistic Methods in Combinatorics and Computer Science: Random Graphs '93 (Poznań 1993), Random Struct. Alg. 6 161–179.CrossRefGoogle Scholar
[11] Molloy, M. and Reed, B. (1998) The size of the giant component of a random graph with a given degree sequence. Combin. Probab. Comput. 7 295–305.CrossRefGoogle Scholar
[12] Wormald, N. C. (1981) The asymptotic connectivity of labelled regular graphs. J. Combin. Theory Ser. B 31 156–167.CrossRefGoogle Scholar