Defant's linear-time conjecture for Pop-Stack Sorting on random permutations

Let D70EnD70E_n be a uniformly random permutation in the symmetric group D70EnD70E_n, and let D43EPopD43E\operatorname{Pop} denote one step of Pop-Stack Sorting, which reverses every maximal decreasing run of a permutation. Write D43EIdnD43E\operatorname{Id}_n for the identity permutation and let o(1)o(1) tend to zero as nn\to\infty. Defant's conjecture. Almost surely, Pop-Stack Sorting needs

(1o(1))n(1-o(1))n

steps to reach D43EIdnD43E\operatorname{Id}_n from D70EnD70E_n. This conjecture predicts a linear lower bound, asymptotically matching the trivial upper bound up to a vanishing factor; its resolution concerns the typical running time of Pop-Stack Sorting on a uniformly random permutation.

Sources & referencesView supporting material

Primary source

Lyuben Lichev, “Lower bound on the running time of Pop-Stack Sorting on a random permutation”, arXiv:2212.09316 (2022).

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.