Louigi Addario-Berry (McGill)

will speak on

Probabilistic aspects of minimum spanning trees

Time: 2:00PM
Date: Wed 14th February 2024
Location: E0.32 (beside Pi restaurant) [map]

Abstract: An extremely dynamic area in modern 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 results 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.

(This talk is part of the Probability series.)

PDF notice

Return to all seminars