Is there a better lower bound on $|P_n|$, the number of posets on a set

Question

Regarding the set of partial orders $P_n$ on an $n$-set, it is well-known that $$|P_n|\geq {2^\frac{n^2}{4}}$$. This lower bound was given long back and I am not fully aware what improvements, if any, was made to this lower bound.

Is there a known improvement of this lower bound? I am asking this because it seems not a very good lower bound for $|P_n|$.

Answer 1

Yes, Kleitman and Rothschild (1975) have a better lower bound, and they even show that it is asymptotically very tight.

Let $P_n$ be the number of posets on $n$ labeled elements; and let $$ Y_n = \sum_{i=1}^n \binom{n}{i} \sum_{j=1}^{n-i} \binom{n-i}{j} (2^i-1)^j (2^j-1)^{n-i-j}. $$ K&R prove that $$ Y_n < P_n \le Y_n (1+O(1/n)). $$ They also prove a simpler asymptotic expression: $$ \log_2 P_n = A_n + O(\log_2 n). $$ where $$ A_n = n^2/4 + 3n/2. $$ This is not that much different from the "trivial" lower bound $T_n = n^2/4$.

Let us compare to the known exact values (A001035).

$$ \begin{array}{rrrrr} n & T_n & A_n & \log_2(Y_n) & \log_2(P_n) \\ \hline 1 & 0.2500 & 1.7500 & -\infty & 0.0000 \\ 2 & 1.0000 & 4.0000 & 1.0000 & 1.5850 \\ 3 & 2.2500 & 6.7500 & 4.1699 & 4.2479 \\ 4 & 4.0000 & 10.0000 & 7.4094 & 7.7748 \\ 5 & 6.2500 & 13.7500 & 11.1737 & 12.0468 \\ 6 & 9.0000 & 18.0000 & 15.4635 & 16.9884 \\ 7 & 12.2500 & 22.7500 & 20.2760 & 22.5474 \\ 8 & 16.0000 & 28.0000 & 25.5962 & 28.6855 \\ 9 & 20.2500 & 33.7500 & 31.4190 & 35.3734 \\ 10 & 25.0000 & 40.0000 & 37.7391 & 42.5880 \\ 11 & 30.2500 & 46.7500 & 44.5551 & 50.3105 \\ 12 & 36.0000 & 54.0000 & 51.8656 & 58.5254 \\ 13 & 42.2500 & 61.7500 & 59.6705 & 67.2197 \\ 14 & 49.0000 & 70.0000 & 67.9698 & 76.3823 \\ 15 & 56.2500 & 78.7500 & 76.7638 & 86.0036 \\ 16 & 64.0000 & 88.0000 & 86.0528 & 96.0754 \\ 17 & 72.2500 & 97.7500 & 95.8374 & 106.5904 \\ 18 & 81.0000 & 108.0000 & 106.1177 & 117.5421 \\ \end{array} $$

So $Y_n$ are clearly better lower bounds than $2^{T_n}$. Note that $A_n$ are only asymptotically correct; for small $n$ they are not in fact lower bounds.

Looking at $Y_n$ and $P_n$ for small $n$, although the differences $\log_2(P_n)-\log_2(Y_n)$ are increasing, the increase is slowing down so it is still plausible that it would eventually reverse and the differences would tend to zero (as claimed).

• 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.