5
$\begingroup$

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.

  • 0
    I'll delete my answer so you're more likely to get the combinatorial argument you wanted.2012-11-27

1 Answers 1