Expected Counts of Short Cycles

Counting Cycles in a Random Graph

In the binomial random graph \(G(n,p)\), each possible edge is chosen independently with probability \(p\). A useful way to study short cycles is to count how many cycles of each length the random graph contains, then add those counts. The calculation combines two ingredients: the number of possible cycles on the vertex set, and the probability that all edges of any one such cycle are present.

Throughout, graphs are finite and simple. A cycle of length \(k\) is an unoriented cycle with \(k\) distinct vertices, where changing the starting vertex or reversing the direction does not produce a new cycle. In \(G(n,p)\), take \(V=\{1,\ldots,n\}\); every unordered pair of distinct vertices is a possible edge, and each is included independently with probability \(p\), where \(0\le p\le1\).

The Expected Number of Cycles of a Fixed Length

First count the possible cycles before any edges are randomly selected. An ordered list of \(k\) distinct vertices specifies a cycle by joining consecutive vertices and joining the last back to the first. But each unoriented cycle is represented by \(2k\) such lists: there are \(k\) choices of starting point and two directions of traversal. Therefore the number of candidate cycles is \((n)_k/(2k)\), where \((n)_k=n(n-1)\cdots(n-k+1)\).

Proof. Let \(\mathcal{C}_k\) be the set of candidate cycles of length \(k\). For each \(C\in\mathcal{C}_k\), define \(I_C=1\) if all edges of \(C\) are present and \(I_C=0\) otherwise. Then \(X_k=\sum_{C\in\mathcal{C}_k} I_C\). The \(k\) edges of a candidate cycle are distinct, and edge selections are independent, so \(\mathbb{E}[I_C]=p^k\). By linearity of expectation, which does not require the indicators for different cycles to be independent, $$ \mathbb{E}[X_k]=\sum_{C\in\mathcal{C}_k}\mathbb{E}[I_C] =|\mathcal{C}_k|p^k =\frac{(n)_k}{2k}p^k. $$ If \(k>n\), there are not \(k\) distinct vertices available, so no cycle of length \(k\) exists. \(\square\)

The factor \(2k\) is essential: the count concerns cycles as subgraphs, not ordered descriptions of cycles. The formula also remains valid at \(p=0\), when the expectation is zero, and at \(p=1\), when every candidate cycle is present.

Adding the Counts Below a Threshold

The total number of cycles shorter than \(g\) is the sum of the counts at each allowed length. Applying linearity of expectation gives an exact expression, even though cycles can share edges or vertices. Such overlaps can make the indicators dependent, but they do not affect the sum of their expectations.

Proof. By definition, \(X_{<g}=\sum_{k=3}^{\min(g-1,n)}X_k\). Taking expectations and using linearity gives \(\mathbb{E}[X_{<g}]=\sum_{k=3}^{\min(g-1,n)}\mathbb{E}[X_k]\). Substituting the fixed-length formula proves the expression. If the sum is empty, there are no lengths in the specified range and both sides are zero. \(\square\)

Since \((n)_k\le n^k\), writing \(q=np\) yields a convenient upper bound: $$ \mathbb{E}[X_{<g}] \le \sum_{k=3}^{\min(g-1,n)}\frac{q^k}{2k}. $$ This bound replaces the falling product in the exact count by \(n^k\). For \(0\le q<1\), the finite sum is at most the corresponding infinite sum. Because \(1/(2k)\le1/6\) for \(k\ge3\), the geometric-series formula gives $$ \mathbb{E}[X_{<g}] \le \frac{1}{6}\sum_{k=3}^{\infty}q^k =\frac{q^3}{6(1-q)}. $$ The condition \(q<1\) is needed for this infinite-series bound. When \(q=1\), or when \(q>1\), use the finite sum instead.

Fixed \(np\) and a Sparse Parameter Choice

When \(p=c/n\), with fixed \(c\ge0\) and \(n\ge c\), the quantity \(np\) stays equal to \(c\). For each fixed \(k\), the exact expectation can be written as $$ \mathbb{E}[X_k] =\frac{c^k}{2k}\prod_{i=0}^{k-1}\left(1-\frac{i}{n}\right). $$ As \(n\) grows, each factor in this finite product tends to \(1\), so the expected count tends to \(c^k/(2k)\). If \(g\) is fixed, there are only finitely many lengths in the sum, and therefore $$ \mathbb{E}[X_{<g}] \longrightarrow \sum_{k=3}^{g-1}\frac{c^k}{2k}. $$ When \(g=3\), this sum is empty and equals zero. The conclusion follows by taking the limit of each term in a finite sum; it does not require any independence between cycle indicators.

Another useful choice, for fixed \(g\ge4\), is \(p=n^{-1+1/(g-1)}\). For \(n\ge1\), this is a valid probability, and \(np=n^{1/(g-1)}\). The bound on the short-cycle expectation becomes $$ \mathbb{E}[X_{<g}] \le \sum_{k=3}^{\min(g-1,n)}\frac{n^{k/(g-1)}}{2k} \le n\sum_{k=3}^{g-1}\frac{1}{2k}. $$ The last inequality holds because \(k\le g-1\), so \(k/(g-1)\le1\), and \(n^{k/(g-1)}\le n\) for \(n\ge1\). For fixed \(g\), the right side is a constant depending on \(g\) times \(n\).

A Common Counting Pitfall

Do not count rotations and reversals as different cycles. For example, on \(V=\{1,2,3,4,5\}\) with edge probability \(p=1/2\), an ordered triple of distinct vertices gives a description of a candidate triangle. There are \(5\cdot4\cdot3=60\) such descriptions, but each triangle is described \(2\cdot3=6\) times. The incorrect calculation \(60(1/2)^3=60/8=15/2\) treats all descriptions as different cycles. The correction is to divide the candidate count by \(6\): there are \(60/6=10\) distinct triangles, so the expected number is \(10(1/2)^3=10/8=5/4\). As a direct check, there are \(\binom{5}{3}=10\) vertex triples and exactly one triangle candidate on each triple.

Also distinguish an expected count from a guaranteed count. A positive expectation does not assert that every graph in the model has a cycle; it is an average over the random choices of edges. For estimating the average number of short cycles, count each possible cycle once and sum its probability of appearing. The calculation remains valid even when different cycles overlap.