Asymptotic enumeration of partially ordered sets

Deepak Dhar

Vol. 90 (1980), No. 2, 299–305

DOI: 10.2140/pjm.1980.90.299

Abstract

We define the entropy function S(ρ) = Lim_n−∞2n⁻² lnN(n,ρ), where N(n,ρ) is the number of distinct partial order relations which may be defined on a set of n elements such that a fraction ρ of the possible n(n − 1)∕2 pairs are comparable. We derive upper bounds to S(ρ) to show that S(ρ) < (1∕2)ln2 if ρ ≥ .699.

Mathematical Subject Classification 2000

Primary: 06A10, 06A10

Secondary: 05A15

Milestones

Received: 17 July 1979

Published: 1 October 1980