Why a Poisson Limit Appears
In a sparse random graph, a fixed pattern may occur only a bounded expected number of times, even as the number of available vertices grows. When occurrences are rare and overlapping occurrences are negligible, their count can behave like a Poisson random variable. Strict balance is the condition that lets us control those overlaps. This tutorial proves the limiting law and uses it to find the limiting probability that the pattern appears at least once.
Write \(G(n,p)\) for the random simple graph on vertex set \([n]=\{1,\dots,n\}\) in which each possible edge is included independently with probability \(p\). Let \(H\) be a fixed simple graph with \(h\ge 1\) vertices and \(k\ge 1\) edges. A copy of \(H\) means a subgraph isomorphic to \(H\); it need not be an induced subgraph. Copies are counted as distinct subgraphs, not as distinct ways of labelling their vertices.
Here a proper subgraph can omit vertices, edges, or both. In particular, a subgraph on all \(h\) vertices but with fewer than \(k\) edges is proper. Strict balance forces \(H\) to be connected: if it had multiple components, at least one component would have density at least the weighted average \(k/h\), contradicting strict balance. It also rules out isolated vertices. We take \(p=c n^{-1/m(H)}\), with fixed \(c>0\); for sufficiently large \(n\), this is a valid probability.
Let \(X_n\) be the number of copies of \(H\) in \(G(n,p)\). Write \(\operatorname{Aut}(H)\) for the set of adjacency-preserving bijections from \(V(H)\) to itself, and let \(a=|\operatorname{Aut}(H)|\). Each copy is represented by exactly \(a\) bijections from \(V(H)\) onto its vertex set. The candidate limiting mean is therefore
The Poisson Limit
We prove the result by factorial moments. For a nonnegative integer \(x\), its \(r\)th falling factorial is \((x)_r=x(x-1)\cdots(x-r+1)\), with \((x)_0=1\). The value \((X_n)_r\) counts ordered \(r\)-tuples of distinct copies. If the copies in such a tuple have disjoint vertex sets, their required edges are all distinct, so their joint occurrence probability is \(p^{rk}\).
The number of ordered \(r\)-tuples of vertex-disjoint copies is \((n)_{rh}/a^r\), where \((n)_{rh}=n(n-1)\cdots(n-rh+1)\). Indeed, first choose an ordered list of \(rh\) distinct vertices and assign them in order to the \(r\) labelled positions for copies of \(H\); then divide by \(a\) for each copy, since its \(a\) labellings represent the same subgraph. Consequently, the disjoint tuples contribute
because \(p=c n^{-h/k}\) and \((n)_{rh}/n^{rh}\to1\) for fixed \(r\).
We next show that overlapping tuples contribute a quantity tending to zero. Consider the union of the copies in an ordered tuple, with \(v\) vertices and \(e\) distinct required edges. Its contribution is at most a constant times \(n^v p^e\): for any fixed pattern of identifications among the at most \(rh\) vertices, there are at most \(n^v\) ways to choose its vertices, and the probability all its \(e\) edges appear is \(p^e\). There are only finitely many such identification patterns for fixed \(r\) and \(H\).
To bound \(e\), expose the copies in order. If the next copy shares \(s\) vertices and \(t\) edges with the union already exposed, adding it changes the vertex count by \(h-s\) and the edge count by \(k-t\). The change in \(e-(k/h)v\) is therefore $$ (k-t)-\frac{k}{h}(h-s)=\frac{k}{h}s-t. $$ If the intersection is a proper subgraph of this copy, strict balance gives \(t/s<k/h\) for \(s\ge1\), so this change is positive. If \(s=0\), the change is zero. If all \(h\) vertices and all \(k\) edges are already in the union, the change is also zero.
For a tuple that contains an overlapping pair of distinct copies, at some stage the union has strictly positive \(e-(k/h)v\). To see why, consider the first copy in the ordering that meets an earlier copy. If its intersection is proper, the displayed change is positive. If all of its edges are already present, the earlier union must already have positive surplus: a union of vertex-disjoint copies cannot contain a distinct copy of the connected graph \(H\). Subsequent additions never decrease the surplus, by the same calculation. Thus every overlapping tuple has \(e-(k/h)v>0\).
Its contribution is bounded by a constant times $$ n^v p^e =c^e n^{\,v-(h/k)e} =c^e n^{-(h/k)(e-(k/h)v)}, $$ which tends to zero. Since there are finitely many patterns for each fixed \(r\), all overlapping tuples together contribute \(o(1)\). We have proved that \(\mathbb{E}(X_n)_r\to\lambda^r\) for every fixed \(r\).
For completeness, these factorial-moment limits imply the asserted probabilities as follows. For integers \(x,j\ge0\) and \(L\ge j\), define $$ S_L(x)=\sum_{r=j}^{L}(-1)^{r-j}\binom{r}{j}\binom{x}{r}. $$ If \(x<j\), this is zero. If \(x=j\), it is one. If \(x>j\), use \(\binom{r}{j}\binom{x}{r}=\binom{x}{j}\binom{x-j}{r-j}\); the alternating partial binomial sum shows that \(S_L(x)\) is nonnegative when \(L-j\) is even and nonpositive when \(L-j\) is odd. Hence, for even \(L-j\), \(S_L(x)\ge \mathbf{1}_{\{x=j\}}\), and for odd \(L-j\), \(S_L(x)\le \mathbf{1}_{\{x=j\}}\). Taking expectations with \(x=X_n\), then letting \(n\to\infty\), gives the corresponding upper and lower bounds with \(\mathbb{E}\binom{X_n}{r}\to\lambda^r/r!\). Finally let \(L\to\infty\) through even and odd values. Both bounds converge to $$ \sum_{r=j}^{\infty}(-1)^{r-j}\binom{r}{j}\frac{\lambda^r}{r!} =\frac{\lambda^j}{j!}\sum_{s=0}^{\infty}\frac{(-\lambda)^s}{s!} =e^{-\lambda}\frac{\lambda^j}{j!}. $$ This proves the theorem. \(\square\)
Worked Examples
Worked Example: A Three-Vertex Path
Let \(H=P_3\), with vertex set \(\{1,2,3\}\) and edge set \(\{12,23\}\). It has \(h=3\), \(k=2\), and density \(2/3\). A proper subgraph with two vertices has at most one edge and density at most \(1/2\); one with one vertex has density zero. Thus \(H\) is strictly balanced. Its only nonidentity automorphism swaps the endpoints, so \(a=2\).
Take \(p=2n^{-3/2}\), which is \(c n^{-h/k}\) with \(c=2\). The number of candidate copies on each three-vertex set is three, one for each choice of middle vertex. Therefore $$ \mathbb{E}X_n=3\binom{n}{3}p^2 =\frac{n(n-1)(n-2)}{2}\cdot4n^{-3} =2\left(1-\frac1n\right)\left(1-\frac2n\right) \longrightarrow 2. $$ The theorem gives \(\lambda=c^k/a=2^2/2=2\), agreeing with this direct calculation. The limiting probability of at least one copy is \(1-e^{-2}\).
Check: counting injections of \(P_3\) would give \(6\binom{n}{3}\) representations, twice the number of copies. Dividing by \(a=2\) gives \(3\binom{n}{3}\), as used above.
Worked Example: A Complete Bipartite Pattern
Let \(H=K_{2,3}\), with vertex set \(\{u_1,u_2,v_1,v_2,v_3\}\) and edge set consisting of all six \(u_i v_j\). Here \(h=5\), \(k=6\), and \(k/h=6/5\). For a subgraph using \(a\) vertices from the first part and \(b\) from the second, its density is at most \(ab/(a+b)\), with density zero if either count is zero. For \(a\le2\), \(b\le3\), every proper choice has density at most \(1\): the largest proper value is \(2\cdot2/(2+2)=1\). Omitting edges can only lower density. Thus \(H\) is strictly balanced. Its automorphisms permute the two vertices in one part and the three in the other, so \(a=2!\,3!=12\).
Choose \(c=1\), so \(p=n^{-5/6}\). The limiting mean is $$ \lambda=\frac{1^6}{12}=\frac1{12}. $$ The limiting probability of at least one \(K_{2,3}\) copy is \(1-e^{-1/12}\). The exponent in the expected count also checks the threshold: there are on the order of \(n^5\) choices of five vertices, and the six required edges contribute \(p^6=n^{-5}\), leaving a bounded expected count.
Check: the exact number of labelled copies on a chosen five-vertex set is \(5!/(2!\,3!)=10\), since the two sides can be exchanged only when their sizes agree, which they do not. Equivalently, choose the two-vertex side in \(\binom52=10\) ways. Dividing the \(5!=120\) bijections by \(a=12\) also gives \(10\).
Worked Example: Overlapping Paths Become Negligible
Return to \(P_3\), with the same \(p=2n^{-3/2}\), and examine ordered pairs of distinct copies. If they share \(s\) vertices and \(t\) edges, their union has \(v=6-s\) vertices and \(e=4-t\) edges. There are only finitely many possible intersection patterns, so for each the contribution is at most a fixed constant times \(n^v p^e\).
If \(s=1\), then \(t=0\), so \(v=5,e=4\), and $$ n^5p^4=n^5(2n^{-3/2})^4=16n^{-1}. $$ If \(s=2,t=0\), then \(v=4,e=4\), and \(n^4p^4=16n^{-2}\). If \(s=2,t=1\), then \(v=4,e=3\), and $$ n^4p^3=n^4(2n^{-3/2})^3=8n^{-1/2}. $$ Finally, if \(s=3\), distinct paths on the same three vertices share one edge, so \(v=3,e=3\), and \(n^3p^3=8n^{-3/2}\). Each quantity tends to zero, so overlapping pairs make no contribution in the limit.
Check: disjoint ordered pairs contribute \((n)_6p^4/2^2\), which tends to \(2^4/4=4\). This equals \(\lambda^2\) for \(\lambda=2\), as the factorial-moment calculation requires.
Appearance Probability and a Common Pitfall
The event that \(H\) appears is \(X_n\ge1\). Since \(X_n\) is a nonnegative integer, $$ \Pr(X_n\ge1)=1-\Pr(X_n=0)\longrightarrow 1-e^{-\lambda} =1-\exp\left(-\frac{c^k}{a}\right). $$ This is the limiting appearance probability at the critical scale. The parameter \(c\) affects the limit through \(c^k\), while symmetries of \(H\) affect it through the automorphism factor \(a\).
Common mistake: using the expected count as the appearance probability. In the \(P_3\) example with \(c=2\), the expected number tends to \(2\), but a probability cannot equal \(2\). The correct limiting probability is \(1-e^{-2}\), obtained from the zero-count probability in the Poisson limit. Expectation alone does not determine an appearance probability; the theorem supplies the additional distributional information.
Strict balance is essential to this argument: it ensures that any overlap creates a union denser than the critical density, making overlapping tuples vanish in the limit. Without that condition, overlap contributions may remain significant, and this proof does not establish a Poisson limit.
Check Your Understanding
Use the definitions and proof above to answer the following questions.
- For a strictly balanced graph with \(h\) vertices, \(k\) edges and \(a\) automorphisms, what choice of \(p\) gives limiting mean \(c^k/a\)?
- Why does counting injective maps from \(V(H)\) overcount copies, and by what factor?
- For two copies whose union has \(v\) vertices and \(e\) edges, write the power of \(n\) in the order of \(n^v p^e\) at the critical scale.
- For \(P_3\) and \(c=2\), calculate the limiting probability that at least one copy appears.
- Why does a bounded expected copy count by itself not prove a Poisson limit?