Counting crucial permutations with respect to monotone patterns

DOI10.1016/J.DISC.2023.113861MaRDI QIDQ6117352zbMATH OpenOpenAlexFDO

Authors Yunseo Choi

Publication date 19 February 2024

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2208.13469

zbMATH Keywords

crucial permutationsRSK correspondenceYoung tableau

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15)

Abstract: Recently, Avgustinovich, Kitaev, and Taranenko defined five types of $(k,ell)-$crucial permutations, which are maximal permutations that do not contain an increasing subsequence of length $k$ or a decreasing subsequence of length $ell$. Further, Avgustinovich, Kitaev, and Taranenko began the enumeration of the $(k,ell)-$crucial permutations of the minimal length and the next minimal length and the $(k,3)-$crucial permutations of all lengths for each of the five types of $(k,ell)-$crucial permutations. In this paper, we complete the enumeration that Avgustinovich, Kitaev, and Taranenko began.

Recommendations

• On five types of crucial permutations with respect to monotone patterns
• Crucial and bicrucial permutations with respect to arithmetic monotone patterns
• \(S\)-crucial and bicrucial permutations with respect to squares
• Permutations avoiding sets of patterns with long monotone subsequences
• scientific article; zbMATH DE number 2192093

Cites work

• An Erdős-Hajnal analogue for permutation classes
• Crucial words and the complexity of some extremal problems for sets of prohibited words
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 3019031 (Why is no real title available?)
• Longest Increasing and Decreasing Subsequences
• On five types of crucial permutations with respect to monotone patterns
• On uniquely k-determined permutations
• Permutations, matrices, and generalized Young tableaux
• The Hook Graphs of the Symmetric Group

Cited in

(2)

• Bicrucial k-power-free permutations
• On P-crucial and S-crucial square-free permutations

This page was built for publication: Counting crucial permutations with respect to monotone patterns

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6117352)