Probability Seminar

Moon DuchinCornell University
Models of random spanning trees

Monday, March 17, 2025 - 4:00pm
Malott 406

Suppose you want a random spanning tree in a given graph G.  The two most popular ways to do this are UST (uniformly random) and MST (minimum, by random weights).  They are not the same, but there is surprisingly little literature on how the probability distributions differ!  I'll give some results on the quantitative properties of MST that justify the slogan "Greedy trees are bushy."  This will end up delivering some new insight into so-called intransitive dice, where you can have three random variables so that A>B, B>C, and C>A are all more likely than not.  (Based on joint work with Eric Babson, Annina Iseli, Pietro Poggi-Corradini, Dylan Thurston, and Jamie Tucker-Foltz.)