# Determine conditions on pn such that the probability that a random graph has at least one triangle goes to zero as n increases

I'm currently struggling with an exercise about random graphs where is requested to determine the conditions on $$p_n$$ such that the probability that $$G(n, p_n)$$ has at least one triangle goes to zero as $$n → +∞$$, also assuming that the probability that three vertices forms a triangle is $$p_n^3$$. I know I have to apply the first order method but I can't relate the theory with general properties.

• Is the step where you're getting stuck "how do I compute the expected number of triangles in $G(n,p$)"? – Misha Lavrov Feb 3 at 0:36

Let $$T_n$$ be the number of triangles in a $$G(n,p_n)$$ random graph. Then you should be able to get a formula for the expected number of triangles, $$ET_n$$. In order to ensure no triangles, or usually none, you should make (a) $$ET _n$$ large, or (b) $$ET_n$$ small. Can you take it from there?
I don't know much about graph theory but you could work out the probability of that no triangle exists. Starting with one random point A and a random point B, the probability that no triangle exists of the form ABx is given by: $$(1-p_n^3)^{n-2}$$. Now pick a different point C and the probability that no triangle exists of the form ACx conditional on what we already know is given by $$(1-p_n^3)^{n-3}$$. Using this strategy you can calculate the probability of A not being in a triangle which will be of the order $$(1-p_n^3)^{n^2}$$. Can you continue?
• Ah you're right of course. The probability of such a triangle is dependent on the existence of the edge AB. By conditioning on this event, we are still able to calculate this. It should be: $p_n\cdot\left(1-(1-p_n^2)^{n-2}\right) +(1-p_n)\cdot0$. Thanks for finding the mistake. I think it is possible to work this out to the end. But since apparently in the second step the independence assumption is also not valid (sorry for that), it will definitely become more messy than I thought at first glance. – Stan Tendijck Feb 3 at 20:51