Random minimum spanning tree

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

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 not be 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 think about N as large and be interested in asymptotic properties as N goes to infinity.