From the Uniform to the Minimum Spanning Tree

Abstract:

A spanning tree of a graph G is a connected subset of G without cycles. The Uniform Spanning Tree (UST) is obtained by choosing one of the possible spanning trees of G at random. The Minimum Spanning Tree (MST) is realised instead by putting random weights on the edges of G and then selecting the spanning tree with the smallest weight. These two models exhibit markedly different behaviours: for example, their diameter on the complete graph with n nodes transitions from n^1/2 for the UST to n^1/3 for the MST. What lies in between? 

We introduce a model of Random Spanning Trees in Random Environment (RSTRE) designed to interpolate between UST and MST. In particular, when the environment disorder is sufficiently low, the RSTRE on the complete graph has a diameter of n^1/2 as the UST. Conversely, when the disorder is high, the diameter behaves like n^1/3 as for the MST. We conjecture a smooth transition between these two values for intermediate levels of disorder.