Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Asymptotic enumeration of partial orders on a finite set


Authors: D. J. Kleitman and B. L. Rothschild
Journal: Trans. Amer. Math. Soc. 205 (1975), 205-220
MSC: Primary 05A15; Secondary 06A10
DOI: https://doi.org/10.1090/S0002-9947-1975-0369090-9
MathSciNet review: 0369090
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: By considering special cases, the number $ {P_n}$ of partially ordered sets on a set of $ n$ elements is shown to be $ (1 + O(1/n)){Q_n}$, where $ {Q_n}$ is the number of partially ordered sets in one of the special classes. The number $ {Q_n}$ can be estimated, and we ultimately obtain

$\displaystyle {P_n} = \left( {1 + O\left( {\frac{1}{n}} \right)} \right)\left( ... ...{{2^i} - 1} \right)}^j}{{\left( {{2^j} - 1} \right)}^{n - i - j}}} } } \right).$


References [Enhancements On Off] (What's this?)

  • [1] K. K.-H. Butler, The number of finite partially ordered sets, Notices Amer. Math. Soc. 18 (1971), 1092. Abstract #71T-A250.
  • [2] S. D. Chatterji, The number of topologies on $ n$ points, Kent State University, NASA Technical Report, 1966.
  • [3] L. Comptet, Recouvrements, bases de filtre et topologies d'un ensemble fini, C. R. Acad. Sci. Paris Sér. A-B 262 (1966), A 1091-A 1094. MR 34 #1209. MR 0201325 (34:1209)
  • [4] J. W. Evans, F. Harary and M. S. Lynn, On the computer enumeration of finite topologies, Comm. ACM 10 (1967), 295-298.
  • [5] D. Klarner, The number of graded partially ordered sets, J. Combinatorial Theory 6 (1969), 12-19. MR 38 #4333. MR 0236035 (38:4333)
  • [6] -, The number of classes of isomorphic graded partially ordered sets, J. Combinatorial Theory 9 (1970), 412-419. MR 42 #2989. MR 0268090 (42:2989)
  • [7] D. Kleitman and B. Rothschild, The number of finite topologies, Proc. Amer. Math. Soc. 25 (1970), 276-282. MR 40 #7157. MR 0253944 (40:7157)
  • [8] V. Krishnamurthy, On the number of topologies on a finite set, Amer. Math. Monthly 73 (1966), 154-157. MR 34 #1208. MR 0201324 (34:1208)
  • [9] A. Shafaat, On the number of topologies definable on a finite set, J. Austral. Math. Soc. 8 (1968), 194-198. MR 37 #1263. MR 0225670 (37:1263)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 05A15, 06A10

Retrieve articles in all journals with MSC: 05A15, 06A10


Additional Information

DOI: https://doi.org/10.1090/S0002-9947-1975-0369090-9
Article copyright: © Copyright 1975 American Mathematical Society

American Mathematical Society