25
$\begingroup$

I am interested in any known results/empirical studies done on the average height of a poset with $N$ elements. Obviously this would depend on how that poset relation was randomly defined, however, at this point, I'll take any reasonable result on the topic regardless of how the poset was formed.

In my case $N$ is a very large number (billions of elements), so I am interested whether the height $h \ll N$ asymptotically.

$\endgroup$

1 Answer 1

36
$\begingroup$

In Asymptotic Enumeration of Partial Orders on a Finite Set (1975), Kleitman and Rothschild showed that almost all partial orders on an $n$-element set have a simple description: they have three "layers" $L_1$, $L_2$, and $L_3$ of incomparable elements, of size $n/4$, $n/2$, and $n/4$ respectively. Each element of $L_1$ is covered by about half the elements of $L_2$. Likewise for $L_2$ and $L_3$, and in the reverse direction.

So almost all finite posets have height $3$.

(If you don't have the time/effort to read Kleitman and Rothschild's paper, I came across this reference via G. Brightwell, Linear extensions of random orders, Discrete Math. 125 (1994) pp. 87–96. If memory serves, Brightwell's paper presents a good summary of this one.)

$\endgroup$
4
  • $\begingroup$ Thank you, this is exactly what I need! I definitely have both the time and the willingness to read the paper. Thank you! $\endgroup$ Sep 20, 2020 at 5:52
  • $\begingroup$ Thank you, this was a very heavy but insightful paper. The result is really interesting. $\endgroup$ Sep 20, 2020 at 13:26
  • 8
    $\begingroup$ Astonishing result $\endgroup$ Sep 20, 2020 at 16:46
  • 2
    $\begingroup$ The statistics for small sizes (as far as can be computed) don't look like the final shape. For example, the most popular number of levels for 16 points is 5. This suggests that the convergence to the final shape is quite slow. $\endgroup$ Sep 21, 2020 at 1:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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