Keyboard shortcuts

Press ← or → to navigate between chapters

Press ? to show this help

Press Esc to hide this help

The two value regions below a second-position maximum

Abstract

For a permutation of size at least four with maximum second, consider its suffix after the first two entries. Require that values above the first entry decrease and that no value below the first entry has both a smaller and a larger such value later. These two conditions imply membership in C, and every simple member of C with maximum second satisfies them.

Theorem 1.1 (The two value regions below a second-position maximum).

Lean statement: D5/S3/Combinatorics/PopStack/PopStackMaximumShape.maximum_second_shape

Proof. Machine-checked in Lean as D5/S3/Combinatorics/PopStack/PopStackMaximumShape.maximum_second_shape (✓ std3). ∎

Source. Repository-derived.

Acknowledgement. Lapo Cioni, Luca Ferrari, Rebecca Smith (2025). Sorting permutations using a pop stack with a bypass. DOI: 10.1016/j.disc.2025.114964. URL: https://arxiv.org/abs/2503.08285v1.

Commentary.

For a permutation of size at least four with maximum second, consider its suffix after the first two entries. Require that values above the first entry decrease and that no value below the first entry has both a smaller and a larger such value later. These two conditions imply membership in C, and every simple member of C with maximum second satisfies them.

References