Georgia Institute of Technology College of Sciences

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)