Consider a random graph of $n$ vertices where the probability of there being an edge between any two vertices is .01. I want to see what is the asymptotic behavior of the probability that there exists a cycle of length 3 within this graph. I understand that the number of ways I can have a cycle of length 3 is $\binom{n}{3},$ and the probability of their being a cycle between a given set of 3 vertices is $(.01)^3.$ However, I am not quite sure where to go with this particular probability. Any assistance will be greatly appreciated.

  • 1
    $\begingroup$ I think the probability distribution is irrelevant all such graphs are isomorphic. $\endgroup$ – Rene Schipperus Jan 5 '16 at 2:34
  • 2
    $\begingroup$ It is a lot easier to find the expected number of triangles. $\endgroup$ – Jorge Fernández Hidalgo Jan 5 '16 at 2:37
  • 2
    $\begingroup$ Possible duplicate of Expected number of triangles in a random graph of size $n$ $\endgroup$ – JMoravitz Jan 5 '16 at 3:55
  • $\begingroup$ @JMoravitz: Isn't the expected number of triangles, found in that earlier question, easier to compute (by linearity of expectation) than the probability of at least one triangle? Such I take to be the significance of dREaM's Comment. $\endgroup$ – hardmath Jan 5 '16 at 4:06

First I guess your random graph model is usually indicated with $G(n,p)$, which is called a Binomial Random graph with $n$ vertices and each edge is selected independently with probability $p$.

If $n\geq 3$ then the probability that a random graph G(n,0.01) contains $C_3$ as an induced subgraph is positive, let's say it is $r>0$. Since $V(G)$, the vertex set of $G$, contains $\lfloor \frac{n}{3} \rfloor$ disjoint subsets of $3$ vertices each, the probability that no induced subgraph of G is isomorphic to $C_3$ is at most $(1-r)^{\lfloor \frac{n}{3} \rfloor}$ which tends to $0$ as $n \rightarrow \infty$.

Hence as $n \rightarrow \infty$, almost every graph $G(n,0.01)$ contains $C_3$ as a induced subgraph.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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