Large Deviation Properties of Minimum Spanning Trees for Random Graphs

Abstract

We study the large-deviation properties of minimum spanning trees for two ensembles of random graphs with $N$ nodes. First, we consider complete graphs. Second, we study Erdős-Rényi (ER) random graphs with edge probability $p=c/N$ conditioned to be connected. By using large-deviation Markov chain sampling, we are able to obtain the distribution $P(W)$ of the spanning-tree weight $W$ down to probability densities as small as $10^{-300}$. For the complete graph, we confirm analytical predictions with respect to the expectation value. For both ensembles, the large deviation principle is fulfilled. For the connected ER graphs, we observe a remarkable change of the distributions at the value of $c=1$, which is the percolation threshold for the original ER ensemble.

9 pages, 12 figures