Timeline for Expected Number of edges for a graph to have a Triangle?
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 28, 2016 at 13:59 | answer | added | MR_BD | timeline score: 0 | |
| Aug 28, 2016 at 13:47 | vote | accept | MR_BD | ||
| Aug 28, 2016 at 10:47 | answer | added | fedja | timeline score: 6 | |
| Aug 28, 2016 at 10:08 | comment | added | fedja | Then it is nearly 4/5 fair and square both theoretically and empirically. Check your program for errors and meanwhile I'll post the argument. | |
| Aug 28, 2016 at 8:08 | comment | added | MR_BD | @fedja I exactly simulate the way you said, but I want a theoretical solution for finding the coefficient of n | |
| Aug 28, 2016 at 2:35 | comment | added | fedja | That depends on how you simulate. Assuming that you just fix $n$, throw in the edges independently at random until you get the first triangle at the $m$-th throw and then take the average of the resulting $m$, you would get about $4/5$. Apparently, you are doing something else, but I cannot figure out what exactly. Can you be more specific about how you run your simulations? | |
| Aug 28, 2016 at 1:55 | comment | added | MR_BD | @fedja I want to know where 3/5 is come from? | |
| Aug 28, 2016 at 1:36 | comment | added | fedja | Erm... Since $3/5<\sqrt[3]6/2$, you are getting triangles with high probability while the expected number is below $1$. This looks fishy, doesn't it? Or am I misunderstanding the question? | |
| Aug 27, 2016 at 11:18 | history | edited | MR_BD | CC BY-SA 3.0 |
added 15 characters in body
|
| Aug 27, 2016 at 11:02 | history | asked | MR_BD | CC BY-SA 3.0 |