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 contributionThe random binary growth model
Original languageEnglish
Pages (from-to)520 - 552
Number of pages33
JournalRandom Structures and Algorithms
Volume27 (4)
DOIs
Publication statusPublished - Dec 2005

Bibliographical note

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

Fingerprint Dive into the research topics of 'The random binary growth model'. Together they form a unique fingerprint.

Cite this