Random spanning trees in random environment
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909050266976256 |
|---|---|
| author | Makowiec, Luca Salvi, Michele Sun, Rongfeng |
| author_facet | Makowiec, Luca Salvi, Michele Sun, Rongfeng |
| contents | We introduce a new spanning tree model called the random spanning tree in random environment (RSTRE), which interpolates between the uniform spanning tree and the minimum spanning tree as the inverse temperature (disorder strength) $β$ varies. On the complete graph with $n$ vertices and i.i.d.\ uniform disorder variables on the edges, we identify: (1) a low disorder regime with $β\leq C n/\log n$, where the diameter of the random spanning tree is typically of order $n^{1/2}$, the same as for the uniform spanning tree; (2) a high disorder regime with $β\geq n^{4/3} \log n$, where the diameter is typically of order $n^{1/3}$, the same as for the minimum spanning tree. We conjecture that for $β=n^α$ with $α\in (1, 4/3)$, the diameter is of order $n^{γ+o(1)}$ for some $γ=γ(α)$ strictly between $1/2$ and $1/3$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_16830 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Random spanning trees in random environment Makowiec, Luca Salvi, Michele Sun, Rongfeng Probability Combinatorics 60K35 (Primary) 82B41, 82B44, 05C05 (Secondary) We introduce a new spanning tree model called the random spanning tree in random environment (RSTRE), which interpolates between the uniform spanning tree and the minimum spanning tree as the inverse temperature (disorder strength) $β$ varies. On the complete graph with $n$ vertices and i.i.d.\ uniform disorder variables on the edges, we identify: (1) a low disorder regime with $β\leq C n/\log n$, where the diameter of the random spanning tree is typically of order $n^{1/2}$, the same as for the uniform spanning tree; (2) a high disorder regime with $β\geq n^{4/3} \log n$, where the diameter is typically of order $n^{1/3}$, the same as for the minimum spanning tree. We conjecture that for $β=n^α$ with $α\in (1, 4/3)$, the diameter is of order $n^{γ+o(1)}$ for some $γ=γ(α)$ strictly between $1/2$ and $1/3$. |
| title | Random spanning trees in random environment |
| topic | Probability Combinatorics 60K35 (Primary) 82B41, 82B44, 05C05 (Secondary) |
| url | https://arxiv.org/abs/2410.16830 |