Colour ratio in Prim's ranking of bipartite graphs
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.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2601.15520
curl -X POST /api/v1/records/arxiv/2601.15520/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2601.15520/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'