The Structure of Random Graph Orders

The random graph order P₍, ₏ is defined by taking a random graph G₍, ₏ 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 P₍, ₏ almost surely has posts if np^-1e^-²/3p, 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 many 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₍, ₏, we prove that, for p in an appropriate range, there are functions H (p) =e (1+o (1) ) p and H (p) such that (H₍, ₏ - H (p) n) / n H (p) N (0, 1).