Linear extensions of a random partial order
type: Item
instance of: scholarly article
title: Linear extensions of a random partial order
zbMATH Open document ID: 0808.06002
author: Noga Alon
author: Béla Bollobás
author: Svante Janson
author: Graham Brightwell
published in: The Annals of Applied Probability
publication date: 1994-01-01T00:00:00Z
review text: 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\).
reviewed by: Josef Niederle
Mathematics Subject Classification ID: 06A06
Mathematics Subject Classification ID: 05C80
zbMATH DE Number: 591422
zbMATH Keywords: random partial order
zbMATH Keywords: random graph
zbMATH Keywords: linear extensions
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1214/aoap/1177005202
OpenAlex ID: W2025893614
DOI: 10.1214/AOAP/1177005202
Recommended article: Linear extensions of random orders
Recommended article: Generating a random linear extension of a partial order
Recommended article: Random \(k\)-dimensional orders: Width and number of linear extensions
Recommended article: Q4891475
Recommended article: Linear extensions and order polynomials of finite partially ordered sets
Recommended article: Reducts of the random partial order
Recommended article: Linear extensions of additive partial orders
Recommended article: Q3201107
description: scientific article; zbMATH DE number 591422