SpringerLink
Log in

Linear Extension Numbers of n-Element Posets

  • Published:
Order Aims and scope Submit manuscript

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 \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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Aiylam, D.: A generalized Stern-Brocot tree. Integers 17, A19 (2017)

    MathSciNet  MATH  Google Scholar 

  2. Atkinson, M.D., Chang, H.W.: Extensions of Partial Orders of Bounded Width. Carleton University, School of Computer Science (1985)

  3. Bates, B., Bunder, M., Tognetti, K.: Locating terms in the stern–brocot tree. Eur. J. Comb. 31(3), 1020–1033 (2010)

    Article  MathSciNet  Google Scholar 

  4. Bates, B., Bunder, M., Tognetti, K.: Linking the Calkin-Wilf and Stern-Brocot trees. European J. Combin. 31(7), 1637–1661 (2010)

    Article  MathSciNet  Google Scholar 

  5. Benjamin, A.T., Quinn, J.J.: Proofs that Really Count: The Art of Combinatorial Proof. Number 27 in Dolciani Mathematical Expositions. MAA (2003)

  6. Björner, A., Wachs, M.L.: Permutation statistics and linear extensions of posets. J. Comb. Theory Series A 58(1), 85–114 (1991)

    Article  MathSciNet  Google Scholar 

  7. Brightwell, G.: Random k-dimensional orders: width and number of linear extensions. Order 9(4), 333–342 (1992)

    Article  MathSciNet  Google Scholar 

  8. Brightwell, G., Winkler, P.: Counting linear extensions. Order 8(3), 225–242 (1991)

    Article  MathSciNet  Google Scholar 

  9. Brightwell, G.R., Tetali, P.: The number of linear extensions of the Boolean lattice. Order 20(4), 333–345 (2003)

    Article  MathSciNet  Google Scholar 

  10. Calkin, N., Wilf, H.S.: Recounting the rationals. Am. Math. Mon. 107(4), 360–363 (2000)

    Article  MathSciNet  Google Scholar 

  11. Dittmer, S., Pak, I.: Counting linear extensions of restricted posets. ar**v:1802.06312v1 (2018)

  12. Edelman, P., Hibi, T., Stanley, R.P.: A recurrence for linear extensions. Order 6(1), 15–18 (1989)

    Article  MathSciNet  Google Scholar 

  13. Felsner, S., Manneville, T.: Linear extensions of N-free orders. Order 32(2), 147–155 (2015)

    Article  MathSciNet  Google Scholar 

  14. Hardy, G.H., Wright, E.M.: An introduction to the theory of numbers. Oxford University Press (1979)

  15. Lehmer, D.H.: On Stern’s Diatomic Series. Am. Math. Mon. 36(2), 59–67 (1929)

    Article  MathSciNet  Google Scholar 

  16. McDiarmid, C., Penman, D., Iliopoulos, V.: Linear extensions and comparable pairs in partial orders. Order 35(3), 403–420 (2018)

    Article  MathSciNet  Google Scholar 

  17. Stachowiak, G.: A relation between the comparability graph and the number of linear extensions. Order 6(3), 241–244 (1989)

    Article  MathSciNet  Google Scholar 

  18. Stanley, R.P.: Two poset polytopes. Discret Comput Geom 1(1), 9–23 (1986)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgments

We thank the anonymous referees for their careful reading and helpful comments.

Author information

Authors and Affiliations

  1. Grace Hopper College, Yale University, New Haven, CT, 06510, USA

    Noah Kravitz

  2. Massachusetts Institute of Technology, Cambridge, MA, 02139, USA

    Ashwin Sah

Authors
  1. Noah Kravitz
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ashwin Sah
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Noah Kravitz.

Additional information

Publisher’s Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Kravitz, N., Sah, A. Linear Extension Numbers of n-Element Posets. Order 38, 49–66 (2021). https://doi.org/10.1007/s11083-020-09527-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11083-020-09527-2

Keywords

Search

Navigation