Geodesic
Revstack sort, zigzag patterns, descent polynomials of \(t\)-revstack sortable permutations, and Steingrímsson's sorting conjecture
Mark Dukes1
1University of Strathclyde
The electronic journal of combinatorics, Tome 21 (2014) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

In this paper we examine the sorting operator $\mathcal{T}(LnR)=\mathcal{T}(R)\mathcal{T}(L)n$. Applying this operator to a permutation is equivalent to passing the permutation reversed through a stack. We prove theorems that characterise $t$-revstack sortability in terms of patterns in a permutation that we call zigzag patterns. Using these theorems we characterise those permutations of length $n$ which are sorted by $t$ applications of $\mathcal{T}$ for $t=0,1,2,n-3,n-2,n-1$. We derive expressions for the descent polynomials of these six classes of permutations and use this information to prove Steingrímsson's sorting conjecture for those six values of $t$. Symmetry and unimodality of the descent polynomials for general $t$-revstack sortable permutations is also proven and three conjectures are given.
DOI : 10.37236/3583
Classification : 05A05, 68P10
Mots-clés : stack sort, descent polynomial, revstack

Mark Dukes  1

1 University of Strathclyde 
@article{10_37236_3583,
     author = {Mark Dukes},
     title = {Revstack sort, zigzag patterns, descent polynomials of \(t\)-revstack sortable permutations, and {Steingr{\'\i}msson's} sorting conjecture},
     journal = {The electronic journal of combinatorics},
     year = {2014},
     volume = {21},
     number = {2},
     doi = {10.37236/3583},
     zbl = {1300.05007},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/3583/}
}
TY  - JOUR
AU  - Mark Dukes
TI  - Revstack sort, zigzag patterns, descent polynomials of \(t\)-revstack sortable permutations, and Steingrímsson's sorting conjecture
JO  - The electronic journal of combinatorics
PY  - 2014
VL  - 21
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/3583/
DO  - 10.37236/3583
ID  - 10_37236_3583
ER  - 
%0 Journal Article
%A Mark Dukes
%T Revstack sort, zigzag patterns, descent polynomials of \(t\)-revstack sortable permutations, and Steingrímsson's sorting conjecture
%J The electronic journal of combinatorics
%D 2014
%V 21
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/3583/
%R 10.37236/3583
%F 10_37236_3583
Mark Dukes. Revstack sort, zigzag patterns, descent polynomials of \(t\)-revstack sortable permutations, and Steingrímsson's sorting conjecture. The electronic journal of combinatorics, Tome 21 (2014) no. 2. doi: 10.37236/3583

Cité par Sources :