0
$\begingroup$

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.

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

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?

$\endgroup$
0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ This is not an effective strategy, mainly because every single probability you've calculated is incorrect. (The probabilities of triangles of the form ABx appearing are not independent.) $\endgroup$ – Misha Lavrov Feb 3 at 0:25
  • $\begingroup$ 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. $\endgroup$ – Stan Tendijck Feb 3 at 20:51
  • $\begingroup$ But I do agree since it becomes super messy, they way to go is to use the theory suggested by @kimchi lover. $\endgroup$ – Stan Tendijck Feb 3 at 20:58

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.