Random minimum spanning tree

In mathematics, the random minimal spanning tree, or random MST, is a model (actually two related models) for a random tree. It might be compared against the uniform spanning tree, a different model for a random tree which has been researched much more extensively.

Some useful background for this page may be found in minimal spanning tree and Hausdorff dimension.

First model

Let G be a finite connected graph. To define the random MST on G, make G into a weighted graph by choosing weights randomly, uniformly between 0 and 1 independently for each edge. Now pick the MST from this weighted graph i.e. the spanning tree with the lowest total weight. Almost surely, there would be only one i.e. there would be no two distinct spanning trees with identical total weight. This tree (denote it by T) is also a spanning tree for the unweighted graph G. This is the random MST.

The most important case, and the one that will be discussed in this page, is that the graph G is a part of a lattice in Euclidean space. For example, take the vertex set to be all the points in the plane (x,y) with x and y both integers between 1 and some N. Make this into a graph by putting an edge between every two points with distance 1. This graph will be denoted by

$\mathbb {Z} _{N}^{2}.$

Mainly we will think about N as large and be interested in asymptotic properties as N goes to infinity.