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

About 4 years old · traced to

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

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

steps to reach D43EId⁡nD43E\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.

References

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.