2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.