Random graph orders (Q911622)

Random graphs are graphs associated with a probability measure depending on rules of ``construction'' of the random graph. Random posets are considered in a similar light. Thus, the same poset P may be the poset element of several different random posets. In this very interesting paper the authors construct a random poset from a random graph with the p-value usually taken at \(1/2\) and the set of vertices taken to be \(\{1,...,n\}\) for some fixed n. The orientation is provided by the order \(i<j\) if (ij) is an edge and i is the smaller integer, then extending this by taking transitive closure. In constructing the diagram only covering relations are retained, so that some edges may be dropped from the original graph. Some parameters of the poset, such as height, will not be affected by the process of taking a transitive closure. The random posets obtained in the manner described are referred to as random graph orders (of a particular p-value). The authors demonstrate the existence of constants c and r such that: (1) \(.5654<c<.610\) and Pr(\(\lim_{n\to \infty}H_ n/n=c)=1\) where \(H_ n\) is the height of an n-point random graph order \((p=);\) (2) \(.034<r<.289\) and Pr(\(\lim_{n\to \infty}S_ n/n=c)=1\) where \(S_ n\) is the set-up or jump number of an n point random graph order \((p=).\) The flow of the counting arguments used indicates that the class developed is a nice one and corresponds well to intuitive notions of what one might expect. Other ideas are discussed, including the failure of the 0-1 law in the case of existence of unique minimal elements and a conjecture that dimension \(D_ n\) is sharply concentrated with expected value approximately \(\sqrt{2 \log n/\log 2}\). In order to study random diagrams it appears that the approach taken in this paper could also be a most natural one.