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.
Original languageEnglish
Article numberP2.2
Number of pages27
JournalThe Electronic Journal of Combinatorics
Volume21
Issue number2
Publication statusPublished - 1 Apr 2014

    Fingerprint

Keywords

  • stack sorting
  • revstack
  • descent polynomial

Cite this