What is The Probability That A Random Graph With A Given Degree Sequence is Connected?

Abstract

An $n$-tuple $D=(d(1),\dots ,d(n))$ is a \emph{feasible degree sequence} if there is a graph on $\{1,\dots ,n\}$ such that $i$ has degree $d(i)$. Any such graph will have $m={\sum }_{i=1}^{n}d(i)/2$ edges. Letting $G(D)$ be a graph chosen uniformly from those with the given degree sequence, we upper-bound the probability that $G(D)$ is disconnected based on the number of vertices of degree $d$ for small $d$, and develop a powerful tool for proving such bounds. If there are any vertices of degree zero the probability $G$ is disconnected is $1$, so we assume there are no such vertices. Our results then imply that if there are $o(\sqrt{m})$ vertices of degree $1$ and $o(m)$ vertices of degree 2 then with high probability $G$ is connected, while if there are no vertices of degree 1 or 2 then the probability $G$ is disconnected is $O(\frac{n^4}{m^6})$.

28 pages, 10 figures