Random spanning trees in random environment

2024/10/22 by Luca Makowiec, Makowiec, Luca, Michele Salvi +3 · 1 citation
Computer Science · #05C05 (Secondary) #60K35 (Primary) 82B41 #82B44 #Advanced Clustering Algorithms Research #Combinatorics (math.CO) #Data Management and Algorithms #Data Mining Algorithms and Applications #FOS: Mathematics #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.2410.16830

openalex publication_date 2024/10/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

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 β≤ 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 β≥ 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 α∈ (1, 4/3), the diameter is of order n^γ+o(1) for some γ=γ(α) strictly between 1/2 and 1/3.

Cited by

• Repeat times and a two-weight UST model

Related

• Observables of random spanning trees in random environment
• Local limits of random spanning trees in random environment
• Geometry of the minimal spanning tree in the heavy-tailed regime: new universality classes
• Models of random spanning trees
• Geometry of the minimal spanning tree of a random 3-regular graph