Steingrímsson's sorting conjecture for revstack and stack sort
Steingrímsson's sorting conjecture for revstack and stack sort
Let
be the symmetric group on $n$ letters, letdenote the stack-sorting operator, and let
denote the revstack-sorting operator. For a nonnegative integer $t$, writeand
undefined\left|{\pi\in\mathfrak{S}_n:\mathcal{S}^t(\pi)=\mathrm{id}}\right|\leq\left|{\pi\in\mathfrak{S}_n:\mathcal{T}^t(\pi)=\mathrm{id}}\right|,
is the identity permutation. Furthermore, this inequality is strict for all pairs satisfying .
The conjecture compares the sorting power of ordinary stack sort with its reverse-input variant; it asserts that revstack sort sorts at least as many permutations after every number of passes, with strict improvement in the indicated range. Its resolution is not specified in the source.
Sources & referencesView supporting material
Primary source
Mark Dukes, “Revstack sort, zigzag patterns, descent polynomials of t-revstack sortable permutations, and Steingrímsson's sorting conjecture”, arXiv:1404.1457 (2014).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.