The diameter of uniform spanning trees in high dimensions
- PDF / 526,545 Bytes
- 34 Pages / 439.37 x 666.142 pts Page_size
- 93 Downloads / 140 Views
The diameter of uniform spanning trees in high dimensions Peleg Michaeli1
· Asaf Nachmias1 · Matan Shalev1
Received: 3 December 2019 / Revised: 8 July 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract We show that the diameter of a uniformly drawn spanning tree of a connected graph on n vertices which satisfies certain high-dimensionality conditions typically grows √ like ( n). In particular this result applies to expanders, finite tori Zdm of dimension d ≥ 5, the hypercube {0, 1}m , and small perturbations thereof. Mathematics Subject Classification 05C81 · 82B41 · 05C05 · 60K35
1 Introduction A spanning tree T of a connected graph G is a subset of edges which spans a connected graph, contains no cycles, and touches every vertex of G. The set of spanning trees of a finite connected graph G is finite; hence we may consider the probability measure assigning each spanning tree equal mass. This is known as the uniform spanning tree (UST) of G denoted UST(G). In this paper we study the distribution of the diameter of the UST, that is, the largest graph distance between two vertices. We show that on graphs that are high-dimensional (in some precise sense given below) the diameter typically grows like the square root of the number of vertices. When the base graph is the complete graph on√n vertices the limiting distribution of the diameter of the UST is typically of order n. In fact, its limiting distribution is known [20]. Moreover, the graph distance metric induced by the (properly scaled) UST converges in the Gromov–Hausdorff sense to Aldous’ continuum random tree (CRT) [2–4]. Aldous [1] was also the first to study the typical diameter of USTs on
B
Peleg Michaeli [email protected] Asaf Nachmias [email protected] Matan Shalev [email protected]
1
School of Mathematical Sciences, Tel Aviv University, 6997801 Tel Aviv, Israel
123
P. Michaeli et al. 1 general graphs and showed that if G is a regular graph with a spectral gap √ uniformly bounded away from 0, then the typical order of the√ diameter is between n/ log n and √ n log n (the lower bound was later improved to n in [7]). Mathematical physics folklore accurately predicts that many models exhibit an upper critical dimension dc above which the far away pieces of the model no longer interact. The effect is that the geometry “trivializes” and to most questions on the model the answer coincides with what it would be on an infinite regular tree or the complete graph. For the UST √ it is known that dc = 4 [5,17] and thus one expects that the diameter of the UST is n in various high-dimensional settings, such as expander graphs, finite tori of dimension d ≥ 5, the hypercube and many more. Indeed in these examples it can be deduced √ from past √ results (such as [1,7,18]) that the order of the diameter is typically between n and n · polylogn. The goal of this paper is to close the polylogarithmic gap between the upper and lower bounds, that is, to show that the diameter of the UST, scaled by n −1/2 , is tight.
Data Loading...
