Geodesic
Partitioning permutations into monotone subsequences
David Wärn1
1University of Cambridge
The electronic journal of combinatorics, Tome 28 (2021) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

A permutation is $k$-coverable if it can be partitioned into $k$ monotone subsequences. Barber conjectured that, for any given permutation, if every subsequence of length ${k+2 \choose 2}$ is $k$-coverable then the permutation itself is $k$-coverable. This conjecture, if true, would be best possible. Our aim in this paper is to disprove this conjecture for all $k \geqslant 3$. In fact, we show that for any $k$ there are permutations such that every subsequence of length at most $(k/6)^{2.46}$ is $k$-coverable while the permutation itself is not.
DOI : 10.37236/10267
Classification : 05A05, 05D05

David Wärn  1

1 University of Cambridge 
@article{10_37236_10267,
     author = {David W\"arn},
     title = {Partitioning permutations into monotone subsequences},
     journal = {The electronic journal of combinatorics},
     year = {2021},
     volume = {28},
     number = {3},
     doi = {10.37236/10267},
     zbl = {1473.05015},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/10267/}
}
TY  - JOUR
AU  - David Wärn
TI  - Partitioning permutations into monotone subsequences
JO  - The electronic journal of combinatorics
PY  - 2021
VL  - 28
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/10267/
DO  - 10.37236/10267
ID  - 10_37236_10267
ER  - 
%0 Journal Article
%A David Wärn
%T Partitioning permutations into monotone subsequences
%J The electronic journal of combinatorics
%D 2021
%V 28
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/10267/
%R 10.37236/10267
%F 10_37236_10267
David Wärn. Partitioning permutations into monotone subsequences. The electronic journal of combinatorics, Tome 28 (2021) no. 3. doi: 10.37236/10267

Cité par Sources :