Louigi Addario-Berry
Université McGill
March 10, 2017 from 16:00 to 18:00 (Montreal/EST time) On location
Colloquium presented by Louigi Addario-Berry (Université McGill)
One of the most dynamic areas of probability theory is the study of the behaviour of discrete optimization problems on random inputs. My talk will focus on the probabilistic analysis of one of the first and foundational combinatorial optimization problems: the minimum spanning tree problem. The structure of a random minimum spanning tree (MST) of a graph G turns out to be intimately linked to the behaviour of critical and nearcritical percolation on G. I will describe this connection, and present some results on the structure, scaling limits, and volume growth of random MSTs. It turns out that, on highdimensional graphs, random minimum spanning trees are expected to be threedimensional when viewed intrinsically, and sixdimensional when viewed as embedded objects. Based on joint works with Nicolas Broutin, Christina Goldschmidt, Simon Griffiths, Ross Kang, Gregory Miermont, Bruce Reed, Sanchayan Sen.
Address
CRM, Université de Montréal, Pavillon André-Aisenstadt, 2920 Chemin de la Tour, room 6254