Quicklists
Javascript must be enabled

Louigi Addario-Berry : Probabilistic aspects of minimum spanning trees

Abstract: 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 near-critical percolation on G. I will describe this connection and some of my results, alone and with coauthors, on the structure, scaling limits, and volume growth of random MSTs. It turns out that, on high-dimensional graphs, random minimum spanning trees are expected to be three-dimensional when viewed intrinsically, and six-dimensional when viewed as embedded objects.

Add to Favorites

Please select playlist name from following

Create new playlist

Report Video

Please select the category that most closely reflects your concern about the video, so that we can review it and determine whether it violates our Community Guidelines or isn’t appropriate for all viewers. Abusing this feature is also a violation of the Community Guidelines, so don’t do it.

0 Comments

Comments Disabled For This Video