The cost classification conjecture for skew-layered permutations

From papers

Let π\pi be a skew-layered permutation of size nn, and let cost(π)\mathsf{cost}(\pi) denote its pop-stack sorting cost. Exclude id\mathsf{id} and id-\mathsf{id}. Skew-layered cost classification conjecture. If nn is even, then

cost(π)=n1.\mathsf{cost}(\pi)=n-1.

If nn is odd and the (n+1)/2(n+1)/2-th position of π\pi is the central point of a run or of a fall of size at least 33, then cost(π)=n2\mathsf{cost}(\pi)=n-2; otherwise, cost(π)=n1\mathsf{cost}(\pi)=n-1. This conjecture refines the preceding necessary condition for permutations of maximum cost and is based on the authors' computer experiments; a general characterization of all maximum-cost permutations remains open.

Progress summary

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

Sources & referencesView supporting material

Primary source

Andrei Asinowski, Cyril Banderier and Benjamin Hackl, “Flip-sort and combinatorial aspects of pop-stack sorting”, arXiv:2003.04912 (2021).

Solutions 0

No solutions have been posted yet.