Random minimum spanning tree and dense graph limits
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913787742781440 |
|---|---|
| author | Hladký, Jan Viswanathan, Gopal |
| author_facet | Hladký, Jan Viswanathan, Gopal |
| contents | A theorem of Frieze from 1985 asserts that the total weight of the minimum spanning tree of the complete graph $K_n$ whose edges get independent weights from the distribution $UNIFORM[0,1]$ converges to Apéry's constant in probability, as $n\to\infty$. We generalize this result to sequences of graphs $G_n$ that converge to a graphon $W$. Further, we allow the weights of the edges to be drawn from different distributions (subject to moderate conditions). The limiting total weight $κ(W)$ of the minimum spanning tree is expressed in terms of a certain branching process defined on $W$, which was studied previously by Bollobás, Janson and Riordan in connection with the giant component in inhomogeneous random graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_11705 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Random minimum spanning tree and dense graph limits Hladký, Jan Viswanathan, Gopal Combinatorics Probability A theorem of Frieze from 1985 asserts that the total weight of the minimum spanning tree of the complete graph $K_n$ whose edges get independent weights from the distribution $UNIFORM[0,1]$ converges to Apéry's constant in probability, as $n\to\infty$. We generalize this result to sequences of graphs $G_n$ that converge to a graphon $W$. Further, we allow the weights of the edges to be drawn from different distributions (subject to moderate conditions). The limiting total weight $κ(W)$ of the minimum spanning tree is expressed in terms of a certain branching process defined on $W$, which was studied previously by Bollobás, Janson and Riordan in connection with the giant component in inhomogeneous random graphs. |
| title | Random minimum spanning tree and dense graph limits |
| topic | Combinatorics Probability |
| url | https://arxiv.org/abs/2310.11705 |