Speaker: Peter Winkler (Bell Labs)
Title: Building Uniformly Random Objects
Abstract: Finite combinatorial objects often come with notions of
size and containment. It is natural to ask whether they
can be constructed step by step in such a way that each
object contains the last and is uniformly random among
objects of its size.
For example: starting with a triangle drawn on the plane,
can you add line segments two at a time so that at every
stage you have a uniformly random triangulation of a polygon?
We will describe such processes for this and some more
general structures related to Catalan numbers. (Joint work
with Malwina Luczak, Cambridge.)