Connectivity Thresholds in G(n,m)

The Connectivity Window with a Fixed Number of Edges

In the model \(G(n,p)\), each possible edge is chosen independently. In \(G(n,m)\), by contrast, the graph is selected uniformly from all simple graphs with exactly \(m\) edges. At the connectivity threshold, the two models have the same limiting connectivity probability, but independence cannot be assumed in the fixed-edge model: selecting one edge changes the conditional probabilities for the others.

We study the window in which the average degree is approximately \(\log n+c\), for a fixed real constant \(c\). Since a graph with \(m\) edges has average degree \(2m/n\), this corresponds to \(m\) near \(\frac n2(\log n+c)\). To allow for integer edge counts, throughout the asymptotic argument let \(m=m_n=\left\lfloor\frac n2(\log n+c)\right\rfloor\). Rounding changes the average degree by at most \(2/n\), which tends to zero.

For this choice of \(m\), the probability that a particular possible edge is selected is \[ \frac mN=\frac{2m}{n(n-1)} =\frac{\log n+c+o(1)}{n-1}. \] This expression is a marginal probability, not an assertion that edge choices are independent. Our goal is to show that, as \(n\) tends to infinity,

Isolated Vertices in the Fixed-Edge Model

A vertex is isolated if it has degree zero. Let \(X\) be the number of isolated vertices. For any specified set of \(k\) vertices, the number of possible edges incident to at least one of them is \[ kn-\binom{k}{2}=kn-\frac{k(k-1)}2. \] Indeed, there are \(k(n-k)\) edges from the set to its complement and \(\binom{k}{2}\) edges within the set. Thus the probability that all \(k\) specified vertices are isolated is the probability that all \(m\) selected edges come from the other \(\binom{n-k}{2}\) edges.

We use this exact ratio to find the limiting distribution of \(X\). For a nonnegative integer \(x\), write \((x)_k=x(x-1)\cdots(x-k+1)\), with \((x)_0=1\). This counts ordered choices of \(k\) distinct objects from \(x\) objects. By summing over ordered sets of \(k\) vertices,

For each fixed \(k\), the ratio has the asymptotic form \(n^{-k}e^{-kc}(1+o(1))\). To see why, put \(a=kn-\binom{k}{2}\), the number of forbidden edges. The ratio can be written as \[ \prod_{i=0}^{m-1}\left(1-\frac{a}{N-i}\right). \] Here \(m=O(n\log n)\), \(N=\binom n2\), and \(a=O(n)\). Taking logarithms, the sum of the first-order terms is \[ -\sum_{i=0}^{m-1}\frac{a}{N-i} =-\frac{am}{N}+o(1) =-k(\log n+c)+o(1). \] The error from replacing \(1/(N-i)\) by \(1/N\) is \(O(am^2/N^2)=o(1)\); the sum of the squared terms in the logarithmic expansion is \(O(ma^2/N^2)=o(1)\). Exponentiating gives the stated ratio. Since \((n)_k/n^k\to1\), it follows that \[ \mathbb E[(X)_k]\longrightarrow (e^{-c})^k \] for every fixed \(k\).

Proof. Let \(\lambda=e^{-c}\), which is positive for every fixed real \(c\). For each fixed \(j\), the identity \(\binom Xj=(X)_j/j!\) and the factorial-moment calculation give \[ \mathbb E\binom Xj\longrightarrow\frac{\lambda^j}{j!}. \] For any nonnegative integer-valued \(X\), the inclusion-exclusion (Bonferroni) inequalities bound \(\mathbb P(X=0)\) between the alternating partial sums of \(\sum_{j\ge0}(-1)^j\mathbb E\binom Xj\), with successive even and odd truncations giving upper and lower bounds. Fix a truncation index and let \(n\) tend to infinity; each finite partial sum then tends to the corresponding partial sum of \(\sum_{j\ge0}(-1)^j\lambda^j/j!\). Letting the truncation index tend to infinity, both bounds converge to the exponential series \(e^{-\lambda}\). Therefore \(\mathbb P(X=0)\to e^{-\lambda}=\exp(-e^{-c})\). \(\square\)

Why Other Disconnected Components Become Unlikely

