Hostname: page-component-586b7cd67f-t7fkt Total loading time: 0 Render date: 2024-11-29T01:40:22.694Z Has data issue: false hasContentIssue false

Counting Partial Orders with a Fixed Number of Comparable Pairs

Published online by Cambridge University Press:  24 May 2001

HANS JÜRGEN PRÖMEL
Affiliation:
Institut für Informatik, Humboldt–Universität zu Berlin, 10099 Berlin, Germany (e-mail: [email protected], [email protected])
ANGELIKA STEGER
Affiliation:
Institut für Informatik, Technische Universität München, 80290 München, Germany (e-mail: [email protected])
ANUSCH TARAZ
Affiliation:
Institut für Informatik, Humboldt–Universität zu Berlin, 10099 Berlin, Germany (e-mail: [email protected], [email protected])

Abstract

In 1978, Dhar suggested a model of a lattice gas whose states are partial orders. In this context he raised the question of determining the number of partial orders with a fixed number of comparable pairs. Dhar conjectured that in order to find a good approximation to this number, it should suffice to enumerate families of layer posets. In this paper we prove this conjecture and thereby prepare the ground for a complete answer to the question.

Type
Research Article
Copyright
2001 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)