Timeline for How random are random spanning trees?
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Dec 1, 2023 at 14:27 | history | suggested | The Amplitwist | CC BY-SA 4.0 |
fixed broken link to Wikipedia
|
| Dec 1, 2023 at 11:47 | review | Suggested edits | |||
| S Dec 1, 2023 at 14:27 | |||||
| Jan 26, 2013 at 6:04 | comment | added | Aaron Meyerowitz | Obviously more difficult than I thought also. | |
| Jan 25, 2013 at 22:23 | comment | added | Sam Hopkins | @AaronMeyerowitz: I now see why this question is more difficult than I thought at first. Thanks. | |
| Jan 25, 2013 at 20:58 | comment | added | Aaron Meyerowitz | @SamHopkins. There are $38$ connected subgraphs of $K_4$. If I pick, choosing uniformly among them, and then pick uniformly among the spanning trees of that subgraph , then the probability of getting a star is 41/152. If I pick a spanning tree by randomly weighting the edges and then taking the minimal cost spanning tree then the probabilities are something else but almost surely not uniform. | |
| Jan 25, 2013 at 2:18 | vote | accept | Felix Goldberg | ||
| Jan 25, 2013 at 2:16 | answer | added | Aaron Meyerowitz | timeline score: 5 | |
| Jan 25, 2013 at 0:30 | comment | added | Felix Goldberg | @SamHopkins: Actually, I was thinking about unlabelled... | |
| Jan 25, 2013 at 0:03 | comment | added | Sam Hopkins | I assume you're considering labeled trees/graphs. Here's an answer for an easier version of the question, which maybe you have already considered: suppose you choose each connected graph on n vertices with equal probability, and suppose you choose from it a random spanning tree. Then it seems clear to me that all trees are equally likely. | |
| Jan 24, 2013 at 23:54 | history | asked | Felix Goldberg | CC BY-SA 3.0 |