Linear extensions and comparable pairs in partial orders
For a poset $Q$, let $Q_{\perp}$ be the comparability graph of $Q$ and let $e(Q)$ be the number of linear extensions of $Q$. It is known that if $Q_{\perp}\cong Q_{\perp}'$, then $e(Q)=e(Q')$. The paper focuses on the following question: given $\delta\in (0,1)$, what are the maximum and minimum values of $e(Q)$ for posets $Q$ whose comparability graph has $\delta Q_{\perp}$ can have $\binom{n}{2}$ edges, so $\delta$ \par To express the main result, the authors introduce the following notation. Given $n$ and $\delta\in (0,1)$, let \[ f^+(n,\delta) = \max_{|Q|=n}\left\{e(Q) \mid \text{comp}(Q)\geq \delta\binom{n}{2}\right\} \] and \[ f^-(n,\delta) = \min_{|Q|=n} \left\{e(Q) \mid \text{comp}(Q)\leq \delta\binom{n}{2}\right\}, \] where $\text{comp}(Q)$ denotes the number of edges in $Q_{\perp}$. \par The principal result says, roughly, that for each fixed $\delta\in(0,1)$ it is the case that $f^+(n,\delta)=n!2^{-\Theta(n)}$ and $f^-(n,\delta)=2^{\Theta(n)}$.
scientific article