Buongiorno
Martedì 16 Gennaio Michele Salvi terrà un seminario di Probabilità al Dipartimento di Matematica della Sapienza Sotto trovate i dettagli.
Grazie per l'attenzione Saluti Alessandra %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Speaker: Michele Salvi (Università di Tor Vergata) Where: Sala di Consiglio, Dip. di Matematica, Sapienza Università di Roma When: Tuesday 16 January, 14:00 (sharp)
Title:
*From the Uniform to the Minimum Spanning Tree*
Abstract:
A spanning tree of a graph G is a connected subset of G without cycles. The *Uniform Spanning Tree* (UST) is obtained by choosing one of the possible spanning trees of G at random. The *Minimum Spanning Tree* (MST) is realised instead by putting random weights on the edges of G and then selecting the spanning tree with the smallest weight. These two models exhibit markedly different behaviours: for example, their diameter on the complete graph with n nodes transitions from n^1/2 for the UST to n^1/3 for the MST. What lies in between?
We introduce a model of *Random Spanning Trees in Random Environment* (RSTRE) designed to interpolate between UST and MST. In particular, when the environment disorder is sufficiently low, the RSTRE on the complete graph has a diameter of n^1/2 as the UST. Conversely, when the disorder is high, the diameter behaves like n^1/3 as for the MST. We conjecture a smooth transition between these two values for intermediate levels of disorder. This talk is based on joint work with Rongfeng Sun and Luca Makowiec (NUS Singapore).