Abstract
The interval poset of a permutation catalogues the intervals that appear in its one-line notation, according to set inclusion. We study this poset, describing its structural, characterizing, and enumerative properties.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Albert, M.H., Atkinson, M.D.: Simple permutations and pattern restricted permutations. Discrete Math. 300, 1–15 (2005)
Bose, P., Buss, J., Lubiw, A.: Pattern matching for permutations. Inform. Process. Lett. 65, 277–283 (1998)
Bousquet-Mélou, M., Claesson, A., Dukes, M., Kitaev, S.: (2 + 2)-Free posets, ascent sequences and pattern avoiding permutations. J. Combin. Theory, Ser. A 117, 884–909 (2010)
Brignall, R.: A survey of simple permutations. In: Linton, S., Ruškuc, N., Vatter, V. (eds.) Permutation patterns, pp 41–65. Cambridge University Press, Cambridge (2010)
Földes, S.: On intervals in relational structures. Z. Math. Logik Grundlag. Math. 26, 97–101 (1980)
OEIS Foundation Inc.: The On-Line Encyclopedia of Integer Sequences. http://oeis.org (2020)
Quackenbush, R.W.: Planar lattices. In: Fajtlowicz, S., Kaiser, K. (eds.) Proceedings of the University of Houston lattice theory conference 1973, pp 512–518. Department of Mathematics, University of Houston, Houston (1973)
Stanley, R.P.: Enumerative combinatorics, vol. 1. Cambridge University Press, Cambridge Studies in Applied Mathematics 49, Cambridge (2011)
Stanley, R.P.: Catalan numbers. Cambridge University Press, Cambridge (2015)
Tenner, B.E.: Database of Permutation Pattern Avoidance, https://math.depaul.edu/bridget/patterns.html
Acknowledgements
I am very grateful to the thoughtful comments of anonymous referees, particularly during this challenging time.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Research partially supported by Simons Foundation Collaboration Grant for Mathematicians 277603 and by a DePaul University Faculty Summer Research Grant. Data sharing not applicable to this article as no datasets were generated or analyzed during the current study.
Rights and permissions
About this article
Cite this article
Tenner, B.E. Interval Posets of Permutations. Order 39, 523–536 (2022). https://doi.org/10.1007/s11083-021-09576-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11083-021-09576-1