Simulations: Uniform spanning trees of random planar maps and graphs
A spanning tree of a connected graph is a subgraph with the same vertex set that is a tree. The uniform spanning tree model draws a random element of the set of all spanning trees of a given (random) graph. Classical algorithms for generating uniform spanning trees include Wilson's algorithm and the Aldous-Broder algorithm.
The Aldous-Broder algorithm performs a simple random walk on the graph. Whenever we reach a vertex for the first time we remember the edge we crossed to get there. After exploring the entire graph we are left with a subset of edges. The corresponding subgraph is uniformly distributed among all spanning trees. The following video illustrates this algorithm for a randomly generated planar graph. Selected edges are coloured red in the graph to the left and are placed in the corresponding tree structure to the right.
The Aldous-Broder algorithm in action
The scaling limit of uniform spanning trees of uniform planar maps is currently an open problem. The order of growth is predicted by the Knizhnik-Polyakov-Zamolodchikov (KPZ) formula to equal n^alpha for alpha = (5 - Sqrt(10)) / 4. I warmly thank N. Berestycki for related explanations. The rate of growth can be confirmed via simulations of planar maps up to n = 10^8 vertices which suggest alpha=0.459... - in agreement with the predicution up to 3 digits after the dot:
| n | 10^3 | 10^4 | 10^5 | 10^6 | 10^7 | 10^8 |
|---|---|---|---|---|---|---|
| h(n) | 31.2812 | 93.8020 | 273.9275 | 792.7325 | 2285.815 | 6585.556 |
| alpha(n) | 0.476927 | 0.465423 | 0.461491 | 0.459914 | 0.459551 |
In the table, h(n) denotes the average height of a uniform spanning tree in a random planar map with n vertices, and alpha(n) = log(h(10*n)/h(n)) / log(10).
Uniform spanning tree of a uniform planar map with 1M vertices. Colours represent closeness centrality in the tree.
Histogram for the height of the uniform spanning tree in random planar maps with 10k vertices. The dotted line represents the density of a maximum of a Brownian excursion, multiplied by a constant so that the average matches the histogram. The distributions are similar but do not match - an effect that gets more pronounced for larger numbers of vertices.
Histogram for the height of the uniform spanning tree in random planar maps with 100k vertices. The dotted line represents the density of a maximum of a Brownian excursion, multiplied by a constant so that the average matches the histogram. The distributions are similar but do not match - an effect that gets more pronounced for larger numbers of vertices.
Histogram for the height of the uniform spanning tree in random planar maps with 1M vertices. The dotted line represents the density of a maximum of a Brownian excursion, multiplied by a constant so that the average matches the histogram. The distributions are similar but do not match - an effect that gets more pronounced for larger numbers of vertices.
0