Random minimal spanning tree

From Wikipedia, the free encyclopedia

In mathematics, random minimal spanning tree, or random MST, is a model (actually two related models) for a random tree (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.

[edit] 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

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