Geodesic
On five types of crucial permutations with respect to monotone patterns
Sergey Avgustinovich ; Sergey Kitaev1 ; Anna Taranenko
1University of Strathclyde
The electronic journal of combinatorics, Tome 30 (2023) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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 quadracrucial 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 Robinson-Schensted 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.
DOI : 10.37236/11500
Classification : 05A05, 05A15
Mots-clés : crucial permutations, Erdős-Szekeres permutations, Robinson-Schensted correspondence

Sergey Avgustinovich    ; Sergey Kitaev  1   ; Anna Taranenko 

1 University of Strathclyde 
@article{10_37236_11500,
     author = {Sergey Avgustinovich and Sergey Kitaev and Anna Taranenko},
     title = {On five types of crucial permutations with respect to monotone patterns},
     journal = {The electronic journal of combinatorics},
     year = {2023},
     volume = {30},
     number = {1},
     doi = {10.37236/11500},
     zbl = {1514.05002},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/11500/}
}
TY  - JOUR
AU  - Sergey Avgustinovich
AU  - Sergey Kitaev
AU  - Anna Taranenko
TI  - On five types of crucial permutations with respect to monotone patterns
JO  - The electronic journal of combinatorics
PY  - 2023
VL  - 30
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/11500/
DO  - 10.37236/11500
ID  - 10_37236_11500
ER  - 
%0 Journal Article
%A Sergey Avgustinovich
%A Sergey Kitaev
%A Anna Taranenko
%T On five types of crucial permutations with respect to monotone patterns
%J The electronic journal of combinatorics
%D 2023
%V 30
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/11500/
%R 10.37236/11500
%F 10_37236_11500
Sergey Avgustinovich; Sergey Kitaev; Anna Taranenko. On five types of crucial permutations with respect to monotone patterns. The electronic journal of combinatorics, Tome 30 (2023) no. 1. doi: 10.37236/11500

Cité par Sources :