A Complete Dichotomy for Permutation Removal
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.
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