UVictoria Dynamics and Probability Seminar: Benoit Corsini

In this talk, I will present a recent work in which two co-authors and myself studied the behaviour of a local algorithm optimizing the weight of a graph. More precisely, the process starts with a given subgraph H of the complete graph with uniform weights and a maximal weight W, and inductively replaces a subgraph of H and of weight less than W by the minimum spanning tree on the corresponding set of vertices. Our main result shows that there is a sharp threshold for W regarding the asymptotic behaviour of this algorithm (i.e. with high probability): if W is less than 1, it is impossible to reach the global minimum spanning tree, whereas it is possible when W is larger than 1. Since this work introduces a new type of local algorithm, I will also present some related open problems. In particular, our results prove when such algorithms can reach the global minimum spanning tree and it is then only natural to ask how fast they can do so when possible. The answer to this question actually relates to efficiently packing sets of uniforms into a special type of partition and leads to a surprisingly difficult open question.