Models of random partial orders

Summary

Introduction

The theory of random graphs has proved to be a success. It has provided many interesting questions, provoking the development of new techniques on the boundary between combinatorics and probability theory. Random graphs have also proved tremendously valuable in applications outside the theory: firstly in extremal questions, where bounds obtained by nonconstructive means are often the best known, and secondly in questions coming from computer science, or, for instance, from biology, which turn out to translate directly into natural questions about particular models of random graphs. It is not appropriate to give an extensive bibliography here, but the place to set off on a serious study of random graphs is the monograph by Bollobas [7].

Another basic combinatorial structure is that of finite partially ordered sets, and it is very natural to ask whether an equally successful theory of random partial orders can be developed. Regrettably, the simple answer will have to be “no”. One reason for this is perhaps that partial orders occur less often in applications than do graphs, but the more important problem is mathematical: the lack of “independence”.

To explain this, it is convenient to recall first the most basic model of random graphs. Let n be a positive integer, and p a real number strictly between 0 and 1. Set [n] = { 1, …, n}. For each pair (i, j) of integers from [n] with i < j, let X_ij be a Bernoulli random variable with Pv(X_ij = 1) = p, with all the X_ij mutually independent.