ABSTRACT

The area of stack sorting of permutations has gone through tremendous progress since the last edition. New upper bounds were proved for the number of 3-stack sortable and 4-stack sortable permutations, and a conjecture regarding an upper bound for the number of https://www.w3.org/1998/Math/MathML"> t https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429274107/76d8f3df-fdac-4af3-ad29-e5f6ca3c54a5/content/math0_17.tif" xmlns:xlink="https://www.w3.org/1999/xlink"/> -stack sortable permutations was refuted. We discuss some of these results, then turn our attention to pop-stack sortable permutations. We present the recent proof of Michael Albert and Vincent Vatter (implicit in earlier work of Peter Ungar) of the fact that every permutation of length https://www.w3.org/1998/Math/MathML"> n https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429274107/76d8f3df-fdac-4af3-ad29-e5f6ca3c54a5/content/math0_18.tif" xmlns:xlink="https://www.w3.org/1999/xlink"/> is https://www.w3.org/1998/Math/MathML"> ( n − 1 ) https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429274107/76d8f3df-fdac-4af3-ad29-e5f6ca3c54a5/content/math0_19.tif" xmlns:xlink="https://www.w3.org/1999/xlink"/> -pop-stack sortable. The exercises and Problems Plus contain a high number of new results, mostly from the work of Colin Defant.