Lower bound of $e(P)$, the amount of linear extensions of a poset $P$ of cardinality $n$

181 Views Asked by At

I am trying to solve the problem, stated as follows

Let $P$ be an $n$-element poset. If $t \in P$ then $\lambda_t= \{ s \in P: s \leq t \}$

Show that $e(P) \geq \frac{n!}{\prod_{t \in P} \lambda_t}$

Where $e(P)$ is the number of linear extensions of P. I think I may be close to a proof, but I am unable to prove the last part and I am starting to doubt its validity.

A theorem in my textbook states that $e(P)$ is equal to the number of chains $0 = I_0 < ... < I_n = 1$ of length $n$ in $J(P)$.

$J(P)$ is graded of rank $n$. If $I_2$ covers $I_1$ in $J(P)$ then $I_2 = I_1 \cup t$ for some minimal element $t \in P - I_1$.

My idea was to create a procedure for making orderings of the elements in $P$ from the chains $0 = I_0 < ... < I_n = 1$ by:

Suppose your ordering so far is $(s_1, s_2,..., s_{k-1})$. Since $I_k = I_{k-1}\cup t$, place $t$ into the order either at the end or to the left of an $s_i$ such that $s_i \leq t$. This can be done in $\lambda_t$ ways. These orderings do not necessarily end up being unique but there are $\prod_{t \in P} \lambda_t e(P)$ of them. If it can be proven that we can create any arbitrary order $\{ s_1, ... ,s_n\}$ this way, the sought inequality follows (as there are $n!$ arbitrary orderings and possibly more procedure orderings). This is where I am stuck, however. I am not able to find a proof.