The number of partial orders of fixed width
Among various intractable problems, the exact enumerations of interesting classes of posets, labeled or unlabeled, form a significant subset, where obtaining asymptotic ``counts of the type: interesting \(f(n) +\) controlled ``vanishing factor \(e(n)\), with \(n\) the order parameter, i.e., the number of elements in the poset, has long been an important alternative, permitting developments of a variety of information, especially as it refers to probability models associated with ``random posets in some such interesting class of posets in order to describe ``general properties of such random posets, often in the form of some inequality obtained on the basis of the asymptotic count. The nature of the function \(f(n)\) is also of great interest here, as it is elsewhere, e.g., in number theory, since it may illuminate the gross nature of the process by which posets in the class under consideration are constructed. The authors of this paper are well experienced in the handling of such problems and they have done some heavyweight moving of obstacles in developing asymptotic formulas for \(\Omega_k(n)\), \(\Omega^u_k(n)\), the number of posets \(P\) of order \(n\) and width at most \(k\) which are labeled and unlabeled, respectively. Thus they show that \[ \Omega_2(n)= n!(4^n/n^{3/2})(8/25\sqrt\pi)(1+ O(1)) \] and \[ \Omega^u_2(n)= (4^n/n^{3/2})(4(2-\sqrt 3)/3\sqrt\pi)(1+ O(1)) \] and they obtain an estimate \[ n!4^{n(k- 1)}D_1(k)n^{-\alpha k^2}\leq \Omega_k(n)\leq n!4^{n(k- 1)}D_2(k)n^{\beta k^2} \] for positive constants \(\alpha\), \(\beta\) and functions \(D_1(k)\), \(D_2(k)\) depending on the width of the parameter \(k\). The arguments used to obtain these results involve much combinatorial magic as well as careful counts. Furthermore, due attention is also paid to implications following from these counts and in particular it is made clear that the notion of a restrictive poset and the answering of the question whether a poset is restrictive is both subtle and often interesting. Here \(P\) is restrictive if \(|\text{Forb}_n(P)|\leq n!c^n\) for all sufficiently large \(n\), where \(\text{Forb}_n(P)\) is the set of all posets on \(\{1,\dots,n\}\) which are \(P\)-free, an example of an interesting class of posets as pointed to at the beginning of this review.
- Asymptotic Enumeration of Partial Orders on a Finite Set
- Enumeration of Posets Generated by Disjoint Unions and Ordinal Sums
- Excluding Induced Subgraphs III: A General Asymptotic
- scientific article; zbMATH DE number 446489 (Why is no real title available?)
- scientific article; zbMATH DE number 6157245 (Why is no real title available?)
- scientific article; zbMATH DE number 3249395 (Why is no real title available?)
- The average number of linear extensions of a partial order
- The number of partially ordered sets with more points than incomparable pairs
- On estimating the number of order ideals in partial orders, with some applications
- Forbidden induced partial orders
- Height counting of unlabeled interval and \(N\)-free posets.
- Scaling limits for width two partially ordered sets: the incomparability window
- Counting partial orders with a fixed number of comparable pairs
- scientific article; zbMATH DE number 4016963 (Why is no real title available?)
- On posets of upper width 3.
- scientific article; zbMATH DE number 822736 (Why is no real title available?)
- Onset of the asymptotic regime for (uniformly random) finite orders
- On recurrence relation in the problem of enumeration of finite posets
- Discrete metric spaces: structure, enumeration, and 0-1 laws
- Some inequalities for partial orders
- Phase transitions in the evolution of partial orders
- Regressions and monotone chains: A Ramsey-type extremal problem for partial orders
- An asymptotic formula for the maximum size of an h-family in products of partially ordered sets
- Asymptotic enumeration of N-free partial orders
This page was built for publication: The number of partial orders of fixed width
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1362577)
