What is the expected height of a random finite partial order?

148 Views Asked by At

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 a finite poset $(P, <)$ is the length of the longest maximal chain in $P$.

Now, suppose we fix $n \in \mathbb{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, <)$?

Context: I've been working on an algorithm whose worst-case time complexity is exponential in the height of a certain finite poset.