The average number of linear extensions of a partial order

DOI10.1016/S0097-3165(96)80001-XzbMath0842.05004OpenAlexW4213328692MaRDI QIDQ1906134

Hans Jürgen Prömel, Angelika Steger, Graham R. Brightwell

Publication date: 26 February 1996

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0097-3165(96)80001-x

zbMATH Keywords

partial orderlinear orderlinear extensionsaverage number

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Combinatorics of partially ordered sets (06A07) Graph theory (05C99)

Related Items

On the Boolean dimension of spherical orders ⋮ Succinct posets ⋮ The number of partial orders of fixed width ⋮ Searching in random partially ordered sets ⋮ Unnamed Item ⋮ On String Graph Limits and the Structure of a Typical String Graph ⋮ Entropy and the link action in the causal set path-sum ⋮ Almost every 2-SAT function is unate ⋮ Hereditary properties of combinatorial structures: Posets and oriented graphs ⋮ Linear extensions and comparable pairs in partial orders ⋮ Onset of the Asymptotic Regime for (Uniformly Random) Finite Orders ⋮ Reconstruction of Partial Orders and List Representation as Random Structures ⋮ Boolean layer cakes ⋮ Forbidden induced partial orders ⋮ Kolmogorov complexity and symmetric relational structures ⋮ MINING POSETS FROM LINEAR ORDERS ⋮ The number of 2-SAT functions

Cites Work

• Unnamed Item
• Unnamed Item
• The number of partially ordered sets with more points than incomparable pairs
• Linear extensions of random orders
• The lattice of natural partial orders
• Coloring Clique-free Graphs in Linear Expected Time
• Asymptotic Enumeration of Partial Orders on a Finite Set