Title: Ungarian Markov Chains
Speaker: Colin Defant (MIT)
Abstract: Inspired by Ungar's solution to the famous slopes problem, we introduce Ungar moves, which are operations that can be performed on elements of a finite lattice L. Applying Ungar moves randomly results in an absorbing Markov chain that we call the Ungarian Markov chain of L. For a variety of interesting lattices L, we focus on estimating E(L), the expected number of steps of this Markov chain needed to get from the top element of L to the bottom element of L. When L is distributive, its Ungarian Markov chain is equivalent to an instance of the well-studied random process known as last-passage percolation with geometric weights. One of our main results states that if L is a trim lattice, then E(L) is at most E(spine(L)), where spine(L) is a specific distributive sublattice of L called the spine of L. Combining this lattice-theoretic theorem with known results about last-passage percolation yields a powerful method for proving upper bounds for E(L) when L is trim. This talk is based on joint work with Rupert Li.
