Timeline for What are some good examples of non-monotone graph properties?
Current License: CC BY-SA 2.5
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 28, 2010 at 23:59 | comment | added | Louigi Addario-Berry | Yes it is roughly unimodal. On a crude scale (p=c/n), it is logarithmic and increasing in c for c < 1, it jumps to order $n^{1/3}$ for $c=1$, and then it drops back to logarithmic and decreasing for $c>1$. If you parameterize $p$ more finely near $1/n$ you see more interesting behaviour emerge. Key papers by Luczak in the barely-below-(1/n) case, and by Riordan and Wormald (arxiv.org/abs/0808.4067) and Ding, Kim, Lubetzky and Peres (tinyurl.com/supdiam) in the barely-above-(1/n) case. | |
| Sep 28, 2010 at 21:09 | comment | added | Matthew Kahle | Thanks, this is interesting. I will look at your paper, but do you know: if you define diameter in this way is it roughly unimodal in p for random graphs, or is it more complicated than that? | |
| Sep 28, 2010 at 0:44 | history | answered | Louigi Addario-Berry | CC BY-SA 2.5 |