The Structure of Random Graph Orders

The random graph order Pn,p is defined by taking a random graph Gn,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 Pn,p almost surely has posts if np⁻¹e-π²/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 Hn,p, we prove that, for p in an appropriate range, there are functions αH(p) =e(1+o(1))p and βH(p) such that (Hn,p - αH(p)n)/√ n βH(p) N(0,1).