On five types of crucial permutations with respect to monotone patterns Full article
| Journal |
Electronic Journal of Combinatorics
ISSN: 1077-8926 , E-ISSN: 1097-1440 |
||||
|---|---|---|---|---|---|
| Output data | Year: 2023, Volume: 30, Number: 1, Article number : P1.40, Pages count : 25 DOI: 10.37236/11500 | ||||
| Authors |
|
||||
| Affiliations |
|
Funding (1)
| 1 | Sobolev Institute of Mathematics | FWNF-2022-0017 |
Abstract:
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 intro-duced. In this paper, we introduce five natural types of crucial permutations with re-spect to monotone patterns, notably quadracrucial permutations that are linked most closely to Erdos-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 Robinson-Schensted correspondence. Moreover, we use the characterizations to prove that the number of such permutations of length n is growing when n -> infinity, and to enumerate minimal crucial permutations in all but one case. We also provide other enumerative results.
Cite:
Avgustinovich S.
, Kitaev S.
, Taranenko A.
On five types of crucial permutations with respect to monotone patterns
Electronic Journal of Combinatorics. 2023. V.30. N1. P1.40 :1-25. DOI: 10.37236/11500 WOS Scopus РИНЦ OpenAlex
On five types of crucial permutations with respect to monotone patterns
Electronic Journal of Combinatorics. 2023. V.30. N1. P1.40 :1-25. DOI: 10.37236/11500 WOS Scopus РИНЦ OpenAlex
Dates:
| Accepted: | Sep 3, 2022 |
| Published print: | Feb 24, 2023 |
| Published online: | Feb 24, 2023 |
Identifiers:
| Web of science: | WOS:000947395500001 |
| Scopus: | 2-s2.0-85148575200 |
| Elibrary: | 61115186 |
| OpenAlex: | W4323670407 |