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 relation i < j, and taking the transitive closure. A post in a partial order is an element comparable with all others. We investigate the occurrence 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 order-for instance, the height, the logarithm of the number of linear extensions, and the number of incomparable pairs-behave as normal random variables. For instance, for the height H-n,H-p, we prove that, for p in 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).