Random partial orders and random linear extensions
|
Tue, 27/01/2009 14:30 |
Graham Brightwell (LSE) |
Combinatorial Theory Seminar  |
L3 |
| Random partial orders and random linear extensions 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 explain some of the problems that need to be resolved, and discuss some of the combinatorial problems that arise. (joint work with Malwina Luczak) | |||