Diameter of uniform spanning trees on random weighted graphs

2023/11/03 by Makowiec, Luca, Salvi, Michele, Sun, Rongfeng · 1 citation
#FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2311.01808

Abstract

For any edge weight distribution, we consider the uniform spanning tree (UST) on finite graphs with i.i.d. random edge weights. We show that, for bounded degree expander graphs and finite boxes of \mathbb Z^d, the diameter of the UST is of order n^1/2+o(1) with high probability, where n is the number of vertices.

Cited by

• Repeat times and a two-weight UST model

Related

• Repeat times and a two-weight UST model
• The diameter of the minimum spanning tree of the complete graph with inhomogeneous random weights
• The diameter of the uniform spanning tree of dense graphs
• On edge disjoint spanning trees in a randomly weighted complete graph
• On Minimum Spanning Trees for Random Euclidean Bipartite Graphs