Building Uniformly Random ObjectsPeter WinklerBell Labs
April 24,

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.) 
Combinatorics Seminar, Mathematics Department, MIT, sara(atsign)math.mit.edu 

