Minmin Wang

Colour ratio in Prim’s ranking of the complete bipartite graph

We consider the complete bipartite graph with n black vertices and m=an white vertices, equipped with i.i.d Uniform (0, 1) weights. The minimum spanning tree of the weighted graph can be found using the so-called Prim’s Algorithm, which outputs a sequence of increasing subtrees T_k, where T_k is a bipartite tree of k vertices. Denote by rho_k the ratio of white vs black vertices in T_k. In a joint work with Félix Kahane, we give a complete characterisation of the asymptotic behaviours of rho_k as both k and n tend to infinity (possibly with different speeds). In particular, our result implies that unless m=n or k=m+n, the colour ratio we observe in T_k converges to a quantity different from m/n=a.