Asymptotic average-sorting-time conjecture for type-B stack-sorting

About 5 years old · traced to

Let Dn\mathcal D_n be the average number of iterations of the ordinary stack-sorting map s⁡\operatorname{\mathtt{s}} needed to send an element of SnS_n to the identity permutation, and let DnB\mathcal D_n^B be the average number of iterations of the type-BB stack-sorting map s⁡B\operatorname{\mathtt{s}}_B needed to send an element of BnB_n to the identity element. Asymptotic average-sorting-time conjecture. One has

lim⁡n→∞(Dnn−DnBn)=0.\lim_{n\to\infty}\left(\frac{\mathcal D_n}{n}-\frac{\mathcal D_n^B}{n}\right)=0.

The conjecture asserts that the normalized average numbers of iterations agree asymptotically between types AA and BB. The source gives no resolution, so the conjecture remains open.

References

Primary source

Colin Defant, “Stack-Sorting for Coxeter Groups”, arXiv:2104.03215 (2022).

Additional references

2 papers in this index state this conjecture (2021). The statement above is taken from the most recent of them; the others are arXiv:2104.02675.

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.