论文标题
关于单调模式的五种关键排列
On five types of crucial permutations with respect to monotone patterns
论文作者
论文摘要
关键排列是避免给定的禁令集的置换，但是以允许的方式进行了任何扩展，导致引入禁令。 在本文中，我们介绍了有关单调模式的五种自然类型的关键排列，特别是四肢置换置换，这些排列最紧密地链接到ERDőSSZEKERES的极端排列。我们定义右至关重要和双色排列的方式与其他禁令中文献中所研究的相应排列的定义一致。对于这五种类型中的每一种，我们通过RSK对应关系提供了其Young Tableaux的表征。此外，我们使用表征来证明，当$ n \ to \ infty $ $ n $的长度$ n $的排列数量正在增长，并列举除一种情况以外的所有情况下最小的关键排列。我们还提供其他列举结果。
A crucial permutation is a permutation that avoids a given set of prohibitions, but any of its extensions, in an allowable way, results in a prohibition being introduced. In this paper, we introduce five natural types of crucial permutations with respect to monotone patterns, notably quadrocrucial permutations that are linked most closely to Erdős-Szekeres extremal permutations. The way we define right-crucial and bicrucial permutations is consistent with the definition of respective permutations studied in the literature in the contexts of other prohibitions. For each of the five types, we provide its characterization in terms of Young tableaux via the RSK correspondence. Moreover, we use the characterizations to prove that the number of such permutations of length $n$ is growing when $n\to\infty$, and to enumerate minimal crucial permutations in all but one case. We also provide other enumerative results.
