Peter Otto

Willamette University
, Bond Hall 225

Abstract

Limits of Mean Lengths of Minimal Spanning Trees via Coalescent Processes

Consider a graph where the edges are assigned random lengths according to the uniform distribution over the unit interval \([0,1]\).  For each spanning tree of the graph, the random length of the spanning tree is the sum of the lengths of the edges of the spanning tree and the minimal spanning tree is the one with the shortest length.  In this talk, I will first present the connection between these random minimal spanning tree lengths and Marcus-Lushnikov processes that track the number of connected components of each possible size of a random coalescent process.  I will then present recent work with Yevgeniy Kovchegov at Oregon State University on extending this connection to more general coalescent processes that yield minimal spanning tree results for inhomogeneous random graphs.