Picture of person typing on laptop with programming code visible on the laptop screen

World class computing and information science research at Strathclyde...

The Strathprints institutional repository is a digital archive of University of Strathclyde's Open Access research outputs. Strathprints provides access to thousands of Open Access research papers by University of Strathclyde researchers, including by researchers from the Department of Computer & Information Sciences involved in mathematically structured programming, similarity and metric search, computer security, software systems, combinatronics and digital health.

The Department also includes the iSchool Research Group, which performs leading research into socio-technical phenomena and topics such as information retrieval and information seeking behaviour.

Explore

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

Dukes, Mark (2014) Revstack sort, zigzag patterns, descent polynomials of t-revstack sortable permutations, and Steingrímsson's sorting conjecture. The Electronic Journal of Combinatorics, 21 (2). ISSN 1077-8926

Full text not available in this repository. Request a copy from the Strathclyde author

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.