The random binary growth model

We describe a family of models of random partial orders, called classical sequential growth models, and study a specific case, which is the simplest interesting model, called a random binary growth model. This model produces a random poset, called a random binary order, B₂, on the vertex set ? by considering each vertex n ≥ 2 in turn and placing it above 2 vertices chosen uniformly at random from the set {0,…,n ? 1} (with additional relations added to ensure transitivity). We show that B₂ has infinite dimension, almost surely. Using the differential equation method of Wormald, we can closely approximate the size of the up‐set of an arbitrary vertex. We give an upper bound on the largest vertex incomparable with vertex n, which is polynomial in n, and, using this bound, we provide an example of a poset P, such that there is a positive probability that B₂ does not contain P. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005