Counting a Fixed Pattern in a Random Graph
In the random graph \(G(n,p)\), each possible edge on \(n\) labeled vertices is included independently with probability \(p\). A fixed small graph \(H\) can occur in many different places, and a single occurrence can be described by several vertex-labeling maps. To calculate its expected count correctly, we must say whether we are counting those maps or counting the resulting copies only once.
Throughout, \(H\) is a fixed finite simple graph with \(v=|V(H)|\) vertices and \(e=|E(H)|\) edges. The random graph \(G(n,p)\) has vertex set \([n]=\{1,\ldots,n\}\), where \(n\) is a nonnegative integer and \(0\le p\le1\); every unordered pair of distinct vertices is an edge independently with probability \(p\). A copy of \(H\) below means a not-necessarily-induced subgraph isomorphic to \(H\). In particular, extra edges among the selected vertices do not prevent a copy: only the edges corresponding to \(E(H)\) need to be present.
An embedding is required to preserve edges, but not nonedges. Thus an edge of \(G(n,p)\) between two selected vertices may be unused by a particular copy. For example, a triangle contains three different two-edge path subgraphs, one for each choice of the omitted triangle edge. An induced copy has the stronger requirement that a pair is adjacent in \(H\) exactly when its image pair is adjacent in \(G(n,p)\).
Expected Number of Labeled Embeddings
For a nonnegative integer \(v\), write \((n)_v=n(n-1)\cdots(n-v+1)\), with \((n)_0=1\). If \(v>n\), this product is zero. There are \((n)_v\) injective maps from \(V(H)\) to \([n]\). For any one such map, the \(e\) different edges of \(H\) must all appear in the random graph. Independence gives probability \(p^e\) for this event.
Proof. For each injective map \(\phi:V(H)\to[n]\), let \(I_\phi\) equal \(1\) if \(\phi\) is an embedding and \(0\) otherwise. Then \(X_{\mathrm{emb}}=\sum_\phi I_\phi\), where the sum ranges over all \((n)_v\) injective maps. The \(e\) edges required by any fixed \(\phi\) are distinct, so independence of edge choices gives \(\mathbb{E}[I_\phi]=\Pr(I_\phi=1)=p^e\). By linearity of expectation, $$ \mathbb{E}[X_{\mathrm{emb}}]=\sum_\phi\mathbb{E}[I_\phi]=(n)_v p^e. $$ This argument does not require the events for different maps to be independent. If \(e=0\), the required event has probability \(1\), as expressed by the convention \(p^0=1\). \(\square\)
To count distinct copies, define \(\operatorname{Aut}(H)\) to be the set of bijections from \(V(H)\) to itself that preserve adjacency in both directions. Its size \(|\operatorname{Aut}(H)|\) is the number of symmetries of \(H\). For instance, a path on three vertices has two automorphisms: the identity and the map interchanging its endpoints.
Proof. Fix a realized graph \(G(n,p)\). Every distinct copy of \(H\) gives exactly \(|\operatorname{Aut}(H)|\) embeddings: once one embedding onto that copy is chosen, composing it with each automorphism gives an embedding onto the same copy. Conversely, if two embeddings describe the same copy, composing one with the inverse of the other gives an automorphism of \(H\). Thus the number of labeled embeddings is exactly \(|\operatorname{Aut}(H)|\) times the number of distinct copies, in every outcome. Taking expectations and applying the theorem proves the formula. \(\square\)
The division by the automorphism count is essential: a symmetric pattern has more maps describing each copy. The formula also accommodates isolated vertices. They contribute to \(v\), and hence to the number of injective choices, but not to \(e\), and hence impose no edge requirements.
Worked Counts
Worked Example: Triangle Copies in \(G(6,1/3)\)
Let \(H=K_3\), so \(v=3\) and \(e=3\). Its six injective maps into \([6]\) for each unordered choice of three images are counted by $$ (6)_3=6\cdot5\cdot4=120. $$ For each map, the three required edges are all present with probability $$ (1/3)^3=1/27. $$ Therefore the expected number of labeled embeddings is $$ 120\cdot\frac{1}{27}=\frac{40}{9}. $$ Every triangle has \(3!=6\) automorphisms, so the expected number of distinct triangle copies is $$ \frac{40/9}{6}=\frac{20}{27}. $$
Check: There are \(\binom{6}{3}=20\) possible image vertex sets. For any one set, its three possible edges are all present with probability \(1/27\). Thus the expected number of triangles is \(20\cdot(1/27)=20/27\), agreeing with the automorphism calculation.
Worked Example: Three-Vertex Paths in \(G(5,1/2)\)
Let \(H=P_3\), with two edges and one middle vertex. Here \(v=3\), \(e=2\), and \(|\operatorname{Aut}(H)|=2\), since the endpoints can be interchanged. The number of labeled embeddings is $$ (5)_3=5\cdot4\cdot3=60, $$ and the probability that both required edges occur for a particular map is $$ (1/2)^2=1/4. $$ The expected number of labeled embeddings is \(60\cdot(1/4)=15\). Dividing by the two automorphisms gives an expected \(15/2\) distinct path copies.
Check: A copy is determined by its middle vertex and its unordered pair of endpoints. There are \(5\binom{4}{2}=5\cdot6=30\) such choices. For each choice, its two incident edges occur with probability \(1/4\), giving \(30\cdot(1/4)=15/2\). We do not require the endpoints to be nonadjacent: if they are adjacent, the selected two edges still form a path subgraph.
Induced Copies Require Missing Edges Too
For an induced copy, the edges of \(H\) must be present and every pair of vertices that is a nonedge in \(H\) must remain a nonedge among the images. There are \(\binom{v}{2}-e\) such pairs. For one fixed injection, the required edge and nonedge events concern distinct pairs, so their joint probability is the product of their probabilities.
Proof. For each injective map \(\phi:V(H)\to[n]\), let \(J_\phi\) be \(1\) when \(\phi\) preserves both edges and nonedges, and \(0\) otherwise. The \(e\) required edges all occur with probability \(p^e\). The other \(\binom{v}{2}-e\) pairs all fail to be edges with probability \((1-p)^{\binom{v}{2}-e}\). These events are independent because they concern different pairs. Therefore \(\mathbb{E}[J_\phi]=p^e(1-p)^{\binom{v}{2}-e}\). Summing over \((n)_v\) injections proves the labeled formula. The same automorphism argument as above applies: an induced copy has exactly \(|\operatorname{Aut}(H)|\) embeddings onto it. \(\square\)
Worked Example: Induced Paths in \(G(4,1/2)\)
Again take \(H=P_3\), with \(v=3\), \(e=2\), and one nonedge among its three vertex pairs. The number of injections is $$ (4)_3=4\cdot3\cdot2=24. $$ For each injection, the two required edges and the one required nonedge have probability $$ (1/2)^2(1-1/2)^1=(1/4)(1/2)=1/8. $$ Thus the expected labeled induced count is \(24\cdot(1/8)=3\). Dividing by \(|\operatorname{Aut}(P_3)|=2\) gives \(3/2\) distinct induced paths.
Check: There are \(\binom{4}{3}=4\) possible vertex sets. On each, there are three choices for which vertex is the middle of an induced path. Each choice requires two edges and one nonedge, with probability \(1/8\). Hence the expected count is \(4\cdot3\cdot(1/8)=3/2\). Without the nonedge requirement, the expected number of ordinary path copies would instead be $$ \frac{(4)_3(1/2)^2}{2}=\frac{24\cdot(1/4)}{2}=3. $$
What the Expectation Does—and Does Not—Say
These formulas turn a fixed pattern into a direct calculation from its vertex count, edge count, and symmetries. The ordinary distinct-copy expectation depends on \(H\) through \(v\), \(e\), and \(|\operatorname{Aut}(H)|\); it does not require checking every possible location in the random graph. For induced copies, the number of required nonedges matters as well.
An expected count is an average over all outcomes, not a guarantee about any single outcome. For example, an expectation below \(1\) does not mean every realization has no copy, and an expectation above \(1\) does not ensure that every realization contains one. These formulas calculate the mean count; conclusions about the probability of seeing at least one copy require additional reasoning.
Common mistake: treating ordinary copies as induced. For a three-vertex path in \(G(4,1/2)\), using the induced formula when counting ordinary copies would give \(3/2\), because it incorrectly requires the endpoints to be nonadjacent. The ordinary-copy calculation is $$ \frac{(4)_3(1/2)^2}{|\operatorname{Aut}(P_3)|} =\frac{24\cdot(1/4)}{2}=3. $$ The induced count is \(3/2\), since it includes the additional requirement that the endpoint pair is a nonedge. Before applying a formula, decide whether extra edges among the chosen vertices are allowed.
Check Your Understanding
Use the definitions and formulas above; distinguish maps, ordinary copies, and induced copies in each answer.
- For a fixed graph \(H\) with \(v\) vertices and \(e\) edges, explain why one injective map is an embedding with probability \(p^e\).
- A graph \(H\) has three vertices and one edge. How many automorphisms does it have, and what formula gives its expected number of distinct copies in \(G(n,p)\)?
- Why does a triangle contain three distinct ordinary copies of \(P_3\), even though it contains no induced copy of \(P_3\)?
- State the expected labeled and distinct induced-copy counts in terms of \(n,v,e,p\), and \(|\operatorname{Aut}(H)|\).
- Explain why the indicator variables for different embeddings need not be independent for the expected-count formula to hold.