pipette
ESEspañol

A Complete Dichotomy for Permutation Removal

Viet Hung Le, Ruilin Shi, and Fan Wei

Preprint

In the authors' words

We study the removal problem for permutation patterns under the normalized earth mover's distance. We prove a complete dichotomy. Let \[ \mathcal E =\{(12),(21),(132),(213),(231),(312)\}. \] If , then every permutation of length that is -far from being -free contains at least copies of ; for , this is sharp up to a constant factor for all sufficiently large . If , then for every sufficiently large there is a permutation of length that is -far from being -free and contains exactly one copy of . Thus the usual positive-density removal conclusion fails for every nontrivial permutation pattern, but the sparse behavior is completely characterized: the minimum number of copies is linear for exactly six patterns and is one for all others. Consequently, no canonical one-sided tester that rejects only after finding a forbidden copy can have query complexity independent of the permutation length.

Main resultThe abstract does not state a limitation.

Appeared: Wednesday, October 21. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: The results and proofs in this paper have also been formally verified in Lean~4; see the "Formal verification'' section following the main text for details