Asymptotic enumeration of N-free partial orders (Q913831): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
Set OpenAlex properties.
 
(One intermediate revision by one other user not shown)
Property / cites work
 
Property / cites work: Counting two-dimensional posets / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3872508 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4918392 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Maximal chains and antichains / rank
 
Normal rank
Property / cites work
 
Property / cites work: On some complexity properties of N-free posets and posets with bounded decomposition diameter / rank
 
Normal rank
Property / cites work
 
Property / cites work: Asymptotic Enumeration of Partial Orders on a Finite Set / rank
 
Normal rank
Property / cites work
 
Property / cites work: Optimal Linear Extensions by Interchanging Chains / rank
 
Normal rank
Property / cites work
 
Property / cites work: Enumeration of Posets Generated by Disjoint Unions and Ordinal Sums / rank
 
Normal rank
Property / cites work
 
Property / cites work: The Recognition of Series Parallel Digraphs / rank
 
Normal rank
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1007/bf00563522 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2010697617 / rank
 
Normal rank

Latest revision as of 08:44, 30 July 2024

scientific article
Language Label Description Also known as
English
Asymptotic enumeration of N-free partial orders
scientific article

    Statements

    Asymptotic enumeration of N-free partial orders (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    1989
    0 references
    It is well-known that N-free posets P are nice posets with respect to a great variety of ``problems'' in poset theory, although they are not as nice as the series-parallel posets (obtainable from a singleton by sum and ordinal sum operations) of which they form a superset. From the viewpoint of enumeration, density results or other probabilistic looks at posets it is useful to be able to provide accurate actual or asymptotic estimates of various quantities involved. In this paper the authors show that the number of unlabeled N-free posets with n elements is \(N(n)=2 \exp (2n \log n+O(n \log n))\). An interesting intermediate step in this computation is the determination of the generating function \(J(x)=\sum j(n)x^ n\) of N-free interval orders in which no two distinct elements have the same lower covers and the same upper covers, these being obtained from a particular block decomposition of the covering graph of a poset. The number j(n) is determined to be \(\sum^{n+1}_{k=2}\left( \begin{matrix} (k-1)(k-2)/2\\ n-k+1\end{matrix} \right)\). Using other counts already available or developed by the authors, a table counting various classes of posets up to \(n=12\) is also provided.
    0 references
    asymptotic enumeration
    0 references
    N-free posets
    0 references
    series-parallel posets
    0 references
    generating function
    0 references
    N-free interval orders
    0 references
    covering graph of a poset
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references