Premium
The random binary growth model
Author(s) -
Georgiou Nicholas
Publication year - 2005
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20083
Subject(s) - combinatorics , mathematics , vertex (graph theory) , upper and lower bounds , binary number , partially ordered set , discrete mathematics , transitive relation , random binary tree , vertex model , binary tree , mathematical analysis , graph , arithmetic
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 2 , 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 2 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 2 does not contain P . © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005