Skip to main content
SpringerLink
Log in

The Number of Unlabeled Orders on Fourteen Elements

  • Published:
Order Aims and scope Submit manuscript

Abstract

Lacking an explicit formula for the numbers T 0(n) of all order relations (equivalently: T 0 topologies) on n elements, those numbers have been explored only up to n=13 (unlabeled posets) and n=15 (labeled posets), respectively.

In a new approach, we used an orderly algorithm to (i) generate each unlabeled poset on up to 14 elements and (ii) collect enough information about the posets on 13 elements to be able to compute the number of labeled posets on 16 elements by means of a formula by Erné. Unlike other methods, our algorithm avoids isomorphism tests and can therefore be parallelized quite easily. The underlying principle of successively adding new elements to small objects is applicable to lattices and other kinds of order structures, too.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Beck, I., Extensions of partial orders, Preprint, University of Haifa.

  2. Borevi?, Z. I. (1982) On the periodicity of residues of the number of finite labeled T 0-topologies, Zap. Nau?n. Sem. Leningrad. Otdel. Mat. Inst. Steklov (LOMI) 114, 32-36, 217 (Russian).

    Google Scholar 

  3. Brightwell, G., Prömel, H. J. and Steger, A. The average number of linear extensions of a partial order, Preprint, Rheinische Friedrich-Wilhelms-Universität Bonn, to appear in J. Combin. Theory Ser. A.

  4. Chaunier, C. and Lyger?s, N. (1991) Progrès dans l'énumération des posets, C.R. Acad. Sci. Paris Sér. I 314, 691-694.

    Google Scholar 

  5. Chaunier, C. and Lyger?s, N. (1992) The number of orders with thirteen elements, Order 9(3), 203-204.

    Google Scholar 

  6. Comtet, L. (1966) Recouvrements, bases de filtre et topologies d'un ensemble fini, V. R. Acad. Sci. Paris, Ser. A-B 262, 1091-1094.

    Google Scholar 

  7. Culberson, J. C. and Rawlins, G. J. E. (1991) New results from an algorithm for counting posets, Order 7(4), 361-374.

    Google Scholar 

  8. Das, S. K. (1977) A machine representation of finite T 0 topologies, J. ACM 24, 676-692.

    Google Scholar 

  9. Erné, M. (1970) Endliche Topologien, Diploma thesis, Universität München.

  10. Erné, M. (1972) Struktur-und Anzahlformeln für Topologien auf endlichen Mengen, PhD dissertation, Westfälische Wilhelms-Universität zu Münster.

  11. Erné, M., Heitzig, J. and Reinhold, J. (2000) On the number of distributive lattices, Preprint.

  12. Erné, M. and Stege, K. (1991) Counting finite posets and topologies, Order 8, 247-265.

    Google Scholar 

  13. Erné, M. and Stege, K. (1993) The number of topologies and orders on 15 points, Preprint, Universität Hannover.

  14. Evans, J. W., Harary, F. and Lynn, M. S. (1967) On the computer enumeration of finite topologies, Comm. ACM 10, 295-297, 313.

    Google Scholar 

  15. Heitzig, J. and Reinhold, J. (1999) Counting finite lattices, Preprint, www-ifm.math.unihannover. de/forschung/preprintsifm.html.

  16. Kleitman, D. J. and Rothschild, B. L. (1975) Asymptotic enumeration of partial orders on a finite set, Trans. Amer. Math. Soc. 205, 205-220.

    Google Scholar 

  17. Knopfmacher, J. (1969) Note on finite topological spaces, J. Austral. Math. Soc. 9, 252-256.

    Google Scholar 

  18. Koda, Y. (1994) The numbers of finite lattices and finite topologies, Bull. Inst. Combin. Appl. 10, 83-89.

    Google Scholar 

  19. McKay, B. D. (1998) Isomorph-free exhaustive generation, J. Algorithms 26(2), 306-324.

    Google Scholar 

  20. Möhring, R. H. (1984) Algorithmic aspects of comparability graphs and interval graphs, in Graphs and Order: The Role of Graphs in the Theory of Ordered Sets and Its Applications, NATO Adv. Stud. Inst. Ser. C: Math. Phys. Sci. 147, pp. 41-102.

  21. Read, R. C. (1978) Every one a winner or how to avoid isomorphism search when cataloguing combinatorial configurations, in Algorithmic Aspects of Combinatorics (Conf., Vancouver Island, B.C., 1976), Ann. Discrete Math. 2, pp. 107-120.

  22. Stege, K. (1990) Kombinatorische Anzahlbestimmungen für Quasiordnungen und Topologien, Diploma thesis, Universität Hannover.

  23. Wright, J. (1972) Cycle indicators of certain classes of types of quasi-orders or topologies, PhD Dissertation, University of Rochester, NY.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institut für Mathematik, Universität Hannover, Welfengarten 1, 30167, Hannover, Germany

    Jobst Heitzig

  2. Institut für Mathematik, Universität Hannover, Welfengarten 1, 30167, Hannover, Germany

    Jürgen Reinhold

Authors
  1. Jobst Heitzig
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jürgen Reinhold
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Heitzig, J., Reinhold, J. The Number of Unlabeled Orders on Fourteen Elements. Order 17, 333–341 (2000). https://doi.org/10.1023/A:1006431609027

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1006431609027

Search

Navigation