4.5 ***Some questions : Random spanning trees***

Let us consider the following weighted graph : $K_n$, the complete graph is our graph and the edge weights ${\{w(e)\}}_{e\in E(K_n)}$ are i.i.d. $U[0,1]$ random variables. Let $M_n$ denote the minimal spanning tree (why is it unique ?). Alan Frieze ([Frieze 1985]) showed that $w(M_n)\to \zeta (3)={\sum }_{k=1}^{\mathrm{\infty }}{k}^{-3}=1.202\mathrm{\dots }$ where $\zeta$ is the famed Riemann-zeta function. See [Addario-Berry 2015] for a newer proof.

We will now consider another weighted graph : Let $V_1,\mathrm{\dots },V_n$ denote i.i.d. uniform points in ${[0,1]}^d$. Let $G_n$ be the complete graph on $\{V_1,\mathrm{\dots },V_n\}$ with edge weights being the euclidean distance between the points i.e., $w(V_i,V_j)=|V_i-V_j|$ for $i\ne j$. Let $M_n$ denote the minimal spanning tree (why is it unique ?). It is known that $n^{-(d-1)/d}w(M_n)\to C_d$ for some $C_d\in (0,\mathrm{\infty })$. See the wonderful monograph of [Steele 1997] for a proof of this and various other related results in probabilistic combinatorial optimization such as stochastic travelling salesman problem, minimal matchings etc. Determining more information about the constant $C_d$ is still open. See [Bertsimas 1990, Rhee 1992, Frieze and Pegden 2017] for some progress in this direction.

See the following talk by Lougi Addario-Berry for more on the thriving research on probabilistic aspects of minimal spanning trees - http://problab.ca/louigi/talks/Msts.pdf.