Building Uniformly Random Objects

Peter Winkler

Bell Labs

April 24,
refreshments at 3:45pm


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.)

Speaker's Contact Info: pw(at-sign)

Return to seminar home page

Combinatorics Seminar, Mathematics Department, MIT, sara(at-sign)

Page loaded on March 25, 2002 at 06:11 PM. Copyright © 1998-99, Sara C. Billey. All rights reserved.