Colour ratio in Prim's ranking of bipartite graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918299474853888 |
|---|---|
| author | Kahane, Félix Wang, Minmin |
| author_facet | Kahane, Félix Wang, Minmin |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_15520 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Colour ratio in Prim's ranking of bipartite graphs Kahane, Félix Wang, Minmin Probability Combinatorics 60C05 (Primary), 05C80 (Primary), 60J80 (Secondary), 60F15 (Secondary), 60G99 (Secondary) G.2; G.3 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. |
| title | Colour ratio in Prim's ranking of bipartite graphs |
| topic | Probability Combinatorics 60C05 (Primary), 05C80 (Primary), 60J80 (Secondary), 60F15 (Secondary), 60G99 (Secondary) G.2; G.3 |
| url | https://arxiv.org/abs/2601.15520 |