# Counting pairs of $k$-cycles with $r$ common edges (Variance of number of $k$-cycles)

This is a random graph probability problem I'm interested in and trying to figure out, that reduces to a combinatorics problem.

Consider a random graph $\mathcal{G}_{n,p}$ on $n$ vertices where an edge forms independently between any two nodes with probability $p$. Let $X$ be the random variable that counts the number of $k$-cycles. If we denote: $$C_k : \text{the set of (undirected) k-cycles on n vertices}$$ and let $I_c$ be the indicator variable for the event that the $k$-cycle $c$ forms, then: $$X = \sum_{c \in C_k} I_c$$ I'm interested in calculating the expectation and variance of $X$, or at least provide a bound that can be analyzed in the limit of $n$.

Since the $k$-cycles are indistinguishable, they all have the same probability of formation, equal to probability that the $k$ edges form, equal to $p^k$. So, $$\mathbb{E}[X] = |C_k| \cdot p^k$$

In calculating $|C_k|$, we see that the number of ways to create a (undirected) $k$-cycle is equal to half of the number of cyclic $k$-permutations on $n$ vertices, where the factor of $2$ comes from the undirected requirement, so: $$|C_k| = \frac{n^\underline{k}}{2k}$$ where $n^\underline{k} = n(n-1)\cdots(n-k+1)$

In order to calculate $\text{var}(X) = \mathbb{E}[X^2] - \mathbb{E}[X]^2$, I calculate the second moment: \begin{align*} \mathbb{E}[X^2] &= \sum_{c_1,c_2 \in C_k} \mathbb{E}[I_{c_1} I_{c_2}] \\ &= \sum_{c_1,c_2 \in C_k} \mathbb{P}[I_{c_1} = 1, I_{c_2} = 1] \\ \end{align*} The events that the $k$-cycle $c_1$ has formed and the $k$-cycle $c_2$ has formed are not necessarily independent. They are independent if and only if the two cycles share no edges. In general, the probability is equal to $p$ raised to the power of edges needed for both cycles to form. So we can restructure the sum as: \begin{align*} \mathbb{E}[X^2] &= \sum_{r = 0}^k \sum_{\substack{c_1, c_2 \in C_k \\ |c_1 \cap c_2| = r}} p^{2k-r} \\ &= \sum_{r = 0}^k p^{2k-r} \cdot \bigg\lvert \Big\{ (c_1,c_2) \in C_k \times C_k \,\bigg\vert\, \text{$c_1$ and $c_2$ share exactly $r$ edges} \Big\} \bigg\rvert \end{align*}

The problem reduces to the combinatorics problem: evaluating or bounding \begin{align*} \bigg\lvert \Big\{ (c_1,c_2) \in C_k \times C_k \,\bigg\vert\, \text{$c_1$ and $c_2$ share exactly $r$ edges} \Big\} \bigg\rvert &= \left(\substack{\text{# of ordered pairs of (undirected) $k$-cycles on $n$} \\ \text{vertices such that the two $k$-cycles share exactly $r$ edges}} \right) \end{align*}

Evaluating or bounding this number is the current problem.

A connected graph on $v$ vertices and at least $2$ cycles must have at least $v+1$ edges.
So pairs of cycles sharing at least one edge (but not all edges) contribute $$O(n^{k+1}p^{k+2}) + O(n^{k+2}p^{k+3}) + \dots + O(n^{2k-2}p^{2k-1})$$ to the expectation $\mathbb E[X^2]$. Here, the $O(\cdot)$ hides the very large constant, depending only on $k$, representing the number of ways in which the two cycles can overlap in the correct number of vertices.
(This requires $p \to 0$ as $n \to \infty$, so that the contribution from overlap-graphs that have exactly one more edge than vertex is asymptotically more significant than the other cases.)
Pairs of cycles sharing no edges, of course, contribute $O(n^{2k} p^{2k})$. In fact, their contribution to $\mathbb E[X^2]$ is $(1+o(1)) \mathbb E[X]^2$.
The final unusual case is the sum of diagonal terms: pairs of cycles which share all $k$ vertices and edges and are, in fact, the same cycle. The contribution here is exactly $\mathbb E[X]$, which is usually not significant.