Keyboard shortcuts

Press ← or → to navigate between chapters

Press ? to show this help

Press Esc to hide this help

Second-position and third-position minima

Abstract

For every n at least four, Phi(n) bijects the simple permutations of size n in C with minimum second and those with minimum third. The map undoPhi(n) is its inverse on both sets.

Theorem 1.1 (Second-position and third-position minima).

Lean statement: D5/S3/Combinatorics/PopStack/PopStackThirdEquivalence.third_minimum_bijection

Proof. Machine-checked in Lean as D5/S3/Combinatorics/PopStack/PopStackThirdEquivalence.third_minimum_bijection (✓ 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 every n at least four, Phi(n) bijects the simple permutations of size n in C with minimum second and those with minimum third. The map undoPhi(n) is its inverse on both sets.

References