A Complete Dichotomy for L_∞ Permutation Removal

Abstract

We study the removal problem for permutation patterns under the normalized L_∞ earth mover's distance. We prove a complete dichotomy. Let ℰ ={(12),(21),(132),(213),(231),(312)}. If σ∈ℰ, then every permutation of length n that is ε-far from being σ-free contains at least ε(n−1) copies of σ; for 0<ε≤ 1/16, this is sharp up to a constant factor for all sufficiently large n. If σ∈ S_k∖ℰ, then for every sufficiently large n there is a permutation of length n that is 1/(8k)-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.

Short permutation pattern waves: The complete length-five classification
Lihong Qiu, Minglei Mao, Yaping Mao
arXiv3 Nov 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
Characterization of a class of complete permutation quadrinomials over 𝔽_2^2m
Yanjun Li, Maosheng Xiong
arXiv9 Sep 2026PreprintarXiv licenceFull textAlgebra & number theoryarXiv
A complete classification of permutation binomials of the form X^r(X^q−1+a) over finite fields
Xiang Fan
arXiv17 Sep 2026PreprintarXiv licenceFull textAlgebra & number theory Combinatorics & discrete mathematicsarXiv
Two Generalizations of the G_0 Dichotomy
B. Miller
arXiv18 Oct 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematics Logic & foundationsarXiv
The P-Ideal Dichotomy and the Failure of Two-Cardinal Square Principles
Victor Torres-Perez, Liuzhen Wu
arXiv3 Nov 2026PreprintarXiv licenceFull textLogic & foundationsarXiv

Cite

BibTeX RIS

BibTeX

@misc{le2026complete,
  title = {{A Complete Dichotomy for $L_\infty$ Permutation Removal}},
  author = {Viet Hung Le and Ruilin Shi and Fan Wei},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.28271},
  eprint = {2610.28271},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.28271},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - A Complete Dichotomy for L_∞ Permutation Removal
AU  - Viet Hung Le
AU  - Ruilin Shi
AU  - Fan Wei
PY  - 2026
DA  - 2026/10/20
PB  - arXiv
DO  - 10.48550/arxiv.2610.28271
UR  - https://arxiv.org/abs/2610.28271
AB  - We study the removal problem for permutation patterns under the normalized L_∞ earth mover's distance. We prove a complete dichotomy. Let ℰ ={(12),(21),(132),(213),(231),(312)}. If σ∈ℰ, then every permutation of length n that is ε-far from being σ-free contains at least ε(n−1) copies of σ; for 0<ε≤ 1/16, this is sharp up to a constant factor for all sufficiently large n. If σ∈ S_k∖ℰ, then for every sufficiently large n there is a permutation of length n that is 1/(8k)-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.
ER  -

Abstract

Related

Cite