Conjectured limiting average depth for pop-stack-sorting

Let Pop\mathsf{Pop} be the pop-stack-sorting map, which reverses every maximal decreasing run of a permutation, and let DnPop\mathcal D_n^{\mathsf{Pop}} be the average number of iterations of Pop\mathsf{Pop} needed to sort a permutation in SnS_n into the identity permutation. Pop-stack-sorting average-depth conjecture.

limnDnPopn=1.\lim_{n\to\infty}\frac{\mathcal D_n^{\mathsf{Pop}}}{n}=1.

The source states that little is known about the average number of pop-stack-sorting iterations and offers this limit as a conjecture for further study.

Sources & referencesView supporting material

Primary source

Colin Defant, “Fertility Monotonicity and Average Complexity of the Stack-Sorting Map”, arXiv:2003.05935 (2020).

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.