Worked Threshold Calculations for Cycles and Cliques

From a Fixed Graph to Its Appearance Scale

For a fixed graph, its appearance scale is the probability at which the expected number of copies in a random graph changes from small to large. Cycles and complete graphs provide two useful families: their scales are determined by different edge-to-vertex ratios, and their expected counts can be calculated explicitly. At the critical scale the expectation stays bounded, so its value alone does not describe the full probability of appearance.

Throughout, \(G(n,p)\) is the random simple graph on \(n\) labelled vertices in which each possible edge is included independently with probability \(p\). A copy of a fixed graph \(H\) means a subgraph isomorphic to \(H\); it need not be an induced subgraph. Write \(v=|V(H)|\), \(e=|E(H)|\), and let \(\operatorname{aut}(H)\) be the number of automorphisms of \(H\). We count copies without distinguishing different labelings of the same copy.

The scale follows from counting possible copies and asking that their expected number be of constant order. For each injection of \(V(H)\) into the \(n\) vertices, all \(e\) required edges occur with probability \(p^e\). Each unlabelled copy is counted \(\operatorname{aut}(H)\) times by these injections. Therefore, if \(X_H\) denotes the number of copies,

For fixed \(H\), \((n)_v\) is asymptotic to \(n^v\). Writing \(p=c n^{-v/e}\) for fixed \(c>0\) makes \(n^v p^e=c^e\), so the expected count approaches a finite positive constant. If \(p=o(n^{-v/e})\), the expectation tends to zero; if \(p/n^{-v/e}\) tends to infinity, the expectation tends to infinity. These calculations suggest the scale, but the last statement alone does not prove that a copy appears with high probability.

Cycles: The Scale \(n^{-1}\)

For a fixed cycle \(C_k\), where \(k\ge3\), use the explicit graph with vertices \(\{1,\ldots,k\}\) and edges \(12,23,\ldots,(k-1)k,k1\). It has \(v=e=k\), so its suggested scale is \(n^{-k/k}=n^{-1}\). The cycle has \(2k\) automorphisms: there are \(k\) choices for the image of a starting vertex and two choices for the direction around the cycle. Consequently, if \(X_{C_k}\) counts unlabelled cycle copies,

Cliques: The Scale \(n^{-2/(r-1)}\)

For a fixed complete graph \(K_r\), take vertices \(\{1,\ldots,r\}\) and all edges \(ij\) with \(1\le i<j\le r\). There are \(v=r\) vertices and \(e=\binom r2=r(r-1)/2\) edges. Every permutation of the vertices is an automorphism, so \(\operatorname{aut}(K_r)=r!\). The expected number of unlabelled copies is therefore

Setting the power of \(n\) in the approximation to zero gives \(r-\gamma r(r-1)/2=0\) when \(p=n^{-\gamma}\). Solving yields \(\gamma=2/(r-1)\). Thus the suggested scale for \(K_r\) is \(n^{-2/(r-1)}\). Larger cliques have more required edges per vertex, so their critical probability is a larger power of \(n^{-1}\) with a smaller exponent.

Why the Expected Count Describes Appearance

For any nonnegative integer-valued count \(X\), \(\Pr(X\ge1)\le\mathbb{E}X\): the value of \(X\) is at least \(1\) whenever \(X\ge1\). Thus, below the suggested scale, the expected counts just calculated imply that the probability of at least one copy tends to zero. At the critical scale, for cycles and cliques, the Poisson limit for strictly balanced subgraphs gives more information: if \(p=c n^{-v/e}\) with fixed \(c>0\), then \(X_H\) converges in distribution to a Poisson random variable with mean \(c^e/\operatorname{aut}(H)\). This is the standard Poisson-limit result for strictly balanced subgraphs. In particular, the limiting probability of at least one copy is \(1-\exp(-c^e/\operatorname{aut}(H))\), not necessarily \(1\).

To justify appearance above the scale, we use a second-moment argument. It applies to a fixed strictly balanced graph \(H\). Set \(a=v/e\), and suppose \(p=n^{-a}w(n)\), where \(w(n)\) tends to infinity. The expectation satisfies \(\mathbb{E}X_H=\Theta(w^e)\), so it tends to infinity. We show that the relative variance tends to zero.

Proof. Write \(X_H\) as the sum of indicator variables, one for each unlabelled candidate copy. Two indicators are independent if their copies share no edge, even if they share vertices, because the edge choices in \(G(n,p)\) are independent. For a pair sharing \(t\ge1\) edges, let \(s\) be the number of shared vertices. There are only finitely many overlap patterns, since \(H\) is fixed. A pattern with \(s\) shared vertices has \(O(n^{2v-s})\) pairs of candidate copies, and the probability that both copies occur is \(p^{2e-t}\). Its contribution to the variance, divided by \((\mathbb{E}X_H)^2=\Theta(n^{2v}p^{2e})\), is at most \(O(n^{-s}p^{-t})\).

Let \(F\) be the graph formed by the \(t\) shared edges and their endpoints, and let \(s_0\) be its number of vertices. Then \(s_0\le s\). If the two copies do not have the same entire edge set, \(F\) is a proper subgraph of \(H\). Strict balance gives \(t/s_0<e/v=1/a\), hence \(at<s_0\). Since \(p=n^{-a}w(n)\),

If the copies have the same entire edge set, their contribution is part of the diagonal variance sum and, after division by \((\mathbb{E}X_H)^2\), is \(O(1/\mathbb{E}X_H)=O(w(n)^{-e})\), which also tends to zero. Summing over the finitely many overlap patterns shows that \(\operatorname{Var}(X_H)/(\mathbb{E}X_H)^2\) tends to zero. Chebyshev's inequality gives \(\Pr(X_H=0)\le\operatorname{Var}(X_H)/(\mathbb{E}X_H)^2\), so this probability tends to zero. Therefore a copy appears with probability tending to \(1\). \(\square\)

Applying the Result to Cycles and Cliques

Both families satisfy the strict-balance condition needed above. For \(C_k\), any proper edge-bearing subgraph is a union of paths, and each path has one more vertex than edge. Summing over its path components gives fewer edges than vertices. Its edge-to-vertex ratio is therefore less than \(k/k=1\).

For \(K_r\), consider a proper subgraph with \(s\) vertices. If \(s<r\), it has at most \(\binom{s}{2}\) edges, so its edge-to-vertex ratio is at most \((s-1)/2<(r-1)/2\). If it has all \(r\) vertices but is missing an edge, its ratio is also strictly less than \(\binom r2/r=(r-1)/2\). Thus \(C_k\) and \(K_r\) are strictly balanced. The theorem proves that \(C_k\) appears with probability tending to \(1\) when \(p\) is much larger than \(n^{-1}\), and \(K_r\) does so when \(p\) is much larger than \(n^{-2/(r-1)}\).

Common Pitfall: Counting Labelings as Different Copies

A common error is to use \(n^v p^e\) as the expected number of unlabelled copies. This gets the exponent and the scale right, but omits the automorphism factor and gives the wrong critical mean. For the triangle just considered, the incorrect calculation gives \(n^3(2/n)^3=8\). The correct asymptotic mean is \(8/6=4/3\), because each triangle has six labelings. At the critical scale that constant matters: it determines the parameter of the Poisson limit.

A second caution is that a diverging expectation by itself does not prove appearance with probability tending to \(1\). The second-moment argument supplies that additional step for these strictly balanced graphs. The useful summary is: