Skip to main content
MathOverflow

Return to Question

fixed broken link to Wikipedia
Source Link
edit approved Dec 1, 2023 at 14:27
The Amplitwist
edit approved Dec 1, 2023 at 14:27
The Amplitwist
  • 1.7k
  • 4
  • 14
  • 29

Suppose you take a $G(n,p)$ random graph for a fixed probability $p$ and find a spanning tree using Kruskal's algorithmKruskal's algorithm. If you now repeat this process indefinitely, will every tree on $n$ vertices appear with the same frequency?

In other word: are some trees more likely than others to be spanning trees of a random graph?

Suppose you take a $G(n,p)$ random graph for a fixed probability $p$ and find a spanning tree using Kruskal's algorithm. If you now repeat this process indefinitely, will every tree on $n$ vertices appear with the same frequency?

In other word: are some trees more likely than others to be spanning trees of a random graph?

Suppose you take a $G(n,p)$ random graph for a fixed probability $p$ and find a spanning tree using Kruskal's algorithm. If you now repeat this process indefinitely, will every tree on $n$ vertices appear with the same frequency?

In other word: are some trees more likely than others to be spanning trees of a random graph?

Source Link
Felix Goldberg
Felix Goldberg
  • 7.1k
  • 4
  • 32
  • 59

How random are random spanning trees?

Suppose you take a $G(n,p)$ random graph for a fixed probability $p$ and find a spanning tree using Kruskal's algorithm. If you now repeat this process indefinitely, will every tree on $n$ vertices appear with the same frequency?

In other word: are some trees more likely than others to be spanning trees of a random graph?