The University of Arizona

Cross-Multiplicative Coalescence and Minimal Spanning Trees of Irregular Graphs

Cross-Multiplicative Coalescence and Minimal Spanning Trees of Irregular Graphs

Series: Mathematical Physics and Probability Seminar
Location: Math 402
Presenter: Yevgeniy Kovchegov, Oregon State University

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.

Department of Mathematics, The University of Arizona 617 N. Santa Rita Ave. P.O. Box 210089 Tucson, AZ 85721-0089 USA Voice: (520) 621-6892 Fax: (520) 621-8322 Contact Us © Copyright 2018 Arizona Board of Regents All rights reserved