patternMinor
What is average number of cycles in an undirected ordered graph of size n?
Viewed 0 times
numbergraphwhatsizeaverageundirectedorderedcycles
Problem
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.
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.
Solution
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. $$
$$ \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. $$
Context
StackExchange Computer Science Q#23315, answer score: 6
Revisions (0)
No revisions yet.