Stack sorting with restricted stacks

Anders Claesson; Giulio Cerbai; Luca Ferrari

arxiv: 1907.08142 · v1 · pith:UWHSQTXLnew · submitted 2019-07-18 · 💻 cs.DS · cs.DM· math.CO

Stack sorting with restricted stacks

Giulio Cerbai , Anders Claesson , Luca Ferrari This is my paper

Pith reviewed 2026-05-24 19:19 UTC · model grok-4.3

classification 💻 cs.DS cs.DMmath.CO

keywords stack sortingpermutation patternspermutation classesavoiding permutationsCatalan numbersgreedy sortingtwo stacks in series

0 comments

The pith

The number of σ-machines producing sortable permutations that do not form a permutation class is given by the Catalan numbers.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper investigates a restricted form of two-stack sorting in which the first stack must avoid a fixed pattern σ when read from top to bottom. A greedy procedure is used that always selects the rightmost possible legal operation. The authors establish that the σ for which the set of sortable permutations fails to be a permutation class are counted by the Catalan numbers. They provide complete characterizations and enumerations for the sortable permutations when σ is 321 and when σ is 123.

Core claim

The σ-machine sorts permutations using two stacks in series under a greedy rightmost-legal-move rule, with the first stack required to avoid σ. The collection of σ-machines for which the sortable permutations do not constitute a permutation class has cardinality equal to the Catalan number. For the patterns 321 and 123 the sortable permutations receive explicit descriptions and generating functions or closed enumerations.

What carries the argument

The σ-machine: a pair of stacks operated greedily with the input stack constrained to be σ-avoiding.

If this is right

The sortable permutations form a permutation class for all but Catalan many choices of σ.
The cases σ=321 and σ=123 admit explicit bijections or pattern-avoidance descriptions for their sortable sets.
Enumeration sequences for the two special cases follow from the characterizations.
Non-class behavior is confined to a Catalan-sized family of patterns.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Similar restrictions might be studied for three or more stacks.
The Catalan enumeration hints at a possible recursive or tree-like structure for the exceptional σ.
These machines could be compared to other pattern-restricted sorting devices.

Load-bearing premise

The sorting always follows the rule of performing the rightmost legal operation and the avoidance condition is enforced on the stack read top to bottom.

What would settle it

A specific σ whose sortable permutations neither form a class nor fit into the Catalan count of exceptions, or a sortable permutation for σ=321 that violates the claimed characterization.

read the original abstract

The (classical) problem of characterizing and enumerating permutations that can be sorted using two stacks connected in series is still largely open. In the present paper we address a related problem, in which we impose restrictions both on the procedure and on the stacks. More precisely, we consider a greedy algorithm where we perform the rightmost legal operation (here "rightmost" refers to the usual representation of stack sorting problems). Moreover, the first stack is required to be $\sigma$-avoiding, for some permutation $\sigma$, meaning that, at each step, the elements maintained in the stack avoid the pattern $\sigma$ when read from top to bottom. Since the set of permutations which can be sorted by such a device (which we call $\sigma$-machine) is not always a class, it would be interesting to understand when it happens. We will prove that the set of $\sigma$-machines whose associated sortable permutations are not a class is counted by Catalan numbers. Moreover, we will analyze two specific $\sigma$-machines in full details (namely when $\sigma=321$ and $\sigma=123$), providing for each of them a complete characterization and enumeration of sortable permutations.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper counts the σ where sortable sets fail to be classes by the Catalan numbers and gives full characterizations for σ=321 and σ=123.

read the letter

The punchline is that this work defines σ-machines (pattern-avoiding first stack plus greedy rightmost operations) and proves the σ yielding non-class sortable sets are counted by Catalan numbers, with explicit bijections or recursions for the 321 and 123 cases. That counting result is the clearest new piece; the two detailed analyses supply concrete sortable sets and their enumerations that were not in the earlier stack-sorting literature cited in the abstract. The model itself is a reasonable restriction on the classical two-stack problem, and the choice to track when the output set stops being a class is a clean way to organize the cases. The proofs presumably rest on case-by-case pattern analysis and some recursive decomposition that produces the Catalan count, which is plausible given how often Catalan numbers appear in stack and pattern problems. The main soft spot is that everything hinges on the internal consistency of the rightmost-greedy rule and the top-to-bottom reading of the stack; if that rule creates hidden dependencies not captured by the pattern avoidance, the non-class count could shift. The two explicit cases look like they can be checked directly once the full arguments are read, so any gaps would be local rather than structural. This is aimed at people already working on restricted stack sorting and permutation classes. A reader who cares about enumeration tools for sorting devices will get usable characterizations and a new counting theorem. The paper is coherent on its own terms and supplies verifiable combinatorial statements, so it deserves a serious referee even if the proofs need tightening in places.

Referee Report

0 major / 3 minor

Summary. The paper defines σ-machines: two stacks in series where the first stack must avoid a fixed pattern σ (read top-to-bottom) and the procedure is the greedy rightmost-legal-move algorithm. It proves that the number of permutations σ for which the sortable set is not a permutation class equals the Catalan number. It then supplies explicit characterizations and enumerations of the sortable permutations for the two cases σ = 321 and σ = 123.

Significance. If the counting argument and the two case analyses hold, the work supplies a clean enumeration result that connects restricted stack sorting to the Catalan numbers and gives concrete, usable characterizations for two natural patterns. The explicit bijections or generating-function derivations (if present) would constitute a verifiable combinatorial contribution in the area of permutation pattern avoidance and sorting networks.

minor comments (3)

§2 (or wherever the formal definition of the σ-machine appears): the phrase 'rightmost legal operation' should be accompanied by an explicit pseudocode or decision tree that lists the four possible moves and the priority order, to remove any ambiguity about ties.
The enumeration statements for σ = 321 and σ = 123 would benefit from a short table comparing the first 10–12 terms against OEIS or against the claimed closed form, even if the proof is bijective.
Notation: the symbol for the sortable set (e.g., Sort(σ)) is introduced without a dedicated definition line; a single displayed equation would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our work on σ-machines and for recommending minor revision. The report provides no major comments to address.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper's central results are a counting theorem (the number of σ such that the sortable permutations do not form a class equals the Catalan number) together with explicit characterizations and enumerations for the cases σ=321 and σ=123. These are self-contained combinatorial statements resting on definitions of σ-machines, greedy rightmost-legal operations, and pattern avoidance. No parameter fitting, self-referential definitions, or load-bearing self-citations appear in the abstract or described claims; the derivations are independent mathematical arguments whose validity is internal to the combinatorial constructions.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The central claims rest on standard definitions of permutation patterns and stack operations together with the newly introduced σ-machine model and greedy procedure; no free parameters or invented entities with independent evidence are visible from the abstract.

axioms (2)

domain assumption The sorting procedure always performs the rightmost legal operation at each step.
Explicitly stated in the abstract as the algorithm used for the σ-machine.
domain assumption The first stack maintains a sequence that avoids the pattern σ when read from top to bottom.
Core restriction defining the σ-machine in the abstract.

invented entities (1)

σ-machine no independent evidence
purpose: Sorting device consisting of two stacks in series with the first stack required to avoid pattern σ
New model introduced to study the restricted variant of stack sorting.

pith-pipeline@v0.9.0 · 5733 in / 1248 out tokens · 29710 ms · 2026-05-24T19:19:20.680722+00:00 · methodology

Stack sorting with restricted stacks

Core claim

What carries the argument

If this is right

Where Pith is reading between the lines

Load-bearing premise

What would settle it

discussion (0)