Keyboard shortcuts

Press ← or → to navigate between chapters

Press ? to show this help

Press Esc to hide this help

Increasing inflation of the minimum

Abstract

Let a word in C consist of a prefix, the entry one, and a suffix, with every entry of the prefix and suffix at least two. Increasing all those other entries by one and replacing the minimum by the adjacent entries one and two preserves membership in C.

Theorem 1.1 (Increasing inflation of the minimum).

Lean statement: D5/S3/Combinatorics/PopStack/PopStackIncreasing.increasing_minimum_inflation

Proof. Machine-checked in Lean as D5/S3/Combinatorics/PopStack/PopStackIncreasing.increasing_minimum_inflation (✓ 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.

Let a word in C consist of a prefix, the entry one, and a suffix, with every entry of the prefix and suffix at least two. Increasing all those other entries by one and replacing the minimum by the adjacent entries one and two preserves membership in C.

References