Timeline for "The" random tree
Current License: CC BY-SA 2.5
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 19, 2009 at 18:24 | comment | added | Ilya Nikokoshev | Indeed, though the point of the construction, of course, is that anything "sufficiently random" works. | |
| Nov 19, 2009 at 16:50 | comment | added | Vladimir Dotsenko | Can't resist mentioning a peculiar construction of the random graph I heard from Peter Cameron a while ago - the vertices are primes congruent to 1 mod 4, and two primes p and q are connected by an edge if p is a square mod q (this relation is symmetric because of quadratic reciprocity law). A beautiful one, isn't it? | |
| Nov 19, 2009 at 1:46 | vote | accept | Ian Agol | ||
| Nov 18, 2009 at 22:25 | history | edited | Ilya Nikokoshev | CC BY-SA 2.5 |
thanks
|
| Nov 18, 2009 at 22:24 | comment | added | Ilya Nikokoshev | Sorry, I meant to thank both of you. I read both Wikipedia and blog post, but forgot the references -- so I copied my ref to n-cafe from your post. | |
| Nov 18, 2009 at 22:00 | comment | added | Andrew Stacey | I didn't spot that the "blog post" you referenced was the n-cafe, hence my answer below. Perhaps when one links off-site, one should say where the link goes to as a courtesy. | |
| Nov 18, 2009 at 20:15 | comment | added | Ilya Nikokoshev | Indeed! I forgot the exact construction while answering. Thanks! | |
| Nov 18, 2009 at 20:13 | history | edited | Ilya Nikokoshev | CC BY-SA 2.5 |
correction
|
| Nov 18, 2009 at 20:12 | comment | added | Harrison Brown | Ilya, not only is it connected w/ probability 1, it's ALWAYS connected. Suppose such a tree was not connected; then there's a connected component not containing vertex 1. This component has some vertex v of minimum label, but v is adjacent to some vertex of smaller label, which is a contradiction. | |
| Nov 18, 2009 at 20:06 | history | edited | Ilya Nikokoshev | CC BY-SA 2.5 |
linkify
|
| Nov 18, 2009 at 19:56 | history | undeleted | Ilya Nikokoshev | ||
| Nov 18, 2009 at 19:56 | history | edited | Ilya Nikokoshev | CC BY-SA 2.5 |
made better
|
| Nov 18, 2009 at 19:48 | history | deleted | Ilya Nikokoshev | ||
| Nov 18, 2009 at 19:43 | comment | added | sdcvvc | en.wikipedia.org/wiki/Rado_graph? | |
| Nov 18, 2009 at 19:42 | history | answered | Ilya Nikokoshev | CC BY-SA 2.5 |