Having no isolated vertices does not, by itself, imply connectivity. A disconnected graph with no isolated vertices has a connected component of size \(s\) for some \(2\le s\le n/2\): take a smallest component, whose size is at most \(n/2\). We now bound the probability that any such component exists.

Proof. Fix a set \(S\) of \(s\) vertices. If \(S\) is a component, then no edge from \(S\) to its complement is selected, and the graph on \(S\) is connected. A connected graph contains a spanning tree: repeatedly delete an edge from a cycle, which preserves connectivity, until no cycle remains. For each fixed \(S\), the number of possible spanning trees is at most \(s^{s-1}\). To obtain this upper bound, fix a root; each tree specifies, for every other vertex, its parent on the unique path to the root, and there are at most \(s\) choices for each of the \(s-1\) parents.

For one candidate tree, let \(b=s-1\) be its number of edges and \(a=s(n-s)\) the number of edges crossing from \(S\) to its complement. The probability that all \(b\) tree edges are selected is at most \((m/N)^b\), by revealing those edges in sequence: each conditional selection probability is at most \(m/N\). Conditional on their selection, the remaining \(m-b\) edges are a uniform subset of the other \(N-b\) edges. Revealing the \(a\) crossing edges in sequence, the probability each is absent is at most \(\exp(-(m-b)/(N-b))\). Indeed, at each reveal the conditional probability of absence is at most \(1-(m-b)/(N-b)\le \exp(-(m-b)/(N-b))\). Therefore the probability that the candidate tree is selected and every crossing edge is absent is at most \[ \left(\frac mN\right)^{s-1} \exp\left(-\frac{s(n-s)(m-s+1)}{N-s+1}\right). \] A union bound over sets \(S\) and their candidate trees bounds the probability of a component of size \(s\) by \[ \binom ns s^{s-1}\left(\frac mN\right)^{s-1} \exp\left(-\frac{s(n-s)(m-s+1)}{N-s+1}\right). \]

For all sufficiently large \(n\), with \(c\) fixed, \(m/N\le 2\log n/n\), and \((m-s+1)/(N-s+1)\ge(\log n-C)/n\) uniformly for \(2\le s\le n/2\), for some constant \(C\) depending only on \(c\). Using \(\binom ns\le(en/s)^s\), the displayed bound is at most \[ \frac{n^{\,1-s+s^2/n}}{s}\,K^s(\log n)^{s-1}, \] where \(K\) is a constant independent of \(s,n\). For \(2\le s\le n/\log n\), we have \(s^2/n\le s/\log n\), so the sum of these bounds is \(O(\log n/n)\): after extracting a bounded factor, successive terms are bounded by a geometric series with ratio at most \(Ke\log n/n\), which tends to zero. For \(n/\log n\le s\le n/2\), we have \(1-s+s^2/n\le1-s/2\). The sum is then bounded by a geometric tail with ratio \(K\log n/\sqrt n\), starting at \(s\ge n/\log n\), and tends to zero. Thus the sum over all \(2\le s\le n/2\) tends to zero, proving the lemma. \(\square\)

The Connectivity Limit

Proof. For \(n\ge2\), a connected graph has no isolated vertices, so its probability is at most the probability of having no isolated vertices. Conversely, if a graph has no isolated vertices but is disconnected, it has a component of size between \(2\) and \(n/2\), as used in the lemma. Thus the difference between the probability of having no isolated vertices and the probability of being connected is at most the probability in the lemma, which tends to zero. The proposition gives the limiting probability of having no isolated vertices as \(\exp(-e^{-c})\). The two probabilities therefore have the same limit. \(\square\)

Common Pitfall: Treating Edges as Independent

In \(G(n,m)\), the edge indicators are not independent: the total number selected is fixed. For example, after one edge is known to be present, the conditional probability that another specified edge is present is \((m-1)/(N-1)\), not \(m/N\). A calculation that multiplies marginal probabilities as if all edge choices were independent may therefore give an incorrect exact probability. Use the uniform-subset ratio for isolation events, as above.

The asymptotic conclusion has two distinct ingredients. First, isolated vertices have a limiting Poisson count with mean \(e^{-c}\), so the chance of none approaches \(\exp(-e^{-c})\). Second, components of size at least two but at most \(n/2\) occur with probability tending to zero. The second step is essential: the absence of isolated vertices alone is not a definition or a guarantee of connectivity for an individual graph.