The growth constant for the stack-sorting map

About 6 years old · traced to

Let SnS_n be the symmetric group, let s:Sn→Sns:S_n\to S_n be the stack-sorting map, and let deg⁡(s:Sn→Sn)\deg(s:S_n\to S_n) denote its maximum fiber size. The paper considers the exponential growth rate

lim⁡n→∞deg⁡(s:Sn→Sn)1/n.\lim\limits_{n\to\infty}\deg(s:S_n\to S_n)^{1/n}.

Stack-sorting growth conjecture. The value of this limit lies in the interval (1.68,1.73)(1.68,1.73).

The interval is suggested by computations on random permutations for n=100n=100 and n=300n=300. The problem of obtaining improved asymptotic estimates, or exact formulas, remains open.

References

Primary source

Colin Defant and James Propp, “Quantifying Noninvertibility in Discrete Dynamical Systems”, arXiv:2002.07144 (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.