Lower bound for the number of partial orders

Question

I was wondering if there is a lower bound or a recursive relation for $P_n$ , the number of partial orders or posets on a set of $n$ elements.

I have noticed that $P_n>P_{n-1}, \forall n\geq 2$. It seems that this bound is somewhat insignificant and trivial, though.

Answer 1

There are a number of results from the 1960s and 1970s about such asymptotics or bounds on the numbers of posets / particular kinds of posets / topologies on $n$ points.

For example, Kleitman and Rothschild (1970), building on an earlier result by Chatterji (1966), show that $$ P_n \ge 2^{n^2/4}. $$

This is for "labeled" posets (the $n$ points are labeled, so for example with $n=2$ the posets $1<2$ and $2<1$ are distinct), but since the numbers grow much faster than $n!$, for large $n$ it does not matter much whether you allow permutations of the $n$ points or not (i.e. consider labeled or unlabeled posets).

The exact numbers of (labeled) posets are known up to $n=18$ due to Brinkmann and McKay (2002), and are listed in OEIS A001035. No simple recursive relation is known that would allow easy calculation of $P_n$ for large $n$; the exact results are based on a lot of computation by cases (see the Brinkmann & McKay paper for details).

• Brinkmann, Gunnar; McKay, Brendan D., Posets on up to 16 points, Order 19, No. 2, 147-179 (2002). ZBL1006.06003.
• Kleitman, D.; Rothschild, B., The number of finite topologies Proceedings of the American Mathematical Society 25:276-282 (1970)