Revstack Sort, Zigzag Patterns, Descent Polynomials of $t$-Revstack Sortable Permutations, and Steingrímsson's Sorting Conjecture

Abstract

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.