Cross-Multiplicative Coalescence and Minimal Spanning Trees of Irregular Graphs
We devise a method for finding the limiting mean length of a minimal spanning tree of a random graph via the Smoluchowski coagulation equations for the corresponding coalescent process. In particular, we use this approach for finding the limiting mean length of a minimal spanning tree for an asymmetric complete bipartite graph with independent uniform edge weights over [0,1], producing a completely new formula yet consistent with the previously known formula for the symmetric bipartite graph. The proof uses the hydrodynamic limit of a novel cross-multiplicative coalescent process that we introduce.
Joint work with Peter T. Otto of Willamette University and Anatoly Yambartsev of University of Sao Paulo.