Three Similar-Sounding Claims That Are Not the Same
Random graph calculations often begin with a simple question: how likely is a particular edge, subgraph, or graph property? A common source of mistakes is treating two different random graph models as though they had the same independence structure. Another is reading an expected number of subgraphs as if it were the probability that at least one appears. A third is using “threshold” and “critical window” interchangeably.
We will separate these claims and show what can safely be calculated in each setting. Throughout, graphs are finite and simple. Write \(N=\binom{n}{2}\) for the number of possible edges on a fixed vertex set of size \(n\).
For \(0<p<1\), conditioning \(G(n,p)\) on having exactly \(m\) edges gives \(G(n,m)\). Indeed, every particular graph with \(m\) edges has probability \(p^m(1-p)^{N-m}\) before conditioning. These probabilities are equal across all such graphs, so the conditional distribution is uniform. The conditioning event has positive probability for \(0\le m\le N\).
Fixed Edge Count Creates Dependence
In \(G(n,p)\), distinct edge indicators are independent by definition. In \(G(n,m)\), once the total number of edges is fixed, including one edge leaves fewer places for the others. For a set of \(k\) distinct specified edges, the probability they are all present is
when \(k\le m\) and \(k\le N\); it is zero if \(k>m\). To obtain the formula, reveal the specified edges in order. Given that the first \(i\) are present, there are \(m-i\) edges left to choose from the \(N-i\) unexposed possibilities, so the next specified edge is present with conditional probability \((m-i)/(N-i)\).
Proof. Each edge is included with probability \(m/N\), so \(\mathbb E[X_e]=\mathbb E[X_f]=m/N\). The joint inclusion formula with \(k=2\) gives \(\mathbb E[X_eX_f]=m(m-1)/(N(N-1))\). Therefore $$ \operatorname{Cov}(X_e,X_f)=\frac{m(m-1)}{N(N-1)}-\frac{m^2}{N^2} =-\frac{m(N-m)}{N^2(N-1)}. $$ Since \(0\le m\le N\), this is nonpositive. It is zero in the cases \(m=0\) and \(m=N\), when the graph is deterministic. \(\square\)
Worked Example: Two Edges in \(G(5,4)\)
Take \(V=\{1,2,3,4,5\}\), with all ten possible pairs as candidate edges, and choose \(E\) uniformly among the four-edge subsets. Let the specified edges be \(12\) and \(13\). Each has inclusion probability \(4/10=2/5\). If they were independent, their joint probability would be \((2/5)^2=4/25\).
In fact, the fixed-edge-count formula gives $$ \Pr(12,13\in E)=\frac{4}{10}\cdot\frac{3}{9}=\frac{12}{90}=\frac{2}{15}. $$ The conditional probability that \(13\) is present given that \(12\) is present is \(3/9=1/3\), not \(2/5\). Numerically, \(2/15=10/75\) while \(4/25=12/75\), so the joint probability is smaller than the independent-edge calculation.
Check: the covariance formula gives \(-4(10-4)/(10^2\cdot9)=-24/900=-2/75\). The joint probability minus the product of the marginal probabilities is \(2/15-4/25=10/75-12/75=-2/75\), in agreement.
The marginal probability \(m/N\) can be a useful approximation to \(p\) when comparing the models, but it does not make the edges independent in \(G(n,m)\). In particular, for a fixed set of several edges, use the joint inclusion formula rather than multiplying the marginal probability once per edge.
Expected Counts Are Not Appearance Probabilities
Let \(H\) be a fixed simple graph with \(v\) vertices and \(e\) edges. Count copies as subgraphs, not necessarily induced subgraphs: extra edges among the selected vertices do not prevent a copy of \(H\). Let \(X_H\) be the number of such copies in the random graph. There are \((n)_v/|\operatorname{Aut}(H)|\) possible copies when \(n\ge v\), where \(\operatorname{Aut}(H)\) is the set of vertex permutations preserving adjacency.
For each possible copy, its \(e\) required edges occur with probability \(p^e\) in \(G(n,p)\). In \(G(n,m)\), the probability is \((m)_e/(N)_e\) when \(e\le m\). Adding the indicator of each possible copy and taking expectations therefore gives
The reason this is an expectation formula is linearity of expectation: it does not require different copies of \(H\) to occur independently. But the formula gives a mean count, not generally the probability that the count is positive.
Proof. For every outcome, \(X\ge \mathbf{1}_{\{X\ge1\}}\), where the indicator is \(1\) if \(X\ge1\) and \(0\) otherwise. Taking expectations proves the inequality. The difference is \(\mathbb E[X-\mathbf{1}_{\{X\ge1\}}]\). Its integrand is nonnegative and is positive exactly when \(X\ge2\). The difference is zero exactly when \(\Pr(X\ge2)=0\). \(\square\)
Worked Example: Triangles in \(G(4,5)\)
Let \(V=\{1,2,3,4\}\), whose six possible edges are \(12,13,14,23,24,34\). Choose \(E\) uniformly among the five-edge subsets. The four possible triangles are the three-edge sets on \(\{1,2,3\}\), \(\{1,2,4\}\), \(\{1,3,4\}\), and \(\{2,3,4\}\).
For each specified triangle, the probability all three edges are present is $$ \frac{5}{6}\cdot\frac{4}{5}\cdot\frac{3}{4}=\frac{1}{2}. $$ There are four triangles, so \(\mathbb E[X]=4(1/2)=2\). This is not the probability of seeing a triangle.
To find that probability, each outcome omits exactly one of the six possible edges, giving six equally likely outcomes. If the omitted edge is \(12\), the triangles on \(\{1,2,3\}\) and \(\{1,2,4\}\) are absent, while those on \(\{1,3,4\}\) and \(\{2,3,4\}\) remain. The same count holds whichever edge is omitted: every outcome has exactly two triangles. Thus \(\Pr(X\ge1)=6/6=1\), whereas \(\mathbb E[X]=2\).
Check: summing the count over outcomes gives \(6\cdot2=12\) triangle occurrences. Summing instead over the four possible triangles gives \(4\cdot3=12\), because each triangle is present in the three outcomes that omit an edge outside it. Both counts agree.
The inequality \(\Pr(X_H\ge1)\le\mathbb E[X_H]\) is often useful: a small expected count implies a small probability of any copy. The reverse inference is not valid from the expectation alone. When multiple copies can occur together, an expectation larger than one is especially incapable of serving as a probability.
Threshold Scale Versus Critical Window
A threshold describes a broad change in the probability of a graph property as the parameter varies with \(n\). For an increasing property, a scale \(p_c(n)\) is a threshold scale if probabilities tend to zero when \(p/p_c\to0\) and tend to one when \(p/p_c\to\infty\). This description does not by itself identify the finer range in which the probability changes from near zero to near one.
For connectivity in \(G(n,p)\), the threshold scale is \((\log n)/n\), while the critical window is parameterized by \(p=(\log n+c)/n\) for fixed real \(c\). Earlier material on isolated vertices at the connectivity window establishes that the probability of no isolated vertices tends to \(\exp(-e^{-c})\); the connectivity-window result gives the same limiting probability for connectivity. These are standard window results, not consequences of knowing only the threshold scale.
Worked Example: Expected Isolated Vertices in the Connectivity Window
In \(G(n,p)\), a vertex is isolated if all its \(n-1\) incident edges are absent. Set \(p=(\log n+c)/n\), where \(c\) is fixed and \(n\) is large enough that \(0\le p\le1\). If \(Z\) counts isolated vertices, then linearity of expectation gives $$ \mathbb E[Z]=n(1-p)^{n-1}. $$ Taking logarithms and substituting the parameter gives $$ \log\mathbb E[Z]=\log n+(n-1)\log\left(1-\frac{\log n+c}{n}\right). $$ As \(n\to\infty\), \(\log(1-x)=-x+O(x^2)\) for \(x\to0\), and here \((n-1)x^2=O((\log n)^2/n)\to0\). Therefore $$ \log\mathbb E[Z]=\log n-(\log n+c)+o(1)=-c+o(1), \qquad \mathbb E[Z]\longrightarrow e^{-c}. $$
This calculation identifies a finite, nonzero limiting mean for each fixed \(c\). It does not, by itself, calculate the probability that \(Z=0\): a mean does not determine a full distribution. The cited window result supplies that further conclusion. Varying \(c\) changes the limiting behavior within the same threshold-scale parameterization; saying only \(p\) is “of order \((\log n)/n\)” loses this information.
Check: with \(c=0\), the displayed limit for the mean is \(e^0=1\). With \(c=\log 2\), it is \(e^{-\log 2}=1/2\). These are expectations, not probabilities of having an isolated vertex.
Common Mistakes and Safe Checks
Mistake: multiplying marginal edge probabilities in \(G(n,m)\). In the \(G(5,4)\) example, a mistaken calculation treats the two edges as independent and obtains \((2/5)^2=4/25\). The correct calculation is \((4/10)(3/9)=2/15\), because after the first specified edge is included, only three of the nine remaining possible edges can be selected.
Mistake: treating an expected count as a probability. If \(X\) counts copies, then \(\mathbb E[X]\) weights outcomes containing two copies twice and outcomes containing three copies three times. The event \(X\ge1\) counts each such outcome only once. First use \(\Pr(X\ge1)\le\mathbb E[X]\); equality requires that at most one copy can occur in every outcome of positive probability.
Mistake: calling the whole threshold-scale range the critical window. A threshold scale gives a leading-order location. A critical window requires a finer parameterization and a statement of the limiting probabilities there. For connectivity, the fixed offset \(c\) in \((\log n+c)/n\) matters: omitting it discards the window information.
When checking a random-graph claim, ask three separate questions: Is the model \(G(n,p)\) or \(G(n,m)\)? Is the quantity an expected count or an event probability? Is the statement about a threshold scale or a specified critical window? Keeping these distinctions explicit prevents a correct formula in one setting from being misapplied in another.
Check Your Understanding
For each question, identify the model and the quantity before calculating.
- In \(G(6,3)\), what is the probability that two particular distinct edges are both present? Compare it with the product of their marginal probabilities.
- Explain why the expected number of copies of a fixed graph can be calculated by summing indicator expectations even when different copies overlap.
- Give a condition on an integer-valued copy count \(X\) that makes \(\Pr(X\ge1)=\mathbb E[X]\), and justify it.
- In \(G(n,p)\), write the exact probability that a specified vertex is isolated, then give the expected number of isolated vertices.
- In one sentence, distinguish what a threshold scale says from what a critical window says.