On the Geometry of Stack-Sorting Simplices

Cameron Ake, Spencer F. Lewis, Amanda Louie, Andrés R. Vindas-Meléndez · 2025

Read On the Geometry of Stack-Sorting Simplices by Cameron Ake, Spencer F. Lewis, Amanda Louie, Andrés R. Vindas-Meléndez (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-00219.txt.

Introduction

Cameron Ake, Spencer Lewis, Amanda Louie, and Andrés Vindas-Meléndez study the shapes that arise from stack-sorting, a classic puzzle about reordering lists with a single stack. Each sorting process traces out a geometric object called a polytope, and the team settles basic questions about those shapes.

They prove every stack-sorting polytope is in fact a simplex, the simplest possible shape in its dimension, with no wasted corners. For polytopes built from one family of permutations, the volume comes out to exactly one in the natural units. They also bound how many lattice points such a shape can hold, and show that a second family has no lattice points in its interior at all. The results tidy up a corner where combinatorics meets geometry.

Catalog record

CREATORCameron Ake, Spencer F. Lewis, Amanda Louie, Andrés R. Vindas-Meléndez
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE40 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-00219

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On the Geometry of Stack-Sorting Simplices Cameron Ake, Spencer F. Lewis, Amanda Louie, Andrés R. Vindas-Meléndez Abstract . We show that all stack-sorting polytopes are simplices. Furthermore, we show that the stack-sorting polytopes generated from L ​ n ​ 1 Ln1 permutations have relative volume 1. We establish an upper bound for the number of lattice points in a stack-sorting polytope. In particular, stack-sorting polytopes generated from 2 ​ L ​ n ​ 1 2Ln1 permutations have no interior points. 1. Introduction A stack is a data structure that only allows the most recently input element to be output. Donald Knuth first popularized the idea of sorting a permutation by storing its values on a stack [ 10 ] . Twenty-two years later, Julian West introduced a deterministic approach: the stack-sorting algorithm [ 14 ] . One pass of the stack-sorting algorithm has time complexity O(n), but the algorithm is not guaranteed to fully sort a permutation in ascending order. So, after we pass a permutation through the algorithm, we pass the sorted result through the algorithm again. If we repeat this, the permutation will be sorted in ascending order after at most n-1 iterations of the algorithm. We will discuss the stack-sorting algorithm in depth in Section 2 . In [ 11 ] , Lee, Mitchell, and Vindas-Meléndez analyzed the geometry of stack-sorting polytopes . To generate a stack-sorting polytope from a permutation of numbers 1 through n , we repeatedly pass the permutation through the stack-sorting algorithm. Then, we consider these input and output permutations as a set of points. The convex hull of these points will be a stack-sorting polytope, a subset of the permutahedron in \mathbb{R}^{n} . In this paper, we continue the study of stack-sorting polytopes. We provide some computational results on the stack-sorting algorithm. Then, we focus on the geometry and volumes of stack-sorting polytopes. We also discuss the interior lattice points of stack-sorting polytopes. We conclude by utilizing triangulations to study the lattice points of these polytopes. In Section 2 , we give an overview of the stack-sorting algorithm, convex lattice polytopes, and stack-sorting polytopes. In Section 3 , we prove that all stack-sorting polytopes are simplices, which we state in Theorem 3.3 . Theorem 3.3 . Let \boldsymbol{\pi}\in\mathfrak{S}_{n} be exactly k -stack-sortable. Then, \triangle:=conv(\mathcal{S}^{\boldsymbol{\pi}}) is a k -simplex. In Section 4 , we give the volume of all Ln1 simplices. Theorem 4.6 . Let \boldsymbol{\pi} be an Ln1 permutation. The relative volume of \triangle=\conv(\mathcal{S}^{\boldsymbol{\pi}}) is 1 . In Section 5 , we study the lattice points of stack-sorting polytopes. We give an upper bound for the number of lattice points in a stack-sorting polytope generated by an Ln1 permutation. We briefly discuss triangulations of stack-sorting polytopes. We also show that stack-sorting polytopes generated by 2Ln1 permutations are hollow in Proposition 5.2 . Proposition 5.2 . Let \boldsymbol{\pi}\in\mathfrak{S}_{n} be of the form 2Ln1 , where L is any permutation of \{3,4,\dots,(n-1)\} . The simplex \triangle:=conv(\mathcal{S}^{\boldsymbol{\pi}}) is hollow. In particular, any non-vertex lattice point of \triangle lies on the facet formed by the convex hull of \mathcal{S}^{\boldsymbol{\pi}}\setminus\{\mathbf{e}\} . In Section 6 , we conclude by giving questions, conjectures, and areas of future research. 2. Background and Preliminaries In this section, we provide some necessary background for studying stack-sorting polytopes. We begin with the stack-sorting algorithm. This algorithm has been widely studied in combinatorics, computer science, probability, and polyehdral geometry; for example, see [ 3 , 4 , 6 , 5 , 9 , 7 , 8 , 11 , 12 ] . 2.1. Stack-sorting algorithm The stack-sorting algorithm takes a permutation \boldsymbol{\pi}\in\mathfrak{S}_{n} of the numbers 1 through n as input. The purpose of the algorithm is to sort these numbers in increasing order. We denote the identity permutation by \mathbf{e}=123\cdots n . Before we discuss the stack-sorting algorithm, we must define a stack. A stack is commonly referred to as a “last in, first out” data structure. A stack outputs its values in the opposite order to which they are input. We refer to inputting a value into a stack as a push , and we refer to outputting a value from the stack as a pop . We call the most-recently-input element of the stack the top element, t . Now, we define the stack-sorting algorithm. Definition 2.1 . The stack-sorting algorithm on a permutation \boldsymbol{\pi} is defined in West’s thesis [ 14 ] . We start with an empty stack and a permutation \boldsymbol{\pi}=\pi_{1}\pi_{2}\cdots\pi_{n} , and we iterate through the elements of \boldsymbol{\pi} , from left to right. For each element \pi_{k} : • We compare \pi_{k} to the value at the top of the stack, t . • While \pi_{k} is greater than t , we pop t from the stack into our output. We repeat this step until \pi_{k} is less than t , or until the stack is empty. • Once \pi_{k} is less than t , or once the stack is empty, we push \pi_{k} onto the stack and repeat the process with \pi_{k+1} . Finally, once we have iterated through all elements of \boldsymbol{\pi} , we pop the remaining values on the stack. We call the resulting permutation s(\boldsymbol{\pi}) . It is important to note that all elements of \boldsymbol{\pi} will be pushed onto the stack and popped into the output. Also note that the stack is always strictly decreasing. We illustrate this process with an example. Example 2.2 . We pass \boldsymbol{\pi}=231 through the stack-sorting algorithm. We begin by pushing the first element of \boldsymbol{\pi} , 2 , onto the stack. (i) 2 3 1 2 3 1 Now, we consider the next element of \boldsymbol{\pi} , 3 . We see 3 is greater than the top element of the stack, 2 . So, we pop 2 . (ii) 2 3 1 2 3 1 The stack is empty, so we push 3 . (iii) 2 3 1 2 3 1 Now, we consider the next (and final) element of \boldsymbol{\pi} , 1 . We see 1 is less than the top element of the stack, 3 . So, we push 1 . (iv) 2 3 1 2 3 1 Now that we have iterated through the permutation, we pop the values that are in the stack. (v) 2 3 1 2 3 1 (vi) 2 1 3 2 1 3 This gives us s(\boldsymbol{\pi})=213 . As we see in Example 2.2 , the stack-sorting algorithm does not always fully sort a permutation in ascending order. We can pass s(\boldsymbol{\pi}) through the algorithm again, yielding s(s(\boldsymbol{\pi})) , or s^{2}(\boldsymbol{\pi}) . We continue applying the algorithm until our permutation is fully sorted. A permutation of length n will be sorted in ascending order after at most n-1 iterations of the stack-sorting algorithm. Definition 2.3 . Given a permutation \boldsymbol{\pi}\in\mathfrak{S}_{n} , if s^{k}(\boldsymbol{\pi})=\mathbf{e}=123\cdots n , then \boldsymbol{\pi} is k-stack-sortable . If this is the smallest value k for which \boldsymbol{\pi} is k -stack-sortable, then \boldsymbol{\pi} is exactly k -stack-sortable. Let \mathcal{S}^{\boldsymbol{\pi}} be the set, including \boldsymbol{\pi} , of permutations resulting from subsequent passes of \boldsymbol{\pi} through the stack-sorting algorithm. That is, \mathcal{S}^{\boldsymbol{\pi}}=\{\boldsymbol{\pi},s(\boldsymbol{\pi}),s^{2}(\boldsymbol{\pi}),\dots,\mathbf{e}\} . We illustrate \mathcal{S}^{\boldsymbol{\pi}} with an example. Example 2.4 . Let \boldsymbol{\pi}=3241 . Then, s(\boldsymbol{\pi})=2314 ,

Read the complete text