- Series
- Graph Theory Seminar
- Time
- Thursday, November 19, 2009 - 12:05pm for 1 hour (actually 50 minutes)
- Location
- Skiles 255
- Speaker
- Graham Brightwell – London School of Economics
- Organizer
- Robin Thomas
Several interesting models of random partial orders can be described via a
process that builds the partial order one step at a time, at each point
adding a new maximal element. This process therefore generates a linear
extension of the partial order in tandem with the partial order itself. A
natural condition to demand of such processes is that, if we condition on
the occurrence of some finite partial order after a given number of steps,
then each linear extension of that partial order is equally likely. This
condition is called "order-invariance".
The class of order-invariant processes includes processes generating a
random infinite partial order, as well as those that amount to taking a
random linear extension of a fixed infinite poset.
Our goal is to study order-invariant processes in general. In this talk, I
shall focus on some of the combinatorial problems that arise.
(joint work with Malwina Luczak)