show/hide this revision's text 2 Clarified that question is about expected diameter not worst-case diameter.

Let $P$ be a pointset consisting of $n$ uniformly random elements of $[0,1]^2$. It is known that the diameter (greatest number of edges in any shortest path between two points) of the Delaunay triangulation of $P$ is of has expected order $\Theta(\sqrt{n})$; the upper bound follows from work by Bose and Devroye, and the lower bound follows from a more general result on weighted Delaunay triangulations by Pimentel.

Since the Euclidean MST $T=T(P)$ is a subgraph of the Delaunay triangulation, it follows that $T$ has expected diameter of order at least $\sqrt{n}$. It seems a plausible guess that the expected order is in fact $\Theta(\sqrt{n})$. However, I know of no non-trivial upper bound on the expected diameter of $T$. (In particular, I don't even know if it is $o(n)$ -- or even if it is less than, say, $n/10$.) Do you?

What upper bounds are known for the expected diameter of $T$, the minimum spanning tree of $n$ uniformly random points in $[0,1]^2$?

show/hide this revision's text 1

What upper bounds are known for the diameter of the minimum spanning tree of $n$ uniformly random points in $[0,1]^2$?

Let $P$ be a pointset consisting of $n$ uniformly random elements of $[0,1]^2$. It is known that the diameter (greatest number of edges in any shortest path between two points) of the Delaunay triangulation of $P$ is of order $\Theta(\sqrt{n})$; the upper bound follows from work by Bose and Devroye, and the lower bound follows from a more general result on weighted Delaunay triangulations by Pimentel.

Since the Euclidean MST $T=T(P)$ is a subgraph of the Delaunay triangulation, it follows that $T$ has diameter of order at least $\sqrt{n}$. It seems a plausible guess that the order is in fact $\Theta(\sqrt{n})$. However, I know of no non-trivial upper bound on $T$. (In particular, I don't even know if it is $o(n)$ -- or even if it is less than, say, $n/10$.) Do you?

What upper bounds are known for the diameter of $T$, the minimum spanning tree of $n$ uniformly random points in $[0,1]^2$?