Centre for Discrete and Applicable Mathematics
	CDAM Research Report, LSE-CDAM-2003-17 August 2003

Abstract

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 N 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.

A PDF file (356 kB) with the full contents of this report can be downloaded by clicking here.

Alternatively, if you would like to get a free hard copy of this report, please send the number of this report, LSE-CDAM-2003-17, together with your name and postal address to: Sorry, this report is currently yet not available in electronic format. To obtain a free hard copy, please send the number of this report, LSE-CDAM-2003-17, together with your name and postal address to:

		CDAM Research Reports Series Centre for Discrete and Applicable Mathematics London School of Economics Houghton Street London WC2A 2AE, U.K.
		Phone: +44(0)-20-7955 7732. Fax: +44(0)-20-7955 6877. Email: info@maths.lse.ac.uk

		Introduction to the CDAM Research Report Series.
		CDAM Homepage.

Last changed: Wed 9 Feb 2005
For comments go to: http://www.maths.lse.ac.uk/webmaster.html