1
$\begingroup$

The following question has arisen tangentially in relation to the analysis of the complexity of an algorithm in my Master's thesis, but my background in combinatorics is limited, and I'm having trouble finding a clear answer:

Let $(P,<)$ be a finite poset. A subset $M \subseteq P$ is a maximal chain if $(M,<)$ is a chain and there is no $N \subseteq P$ such that $M \subsetneq N$ and $(N,<)$ is a chain. The height of $(P,<)$ is the length of the longest maximal chain in $P$.

Now, suppose we fix $n∈ℕ$, and choose a poset $(P,<)$ uniformly at random from the set of posets with n elements.

What is a good upper bound on the expected value of the height of $(P,<)$?

$\endgroup$
4
$\begingroup$

It is known that most posets of large order have three levels. That is, there are maximal elements plus their immediate children and grandchildren, and nothing else.

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

Experimentally, this asymptotic behaviour sets in very slowly as as the order increases.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.