Are most finite posets large?

Question

I'm currently experimenting with an algorithm that can be found here to asymptotically uniformly generate posets on a finite set $[n]$. This paper describes a Markov chain that can be used to generate directed acyclic graphs that represent partial orders and suggests that running this chain for $n^2$ steps generates results that are nearly uniformly distributed. I tried generating large numbers of partial orders for larger $n$ (up to $n = 40$) and noticed that all posets I generated with this algorithm contain most of the tuples they could contain (about ~740 tuples on average; partial orders on $[40]$ can contain at most 820 tuples). Assuming this algorithm is still accurate with $n^2$ steps for larger $n$, this would suggest that there are vastly more posets with a large number of tuples than there are posets with a small number of them. Since for each $n$, there is exactly one smallest but $n!$ largest posets on $[n]$, this intuitively makes sense to me, but are there any more exact results on how many "large" posets there are compared to "small" ones?

Answer 1

I understand tuples means here the pairs $(a,b)$ such that $a<b$ in the partial order. One could call them edges if one considers the DAG of the relation (note: not the Hasse diagram which only contains the covering pairs). Let's call their number $T$.

Exact results. As you probably know, Brinkmann and McKay (2002) counted unlabelled posets on at most 16 points exactly. They also break down the numbers by a few parameters: number of levels, number of minimal and maximal points, and number of nontrivial relations, which is in fact our $T$. For $n=16$ we have about $4.4831 \times 10^{15}$ unlabeled posets, and from Table 59 we find and calculate:

• largest $T$ is $120$ (only one such unlabeled poset, namely the chain; it has $16\times 15/2=120$ nontrivial relations)
• average $T$ is $54.222$ and median is $54$
• the most common $T$ is $54$, in $2.2721 \times 10^{14}$ posets ($5.1\%$ of all)

This would suggest that the average or typical $T$ is pretty large but not near the maximum. Two caveats:

1. this is for unlabeled posets; this should not matter very much, because the majority of large posets are rigid (have trivial automorphism group), for example with $n=16$ already about $89\%$ if I count correctly from B&M Tables 1 and 2
2. these are still relatively small posets, so they may not be representative of asymptotics; quoting B&M,

It was proved by Kleitman and Rothschild [9] that a large random poset typically has three levels with approximately $n/4$, $n/2$ and $n/4$ vertices, respectively. Our results do not show this behaviour, emphasizing again that the convergence of posets to their asymptotic behaviour is quite slow.

Anyway, since exact results are available up to $n=16$, it would probably be a very good thing to validate the uniform generator against them. As I understand the uniform generator is uniform on labeled posets, so for a good comparison one should adjust the results by the size of the automorphism group of each generated poset. (But as noted above, this should not make a big difference.)

Asymptotic results. Kleitman and Rothschild (1975) showed that asymptotically almost all posets are graded with the following form: $3$ levels $L_1,L_2,L_3$ (from the bottom up), of approximately $n/4$, $n/2$ and $n/4$ elements respectively; each element on $L_i$ covers approximately half of $L_{i-1}$ and is covered by approximately half of $L_{i+1}$. This means about $2(n/2)(n/4)/2 = \frac{1}{8}n^2$ covering pairs. I'm not sure how many pairs $a<b$ we have with $a \in L_1$ and $b \in L_3$, but surely at most $\approx \frac{1}{16}n^2$, so the total number of tuples should be approximately between $\frac{1}{8}n^2$ and $\frac{3}{16}n^2$. This is again large but much less than the maximum possible number $n(n-1)/2 \approx \frac{1}{2}n^2$.

• Brinkmann, Gunnar; McKay, Brendan D., Posets on up to 16 points, Order 19, No. 2, 147-179 (2002). ZBL1006.06003.

• Kleitman, D. J.; Rothschild, B. L., Asymptotic enumeration of partial orders on a finite set, Trans. Am. Math. Soc. 205, 205-220 (1975). ZBL0302.05007.