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 |
| _version_ | 1826206379917967360 |
|---|---|
| author | Kravitz, Noah Sah, Ashwin |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Kravitz, Noah Sah, Ashwin |
| author_sort | Kravitz, Noah |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T13:28:16Z |
| format | Article |
| id | mit-1721.1/132100 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T13:28:16Z |
| publishDate | 2021 |
| publisher | Springer Netherlands |
| record_format | dspace |
| spelling | mit-1721.1/1321002023-03-15T20:19:25Z Linear Extension Numbers of n-Element Posets Kravitz, Noah Sah, Ashwin Massachusetts Institute of Technology. Department of Mathematics 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. 2021-09-20T17:41:57Z 2021-09-20T17:41:57Z 2020-05-11 2021-04-04T03:31:39Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/132100 en https://doi.org/10.1007/s11083-020-09527-2 Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. Springer Nature B.V. application/pdf Springer Netherlands Springer Netherlands |
| spellingShingle | Kravitz, Noah Sah, Ashwin Linear Extension Numbers of n-Element Posets |
| title | Linear Extension Numbers of n-Element Posets |
| title_full | Linear Extension Numbers of n-Element Posets |
| title_fullStr | Linear Extension Numbers of n-Element Posets |
| title_full_unstemmed | Linear Extension Numbers of n-Element Posets |
| title_short | Linear Extension Numbers of n-Element Posets |
| title_sort | linear extension numbers of n element posets |
| url | https://hdl.handle.net/1721.1/132100 |
| work_keys_str_mv | AT kravitznoah linearextensionnumbersofnelementposets AT sahashwin linearextensionnumbersofnelementposets |