6
$\begingroup$

Let $G \sim G(n,p)$ be a directed Erdős–Rényi random graph with $n$ vertices and the probability $p$ that there is a directed edge between any two ordered pairs of vertices.

What is the expected number of cycles in $G$?
Is there an exact formula or an upper bound and lower bound on the expected number of simple cycles in $G$?

$\endgroup$
  • $\begingroup$ Hi @Anders. Welcome! You might like to use MathJax in future :) $\endgroup$ – Shaun Mar 25 '14 at 20:11
5
$\begingroup$

Let $X$ be the total number of cycles, $X_k$ the number of cycles of length $k$ in $G$, and $Y_k$ the number of cycles of length $k$ in a random graph of size $k$.

Note that:

  • ${\sf E}[X] = \sum_{k=2}^n {\sf E}[X_k]$.
  • ${\sf E}[X_k] = {n \choose k} {\sf E}[Y_k]$.
  • ${\sf E}[Y_k] = (k!/k)p^k = (k-1)!p^k$.

The last one is because a cycle of length $k$ is a permutation of numbers from $1$ to $k$ but the first vertex does not matter (a cycle does not have a first vertex). The probability of each edge being present is $p$, so the probability of $k$ edges being present is $p^k$.

We have:

\begin{align*} {\sf E}[X] &= \sum_{k=2}^n E[X_k] \\ &= \sum_{k=2}^n {n \choose k} E[Y_k] \\ &= \sum_{k=2}^n {n \choose k} (k-1)! p^k \\ &= \sum_{k=2}^n \frac{n!}{k!(n-k)!} (k-1)! p^k \\ &= \sum_{k=2}^n \frac{n!}{(n-k)!k} p^k \\ &= \sum_{k=2}^n \frac{n\ldots (n-k+1)}{k} p^k \\ \end{align*}

For a simple lower bound we can drop the first half of the sum: \begin{align*} &\geq \sum_{k=n/2}^{n} \frac{n\ldots (n-k+1)}{k} p^k \\ &\geq \sum_{k=n/2}^{n} \frac{(n/2)^{k}}{n} p^k \\ &\geq \frac{1}{n}\sum_{k=n/2}^{n} (np/2)^{k} \\ &= \frac{(\frac{np}{2})^{n+1}-(\frac{np}{2})^{\frac{n}{2}}}{\frac{np}{2}-1} \end{align*}

$\endgroup$
  • $\begingroup$ What is n? DId you mean to say a random graph of n nodes? $\endgroup$ – Joel Aug 1 '16 at 20:25
  • $\begingroup$ $n$ is the number of vertices. The OP defines the model. $\endgroup$ – D Poole Aug 2 '16 at 12:44
  • $\begingroup$ I should have said a bit more: What does "in a random graph of size k" mean - did you mean "of n nodes"? $\endgroup$ – Joel Aug 3 '16 at 8:09
  • $\begingroup$ By symmetry, I reduce the question of the expected number of cycles in $D(n,p)$ to the expected number of cycles in $D(k,p)$ (we are looking at directed graphs here, so I use $D(n,p)$ instead of $G(n,p)$), In particular, $$ E[\# \text{ of cycles in }D(n,p) \text{ of length }k] = {n \choose k}E[\# \text{ of cycles in }D(k,p)\text{ of length }k]$$ $\endgroup$ – D Poole Aug 3 '16 at 12:08

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.