# Revstack sort, zigzag patterns, descent polynomials of t-revstack sortable permutations, and Steingrímsson's sorting conjecture

Mark Dukes

Research output: Contribution to journalArticle

### Abstract

In this paper we examine the sorting operator T(LnR)=T(R)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 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.
Language English P2.2 27 The Electronic Journal of Combinatorics 21 2 Published - 1 Apr 2014

Zigzag
Descent
Sorting
Sort
Permutation
Polynomials
Polynomial
Information use
Unimodality
Operator
Theorem
Symmetry

### Keywords

• stack sorting
• revstack
• descent polynomial

### Cite this

@article{32ec00e037494296929a84c9e174df7b,
title = "Revstack sort, zigzag patterns, descent polynomials of t-revstack sortable permutations, and Steingr{\'i}msson's sorting conjecture",
abstract = "In this paper we examine the sorting operator T(LnR)=T(R)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 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{\'i}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.",
keywords = "stack sorting , revstack, descent polynomial",
author = "Mark Dukes",
year = "2014",
month = "4",
day = "1",
language = "English",
volume = "21",
journal = "The Electronic Journal of Combinatorics",
issn = "1077-8926",
number = "2",

}

In: The Electronic Journal of Combinatorics, Vol. 21, No. 2, P2.2, 01.04.2014.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Revstack sort, zigzag patterns, descent polynomials of t-revstack sortable permutations, and Steingrímsson's sorting conjecture

AU - Dukes, Mark

PY - 2014/4/1

Y1 - 2014/4/1

N2 - In this paper we examine the sorting operator T(LnR)=T(R)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 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.

AB - In this paper we examine the sorting operator T(LnR)=T(R)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 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.

KW - stack sorting

KW - revstack

KW - descent polynomial

UR - http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i2p2

M3 - Article

VL - 21

JO - The Electronic Journal of Combinatorics

T2 - The Electronic Journal of Combinatorics

JF - The Electronic Journal of Combinatorics

SN - 1077-8926

IS - 2

M1 - P2.2

ER -