{"id":"arxiv/2601.15520","url":"https://arxiv.org/abs/2601.15520","tags":["math.PR","math.CO"],"score":0,"title":"Colour ratio in Prim's ranking of bipartite graphs","domain":"math.PR","source":"arxiv","authors":["Félix Kahane","Minmin Wang"],"reviews":0,"subject":"math.PR","summary":"We consider a complete bipartite graph of size $n$ endowed with i.i.d. uniform edge weights and run Prim's Algorithm to obtain a ranking of its vertices. Let $ρ^{(n)}_k$ be the proportion of black vertices among the first $k$ vertices in this ranking. We characterise the limit behaviour of $ρ^{(n)}_k$ as both $n$ and $k$ tend to infinity. Our results show that in general the limit of $ρ^{(n)}_k$, when existing, differs from the overall proportion of the black vertices in the graph.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-01-21","reactions":{}}