Defant's linear-time conjecture for Pop-Stack Sorting on random permutations
Defant's linear-time conjecture for Pop-Stack Sorting on random permutations
Let be a uniformly random permutation in the symmetric group , and let denote one step of Pop-Stack Sorting, which reverses every maximal decreasing run of a permutation. Write for the identity permutation and let tend to zero as . Defant's conjecture. Almost surely, Pop-Stack Sorting needs
steps to reach from . 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
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.