The random binary growth model

N Georgiou

Research output: Contribution to journalArticle (Academic Journal)peer-review

6 Citations (Scopus)

Abstract

We describe a family of models of random partial orders, called \emph{classical sequential growth models}, and study a specific case, which is the simplest interesting model, called a \emph{random binary growth model}. This model produces a random poset, called a \emph{random binary order}, $B_2$, on the vertex set $\mathbb{N}$ by considering each vertex $n \geq 2$ in turn and placing it above 2 vertices chosen uniformly at random from the set $\{0,\dotsc,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$.
Translated title of the contribution The random binary growth model English 520 - 552 33 Random Structures and Algorithms 27 (4) https://doi.org/10.1002/rsa.20083 Published - Dec 2005

Bibliographical note

Publisher: John Wiley
Other identifier: IDS Number: 984EL