The number of partial orders of fixed width (Q1362577): Difference between revisions

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.