Minmin Wang (University of Sussex) – Colour ratio in Prim’s ranking of the complete bipartite graph

Consider the complete bipartite graph with $n$ black vertices and $m=an$ white vertices. Edges in the graph can only exist between vertices of different colours. Equip the $mn/2$ edges of the graph with i.i.d Uniform (0, 1) weights. The minimum spanning tree of the graph with respect to these weights can be constructed 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$.