Timeline for How to estimate the growth of the probability that $G(n, M)$ contains a $k$-clique
Current License: CC BY-SA 2.5
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 31, 2010 at 18:08 | comment | added | Kevin P. Costello | I believe the results will be false if $c$ is taken slightly larger than $2-2/(k-1)$ (the threshold for a random $G(n,m)$ to have a clique). For a graph from the $G(n,p)$ model in this range, there are concentration results saying that the probability you fail to have a clique decays much faster than polynomially (see for example Guy Wolfovitz's Theorem 2 at arxiv.org/abs/0912.3868 ), and the same sort of concentration should hold for $G(n,M)$. So the probability's already so close to $1$ that adding another edge can't change it much. This doesn't say much about smaller c though. | |
| Aug 31, 2010 at 14:13 | answer | added | Louigi Addario-Berry | timeline score: 1 | |
| Jan 8, 2010 at 7:30 | history | edited | Penghui Yao | CC BY-SA 2.5 |
added 53 characters in body; added 20 characters in body
|
| Jan 8, 2010 at 7:13 | history | asked | Penghui Yao | CC BY-SA 2.5 |