***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Speaker: Colin Defant (MIT)

Thursday 9th March, 3:00 in Fine Hall 224.

Title: Ungarian Markov chains 

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. 

		----------------------------------

Anyone wishing to be added to or removed from the mailing list should
contact Paul Seymour (pds@math.princeton.edu)