Linear extension numbers of \(n\)-element posets (Q2663168)

Let \(P\) be a poset (partially ordered set) with \(n\) vertices. The number of linear extensions of \(P\) -- i.e. of total orders of the vertex set of \(P\) which agree with the partial order where it is defined -- is an important invariant of \(P\), which is in some loose sense a measure of the complexity of \(P\). Consequently it is of interest to be aware what the possible values of the number of linear extensions are. (It is clearly between \(n!\), attained when the original poset has no comparisons at all, and 1, attained when the original poset is already a total order). Let \(\mathbf{LE}(n)\) denote the set of possible numbers of linear extensions of an \(n\)-vertex poset. The main result of the paper under review is that there is a positive constant \(c\) such that every integer in \([1, \exp(cn/\log(n)]\) is the number of linear extensions of some \(n\)-vertex poset. The clever proof depends on constructing recursively a sequence of width 2 posets whose number of linear extensions are related to properties of the so-called Stern-Brocot tree, itself closely linked to the Farey tree). This means that the question reduces to proving the following number-theoretic result, likely to be of independent interest: There is a constant \(c>9\) such that, given \(n\geq 2\), there is some \(1\leq d\leq n-1\) such that when the Euclidean algorithm is run on \((n,d)\) the sum of the quotients is at most \(c\frac{n}{\phi(n)}\log(n)\log\log(n)\) where \(\phi\) is Euler's totient function as usual. The authors conjecture that the factor \(\frac{n}{\phi(n)}\log\log(n)\) can be removed. This result shows that small values in the range from 1 to \(n!\) will have \(n\)-vertex posets with that number of linear extensions: however as we move up the range many potential values cannot happen. The authors show that for \(n\geq 8\) we have \(\vert \mathbf{LE}(n)\cap [(n-1)!, n!]\vert <(n-3)!\). Various open problems on extending these results are also mentioned.