Linear Extension Numbers of n-Element Posets
Abstract We address the following natural but hitherto unstudied question: what are the possible linear extension numbers of an n-element poset? Let LE(n) denote the set of all positive integers that arise as the number of linear extensions of some n-element poset. We show that LE(n)...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Netherlands
2021
|
| Online Access: | https://hdl.handle.net/1721.1/132100 |
| Summary: | Abstract
We address the following natural but hitherto unstudied question: what are the possible linear extension numbers of an n-element poset? Let LE(n) denote the set of all positive integers that arise as the number of linear extensions of some n-element poset. We show that LE(n) skews towards the “small” end of the interval [1, n!]. More specifically, LE(n) contains all of the positive integers up to
exp
c
n
log
n
$\exp \left (c\frac {n}{\log n}\right )$
for some absolute constant c, and |LE(n) ∩ ((n − 1)!, n!]| < (n − 3)!. The proof of the former statement involves some intermediate number-theoretic results about the Stern-Brocot tree that are of independent interest. |
|---|