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

average numberlinear extensionslinear orderpartial order

Mathematics Subject Classification ID

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

Review text

\textit{D. J. Kleitman} and \textit{B. L. Rothschild} [Trans. Am. Math. Soc. 205, 205-220 (1975; Zbl 0302.05007)] gave an asymptotic formula for the number of partial orders in an \(n\) element set. The authors give a shorter proof of this result and extend it to count linear extensions of a given partial order. Thus asymptotic formulas are obtained for the average number of linear extensions of an \(n\) element partial order and for the number of suborders of an \(n\) element linear order. Some graph theory technique is used in the proofs.

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

• Asymptotic Enumeration of Partial Orders on a Finite Set
• Coloring Clique-free Graphs in Linear Expected Time
• scientific article; zbMATH DE number 446489 (Why is no real title available?)
• scientific article; zbMATH DE number 3349081 (Why is no real title available?)
• 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

(31)

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

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)