Steingrímsson's sorting conjecture for revstack and stack sort

Let

be the symmetric group on $n$ letters, let

denote the stack-sorting operator, and let

denote the revstack-sorting operator. For a nonnegative integer $t$, write

and

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|,

wherewhere

is the identity permutation. Furthermore, this inequality is strict for all pairs (n,t)(n,t) satisfying 2<t<n12<t<n-1.

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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.