Linear extensions of a random partial order (Q1327606)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Linear extensions of a random partial order |
scientific article |
Statements
Linear extensions of a random partial order (English)
0 references
1994
0 references
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\).
0 references
random partial order
0 references
random graph
0 references
linear extensions
0 references