Linear extensions of a random partial order
Let \(G_ n\) be the graph associated with the natural strict order relation on \(\{1,\dots,n\}\). Consider the random graph \(G_{n,p}\) in which each possible edge (i.e. edge in \(G_ n\)) appears with probability \(p\), where \(0< p<1\), independently of all other edges. The authors study asymptotics of the number of linear extensions of the transitive closure of \(G_{n,p}\) for fixed \(p\) and \(n\to\infty\).
scientific article; zbMATH DE number 591422