The diameter of random spanning trees interpolating between the UST and the MST of the complete graph
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916496945446912 |
|---|---|
| author | Kúsz, Ágnes |
| author_facet | Kúsz, Ágnes |
| contents | We introduce $\mathsf{WST}^{β_n}(K_n)$ as the weighted spanning tree of the complete graph $K_n$ w.r.t. the random electric network of conductances $\{\exp(-β_nU_{e})\}_{e\in E(K_n)}$ with $\mathrm{Unif}[0,1]$ i.i.d. $U_e$'s.
Moving from $β_n\equiv 0$ to faster and faster growing $β_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}^{β_n}(K_n)$ behaving more and more like $\mathsf{MST}(K_n)$:
- around $β_n=n^{3+o(1)}$ regarding the agreement of the two standard algorithms generating these models : Aldous-Broder and Prim's invasion algorithms,
- around $β_n=n^{2+o(1)}$ regarding the models consisting of exactly the same edges, and
- around $β_n=n^{1+o(1)}$ regarding the expected total length $\mathbb{E}\left[\sum_{e\in \mathsf{WST}^{β_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}^{β_n}(K_n)$ grows like $Θ(n^{1/3})$ for $β_n\ge n^{4/3+o(1)}$ likewise the $\mathsf{MST}(K_n)$ case, and it grows like $Θ(n^{1/2})$ for $β_n\le n^{1+o(1)}$ similarly to the $\mathsf{UST}(K_n)$ case. For $β_n=n^α$ with $1<α<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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_18269 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The diameter of random spanning trees interpolating between the UST and the MST of the complete graph Kúsz, Ágnes Probability Combinatorics We introduce $\mathsf{WST}^{β_n}(K_n)$ as the weighted spanning tree of the complete graph $K_n$ w.r.t. the random electric network of conductances $\{\exp(-β_nU_{e})\}_{e\in E(K_n)}$ with $\mathrm{Unif}[0,1]$ i.i.d. $U_e$'s. Moving from $β_n\equiv 0$ to faster and faster growing $β_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}^{β_n}(K_n)$ behaving more and more like $\mathsf{MST}(K_n)$: - around $β_n=n^{3+o(1)}$ regarding the agreement of the two standard algorithms generating these models : Aldous-Broder and Prim's invasion algorithms, - around $β_n=n^{2+o(1)}$ regarding the models consisting of exactly the same edges, and - around $β_n=n^{1+o(1)}$ regarding the expected total length $\mathbb{E}\left[\sum_{e\in \mathsf{WST}^{β_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}^{β_n}(K_n)$ grows like $Θ(n^{1/3})$ for $β_n\ge n^{4/3+o(1)}$ likewise the $\mathsf{MST}(K_n)$ case, and it grows like $Θ(n^{1/2})$ for $β_n\le n^{1+o(1)}$ similarly to the $\mathsf{UST}(K_n)$ case. For $β_n=n^α$ with $1<α<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. |
| title | The diameter of random spanning trees interpolating between the UST and the MST of the complete graph |
| topic | Probability Combinatorics |
| url | https://arxiv.org/abs/2410.18269 |