# The diameter of random spanning trees interpolating between the UST and the MST of the complete graph

Source: [The diameter of random spanning trees interpolating between the UST and the MST of the complete graph](<https://www.sota2.com/research/paper/68fa5c9c1e209131ce9d29c0>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-25T17:44:27.821Z

Authors: \\'Agnes K\\'usz

Published: 2024-10-23T20:40:48.000Z

## Abstract

We introduce $\\mathsf{WST}^{\\beta\_n}(K\_n)$ as the weighted spanning tree of the complete graph $K\_n$ w.r.t. the random electric network of conductances $\\{\\exp(-\\beta\_nU\_{e})\\}\_{e\\in E(K\_n)}$ with $\\mathrm{Unif}\[0,1\]$ i.i.d. $U\_e$'s.   Moving from $\\beta\_n\\equiv 0$ to faster and faster growing $\\beta\_n$'s, the model interpolates between the \\emph{uniform} and the \\emph{minimum} spanning trees: $\\mathsf{WST}^0(K\_n)=\\mathsf{UST}(K\_n)$, and there are phase transitions for $\\mathsf{WST}^{\\beta\_n}(K\_n)$ behaving more and more like $\\mathsf{MST}(K\_n)$:   - around $\\beta\_n=n^{3+o(1)}$ regarding the agreement of the two standard algorithms generating these models : Aldous-Broder and Prim's invasion algorithms,   - around $\\beta\_n=n^{2+o(1)}$ regarding the models consisting of exactly the same edges, and   - around $\\beta\_n=n^{1+o(1)}$ regarding the expected total length $\\mathbb{E}\\left\[\\sum\_{e\\in \\mathsf{WST}^{\\beta\_n}(K\_n)}U\_e\\right\]$.   But most importantly, we study the global geometry of the model: we prove that the typical diameter of $\\mathsf{WST}^{\\beta\_n}(K\_n)$ grows like $\\Theta(n^{1/3})$ for $\\beta\_n\\ge n^{4/3+o(1)}$ likewise the $\\mathsf{MST}(K\_n)$ case, and it grows like $\\Theta(n^{1/2})$ for $\\beta\_n\\le n^{1+o(1)}$ similarly to the $\\mathsf{UST}(K\_n)$ case. For $\\beta\_n=n^{\\alpha}$ with $1\<\\alpha\<4/3$, the behavior of the typical diameter is a more delicate open question, but we conjecture that its exponent strictly between 1/2 and 1/3.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2410.18269>)

[PDF](<https://arxiv.org/pdf/2410.18269.pdf>)
