# Probability of cycles of length at most $g$ in a random graph

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.

-
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

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.