The average number of linear extensions of a partial order

DOI10.1016/S0097-3165(96)80001-XMaRDI QIDQ1906134zbMATH OpenOpenAlexFDO

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

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)

Recommendations

• scientific article; zbMATH DE number 4016963
• Linear extensions of random orders
• Linear extensions and comparable pairs in partial orders
• scientific article; zbMATH DE number 924935
• Inequalities for the number of linear extensions

Cites work

• scientific article; zbMATH DE number 446489 (Why is no real title available?)
• scientific article; zbMATH DE number 3349081 (Why is no real title available?)
• Asymptotic Enumeration of Partial Orders on a Finite Set
• Coloring Clique-free Graphs in Linear Expected Time
• Linear extensions of random orders
• The lattice of natural partial orders
• The number of partially ordered sets with more points than incomparable pairs

Cited in

(28)

• A recurrence for linear extensions
• Linear extensions and comparable pairs in partial orders
• scientific article; zbMATH DE number 4016963 (Why is no real title available?)
• The number of linear extensions of subset ordering
• Entropy and the link action in the causal set path-sum
• On the Boolean dimension of spherical orders
• Onset of the asymptotic regime for (uniformly random) finite orders
• Boolean layer cakes
• Linear extension numbers of \(n\)-element posets
• Searching in random partially ordered sets
• Kolmogorov complexity and symmetric relational structures
• Forbidden induced partial orders
• The number of partial orders of fixed width
• Phase transitions in the evolution of partial orders
• Succinct posets
• The number of 2-SAT functions
• Mining posets from linear orders.
• Hereditary properties of combinatorial structures: Posets and oriented graphs
• Reconstruction of partial orders and list representation as random structures
• On string graph limits and the structure of a typical string graph
• Inequalities for the number of linear extensions
• scientific article; zbMATH DE number 924935 (Why is no real title available?)
• The number of linear extensions of bipartite graphs
• Almost every 2-SAT function is unate
• Frequency estimates for linear extension majority cycles on partial orders
• scientific article; zbMATH DE number 3985224 (Why is no real title available?)
• An asymptotic formula for the maximum size of an h-family in products of partially ordered sets
• scientific article; zbMATH DE number 7666239 (Why is no real title available?)

This page was built for publication: The average number of linear extensions of a partial order

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1906134)