Minimum spanning arborescence  

I will introduce a model of random spanning trees called minimum spanning arborescence, which is defined as follows. Consider a finite graph, and assign iid continuous weights to both orientations of every edge. Fix a root vertex and now consider a directed spanning tree with every edge oriented towards the root. The minimum spanning arborescence is the arborescence with minimum weight. 

The undirected version of this model: the minimum spanning tree has been studied extensively by probabilists in the past two decades or so.

Turns out the oriented model has been studied quite a lot by computer scientists in the 70's and have a lot of applications, but has eluded the attention of probabilists. One of the reasons, perhaps, is that there is no nice algorithm like Kruskal's or Prim's algorithm to study this model.

I will talk about a project which attempts to turn the attention of probabilists to this area, and illustrate that there is another nice algorithm (which we call the CLEB algorithm, but sometimes called Edmond's algorithm in computer science literature) which can be used to study  the probabilistic aspects, particularly the geometry of minimum spanning arborescence. I will talk about some preliminary results in this area, and about some upcoming projects. One interesting aspect we find is that this model in some cases is much closer to the Uniform spanning tree than to the (unoriented) minimum spanning tree.

Joint work with Arnab Sen.