The growth constant for the stack-sorting map

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

limndeg(s:SnSn)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.

Sources & referencesView supporting material

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.