A Complete Dichotomy for Permutation Removal
En palabras de los autores
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.
Apareció: miércoles, 21 de octubre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 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