TY - JOUR

T1 - Critical window for connectivity in the configuration model

AU - Federico, L.

AU - van der Hofstad, R.W.

PY - 2017/9/1

Y1 - 2017/9/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85020113045&partnerID=8YFLogxK

U2 - 10.1017/S0963548317000177

DO - 10.1017/S0963548317000177

M3 - Article

AN - SCOPUS:85020113045

VL - 26

SP - 660

EP - 680

JO - Combinatorics, Probability and Computing

JF - Combinatorics, Probability and Computing

SN - 0963-5483

IS - 5

ER -