4
$\begingroup$

What is average number of cycles in an undirected ordered graph of size $n$? I've tried finding out sum of number of cycles in all sorts of a graph of size n but I couldn't find that out.

$\endgroup$
1
  • 1
    $\begingroup$ What specifically have you tried resp where have you looked? $\endgroup$
    – Raphael
    Apr 1, 2014 at 11:45

1 Answer 1

6
$\begingroup$

Hint: Suppose that there are $Z_m$ cycles of length $m$, and that $p_m$ is the probability that a specific cycle of length $m$ is in the graph. Then the expected number of cycles is $$ \sum_{m=3}^n Z_m p_m $$ due to linearity of expectation.

Here is the entire calculation. In the $G(n,p)$ model, in which each edge is present with probability $p$ independently, clearly $p_m = p^m$. The number of ordered $m$-tuples of points is $n!/(n-m)!$. Each cycle of length $m$ is described by $2m$ such tuples: choose a starting point and an orientation. Therefore the total number of cycles of length $m$ is $n!/2m(n-m)!$, and the expected number of cycles is $$ E = \sum_{m=3}^n \frac{n!}{2m(n-m)!} p^m. $$

In order to estimate this number, let's find the largest term. The ratio of two successive terms is roughly $$ \frac{p^{m+1}}{(n-m-1)!} \frac{(n-m)!}{p^m} = (n-m)p. $$ When $p$ is constant, we see that the most important term corresponds to $m = n$, namely $n! p^n/(2n)$, and we deduce that for large enough $n$, the expected number of cycles satisfies $$ 2(n-1)! p^n \leq E \leq 2n! p^n. $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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