23
$\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$
33
$\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.)

| cite | improve this answer | |
$\endgroup$
  • $\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$ – AspiringMat Sep 20 at 5:52
  • $\begingroup$ Thank you, this was a very heavy but insightful paper. The result is really interesting. $\endgroup$ – AspiringMat Sep 20 at 13:26
  • 8
    $\begingroup$ Astonishing result $\endgroup$ – მამუკა ჯიბლაძე Sep 20 at 16:46
  • 1
    $\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$ – Brendan McKay Sep 21 at 1:29

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.