The number of partial orders of fixed width
type: Item
instance of: scholarly article
title: The number of partial orders of fixed width
zbMATH Open document ID: 0878.06002
DOI: 10.1007/BF00405592
author: Graham Brightwell
author: Sarah Goodall
published in: Order
publication date: 1998-01-04T00:00:00Z
review text: 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…
Mathematics Subject Classification ID: 06A07
Mathematics Subject Classification ID: 05A16
zbMATH DE Number: 1044145
zbMATH Keywords: partial order
zbMATH Keywords: asymptotic enumeration
zbMATH Keywords: width
zbMATH Keywords: restrictive poset
reviewed by: J. Neggers
MaRDI profile type: Publication
cites work: Q3142411
cites work: The average number of linear extensions of a partial order
cites work: Q4918392
cites work: Q5538132
cites work: Asymptotic Enumeration of Partial Orders on a Finite Set
cites work: Excluding Induced Subgraphs III: A General Asymptotic
cites work: Enumeration of Posets Generated by Disjoint Unions and Ordinal Sums
description: scientific article; zbMATH DE number 1044145