THE STRUCTURE OF RANDOM GRAPH ORDERS

The random graph order P-n,P-p is defined by taking a random graph G(n ,p) on vertex set [n], treating an edge ij with i < j in [n] as a rela tion i < j, and taking the transitive closure. A post in a partial ord er is an element comparable with all others. We investigate the occurr ence of posts in random graph orders, showing in particular that Pa,p almost surely has posts if np(-1)e(-pi 2/3p) --> infinity, but almost surely does not if this quantity tends to 0. If there are many posts, the partial order decomposes as a linear sum of smaller orders, and we use this decomposition to show that parameters of a random graph orde r-for instance, the height, the logarithm of the number of linear exte nsions, and the number of incomparable pairs-behave as normal random v ariables. For instance, for the height H-n,H-p, we prove that, for p i n an appropriate range, there are functions alpha(H)(p) = e(1 + o(1))p and beta(H)(p) such that (H-n,H-p - alpha(H)(p)n)/root n beta(H)(p)-- >N-d(0,1).