Timeline for Expected Number of edges for a graph to have a Triangle?
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 28, 2016 at 17:54 | comment | added | MR_BD | @fedja Oooops. Yes. That's it... Dear fedja: a Big Thanks For Your Kindness... i really enjoyed talking to you... BEST WISHES | |
| Aug 28, 2016 at 17:04 | comment | added | fedja | Sorry, I misread that (alas, it will soon be time when I will need glasses to read...). But then it creates another obvious error: the distribution you create this way is not uniform on edges. Indeed, the probability of the edge $x-y$ to be added is about $1/n(x-1)$ instead of the correct $2/n(n-1)$. So you get rather heavy on edges with small indices, which also significantly increases the chance to create a triangle somewhere. | |
| Aug 28, 2016 at 16:26 | comment | added | MR_BD | @fedja I prevent the diagonal ones. x=randi(n-1)+1 and y=randi(x-1) So x begins at 2 and y is at most x-1 ... So all ones is above the diagonal... | |
| Aug 28, 2016 at 15:34 | comment | added | fedja | Actually, not even an edge is needed: just one non-zero diagonal entry stops the process. | |
| Aug 28, 2016 at 15:25 | comment | added | fedja | Aha, here is the problem: you shouldn't put anything on the diagonal $x=y$ and you never prevent this explicitly, as far as I can tell (+1 on the x assignment is totally ridiculous and does nothing ("random plus one" is still just "random"). So, you stop if you either have a triangle, or you get at least one diagonal entry and an edge on the corresponding vertex. The second case is what is driving you down, so, remove +1 and replace "if A0(x,y)==0" with "if A0(x,y)==0 & x!=y" (or whatever is the right syntax in Maple; I usually use C), and you'll be fine. | |
| Aug 28, 2016 at 13:59 | history | answered | MR_BD | CC BY-SA 3.0 |