Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am working on a homework problem. The essence of it is as follows:

Fix some integer $g$, a probability $p\in [0,1]$, and a linear function $f(n)$, where $n$ is the number of vertices of a random graph. If the probability of having a particular edge in a graph is $p$, what is the probability that the number of cycles of length at most $g$ in a random graph with $n$ vertices will surpass $f(n)$?

I'd like just some hints in the direction of the solution. The actual question has $p$ as a function of $n$ and $g$, and asks for the result in the limit as $n\to\infty$, but I would like to understand the question in general.

share|cite|improve this question
I'll delete my answer so you're more likely to get the combinatorial argument you wanted. – Alexander Gruber Nov 27 '12 at 1:54

I doubt you'll find a closed form for the finite case; the calculation is complicated because of the correlations between different cycles; I think the problem was posed for the infinite case for a reason :-)

For the infinite case, you can calculate the expected number of cycles, whose behaviour for $n\to\infty$ will depend on how $p$ depends on $n$. You can also calculate the variance of the number of cycles as the expected value of the square minus the square of the expected value. Then you can use Chebyshev's inequality to show that the probability for the number to deviate appreciably from the expected number goes to $0$ for $n\to\infty$, so you can just compare $f(n)$ with the expected number.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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