betaFeedback

WorksMathematics

A Complete Dichotomy for L∞L_\infty Permutation Removal

Abstract

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

Introduction

The graph removal lemma is one of the main tools in extremal combinatorics. To state it, let GG and HH be graphs on the same vertex set [n][n], and define their normalized edit distance by d1(G,H)=∣E(G)△E(H)∣(n2)d_1(G,H)=\frac{|E(G)\mathbin{\triangle}E(H)|}{\binom{n}{2}}, the fraction of vertex pairs whose adjacency must be changed. Thus d1d_1 is essentially the normalized L1L_1 distance between the two adjacency matrices. We say that GG is ε\varepsilon-far from being FF-free if d1(G,H)≥εd_1(G,H)\ge\varepsilon for every FF-free graph HH on [n][n]. The graph removal lemma states that, if a graph is far from being FF-free, then it should contain many copies of FF. The precise statement is that, for every fixed graph FF and every ε>0\varepsilon>0, there is a constant δF(ε)>0\delta_F(\varepsilon)>0 such that every nn-vertex graph that is ε\varepsilon-far from being FF-free contains at least δF(ε)n∣V(F)∣\delta_F(\varepsilon)n^{|V(F)|} copies of FF. The triangle case is due to Ruzsa and Szemerédi [23], and the general result was proved by Alon, Duke, Lefmann, Rödl, and Yuster [2] and by Füredi [14]. The usual proof combines Szemerédi’s regularity lemma [24] with a counting lemma.

Removal lemmas are important not only in extremal combinatorics, but also in number theory, discrete geometry, and theoretical computer science. In particular, they give one-sided property testers. If every graph that is ε\varepsilon-far with respect to the L1L_1 distance from being FF-free contains many A central question is to determine the best possible dependence of δF(ε)\delta_F(\varepsilon) on ε\varepsilon. This remains a major open problem even for F=K3F=K_3. Alon [1] proved that a polynomial bound is possible if and only if FF is bipartite, but this does not determine the sharp quantitative bound. See [16] for a recent survey and for related results for directed graphs, tournaments, and hypergraphs.

Permutations arise naturally in rankings and permutation patterns give a similar setting. A permutation π\pi contains a pattern σ\sigma if some subsequence of π\pi has the same relative order as σ\sigma. Pattern avoidance is a basic topic in both extremal and enumerative combinatorics. This leads to the following property-testing question: can one decide whether a very large permutation is σ\sigma-free, or far from being σ\sigma-free, by looking at only a small random subpermutation?

For permutations, the answer depends on the metric. Cooper [5] proved a permutation removal lemma using a regularity argument. However, the result was not stated with respect to a metric, so it did not directly give a property-testing result. Hoppen, Kohayakawa, Moreira, and Sampaio [18] proved that hereditary permutation properties are one-sided testable under the rectangular distance. Their proof uses compactness and gives no effective bound on the query complexity.

Klimošová and Král’ [20] proved that every hereditary permutation property is testable under Kendall’s tau distance, the normalized number of pairs whose relative order differs. Their bound is of Ackermann type in 1/ε1/\varepsilon. Fox and Wei [11, 12] obtained a polynomial bound for testing σ\sigma-freeness for every fixed pattern σ\sigma.

Fox and Wei [12, 13] also studied the earth mover’s distance

ρEMD(π1,π2)=(n2)−1min⁡θ∈Sn∑i=1n(∣i−θ(i)∣+∣π1(i)−π2(θ(i))∣).\rho_{\mathrm{EMD}}(\pi_1,\pi_2)=\binom{n}{2}^{-1}\min_{\theta\in S_n}\sum_{i=1}^{n}\left(|i-\theta(i)|+|\pi_1(i)-\pi_2(\theta(i))|\right).

This is the minimum normalized total L1L_1 transportation cost between the point sets of the two permutations.

An optimal matching between two permutations

Figure 1. An optimal matching (dashed line segments) with total L1L_1 cost 22 from π1=942587631\pi_1=942587631 to π2=168739245\pi_2=168739245; hence ρEMD(π1,π2)=22/(92)=11/18\rho_{\mathrm{EMD}}(\pi_1,\pi_2)=22/\binom{9}{2}=11/18.

An optimal matching from the decreasing permutation to its endpoint swap

Figure 2. An optimal matching (θ(i)=i\theta(i)=i for every i≠1,ni\ne1,n) from the decreasing permutation δ15\delta_{15} to its endpoint swap τ\tau (τ(1)=1\tau(1)=1 and τ(n)=n\tau(n)=n) with total L1L_1 cost 28; hence ρEMD(δ15,τ)=28/(152)=4/15\rho_{\mathrm{EMD}}(\delta_{15},\tau)=28/\binom{15}{2}=4/15.

Fox and Wei [12, 13] proved polynomial-query two-sided testing results for hereditary permutation properties and also obtained a canonical one-sided tester for a closely related metric that is quantitatively equivalent to earth mover’s distance. In particular, for every fixed pattern σ∈Sk\sigma\in S_k and every ε>0\varepsilon>0, their results imply a removal lemma with respect to earth mover’s distance: There exists a δσ,EMD(ε)>0\delta_{\sigma,\mathrm{EMD}}(\varepsilon)>0 such that every sufficiently large permutation that is ε\varepsilon-far from being σ\sigma-free under earth mover’s distance contains at least δσ,EMD(ε)nk\delta_{\sigma,\mathrm{EMD}}(\varepsilon)n^k copies of σ\sigma.

The best possible dependence of δσ,EMD(ε)\delta_{\sigma,\mathrm{EMD}}(\varepsilon) on ε\varepsilon is not known in general. Thus the sharp quantitative removal problem remains open both for graph edit distance and for the permutation earth mover’s distance. Garbe, Hladký, Kun, and Pekárková [15] later gave a nonquantitative proof of permutation removal using the structure of pattern-avoiding permutons.

Our result

For the permutation metrics discussed above, farness from σ\sigma-freeness forces a positive density of σ\sigma-copies. The earth mover’s distance is an L1L_1-type metric: it measures the total transportation cost, so a small number of points may move a long distance at small total cost. We study the corresponding bottleneck metric, in which every point must move only a short distance.

For two permutations π1,π2∈Sn\pi_1,\pi_2\in S_n, define the L∞L_\infty-earth mover’s distance as

ρ∞(π1,π2)=1n−1min⁡θ∈Snmax⁡1≤i≤nmax⁡{∣i−θ(i)∣,∣π1(i)−π2(θ(i))∣}.\rho_\infty(\pi_1,\pi_2)=\frac{1}{n-1}\min_{\theta\in S_n}\max_{1\le i\le n}\max\left\{|i-\theta(i)|,\left|\pi_1(i)-\pi_2(\theta(i))\right|\right\}.

Figure 3 and Figure 4 provide a visual example of the distance between two permutations, illustrating an optimal geometric matching that minimizes the maximum individual displacement. Thus earth mover’s distance minimizes a sum of displacements, while ρ∞\rho_\infty minimizes the largest displacement of any matched point. Although ρEMD\rho_{\mathrm{EMD}} and ρ∞\rho_\infty have comparable magnitudes for the illustrated pair (π1,π2)(\pi_1,\pi_2), the decreasing permutation δn\delta_n and its endpoint swap τn\tau_n satisfy ρEMD(δn,τn)=4/n\rho_{\mathrm{EMD}}(\delta_n,\tau_n)=4/n while ρ∞(δn,τn)→1/2\rho_\infty(\delta_n,\tau_n)\to1/2 as n→∞n\to\infty, showing that ρ∞\rho_\infty can exceed ρEMD\rho_{\mathrm{EMD}} by an arbitrarily large factor. A small ρ∞\rho_\infty asks that every matched point move only a short distance.

An optimal matching between two permutations

Figure 3. An optimal matching (dashed line segments) with maximum L∞L_\infty displacement 2 from π1=942587631\pi_1=942587631 to π2=168739245\pi_2=168739245; hence ρ∞(π1,π2)=2/(9−1)=1/4\rho_\infty(\pi_1,\pi_2)=2/(9-1)=1/4.

An optimal matching from the decreasing permutation to its endpoint swap

Figure 4. An optimal matching (dashed line segments) from the decreasing permutation δ15\delta_{15} to its endpoint swap τ\tau with maximum L∞L_\infty displacement 8; hence ρ∞(δ15,τ)=8/(15−1)=4/7\rho_\infty(\delta_{15},\tau)=8/(15-1)=4/7.

We ask the following question: if a permutation is ε\varepsilon-far from being σ\sigma-free under ρ∞\rho_\infty, how many copies of σ\sigma must it contain?

Complete dichotomy. Let E={(12),(21),(132),(213),(231),(312)}\mathcal{E}=\{(12),(21),(132),(213),(231),(312)\} be the set of six permutations. We prove that the answer has only two possible forms. For σ∈E\sigma\in\mathcal{E}, ε\varepsilon-farness forces Θ(εn)\Theta(\varepsilon n) copies. For every other pattern σ\sigma of length kk, a single copy can keep a permutation 1/(8k)1/(8k)-far from being σ\sigma-free. Thus the usual positive-density removal conclusion fails for every nontrivial pattern, but the precise sparse behavior is completely classified.

To be more precise, for σ∈Sk\sigma\in S_k and π∈Sn\pi\in S_n, a σ\sigma-copy in π\pi is a set of indices 1≤i1<⋯<ik≤n1 \le i_1 < \cdots< i_k \le n such that

π(ia)<π(ib)⟺σ(a)<σ(b)for all a,b∈[k].\pi(i_a) < \pi(i_b) \quad\Longleftrightarrow\quad\sigma(a) < \sigma(b) \qquad\text{for all } a,b \in[k].

We denote the number of σ\sigma-copies in π\pi by Nσ(π)N_\sigma(\pi) and call π\pi σ\sigma-free if Nσ(π)=0N_\sigma(\pi)=0.

Theorem 1.1. Let σ∈E\sigma\in\mathcal{E}. For every n≥2n \ge2, every π∈Sn\pi\in S_n, and every ε>0\varepsilon> 0, if π\pi is ε\varepsilon-far from being σ\sigma-free with respect to ρ∞\rho_\infty, then

Nσ(π)≥ε(n−1).N_\sigma(\pi) \ge\varepsilon(n-1).

The bound ε(n−1)\varepsilon(n-1) is essentially tight. Indeed, for every 0<ε≤1/160 < \varepsilon\le1/16 and all sufficiently large nn, there is a permutation π∈Sn\pi\in S_n that is ε\varepsilon-far from being σ\sigma-free and satisfies

Nσ(π)≤6εn.N_\sigma(\pi) \le6\varepsilon n.

References

  1. [1]N. Alon, Testing subgraphs in large graphs, Random Structures & Algorithms 21 (2002), no. 3–4, 359–370.
  2. [2]N. Alon, R. A. Duke, H. Lefmann, V. Rödl, and R. Yuster, The algorithmic aspects of the regularity lemma, Journal of Algorithms 16 (1994), no. 1, 80–109.
  3. [5]J. N. Cooper, A permutation regularity lemma, Electronic Journal of Combinatorics 13 (2006), no. 1, Research Paper 22.DOI
  4. [11]J. Fox and F. Wei, Strongly testing hereditary permutation properties with polynomial query complexity, unpublished manuscript, 2015.
  5. [12]J. Fox and F. Wei, Permutation property testing under different metrics with low query complexity, in Proceedings of the Twenty-Eighth Annual ACM–SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2017, pp. 1618–1637.
  6. [13]J. Fox and F. Wei, Fast property testing and metrics for permutations, Combinatorics, Probability and Computing 27 (2018), no. 4, 539–579.arxiv.org/abs/1611.01270
  7. [14]Z. Füredi, Extremal hypergraphs and combinatorial geometry, in Proceedings of the International Congress of Mathematicians (Zürich, 1994), vol. II, Birkhäuser, Basel, 1995, pp. 1343–1352.DOI
  8. [15]F. Garbe, J. Hladký, G. Kun, and K. Pekárková, On pattern-avoiding permutations, Random Structures & Algorithms 65 (2024), no. 1, 46–60.
  9. [16]L. Gishboliner and A. Shapira, Polynomial property testing, Computer Science Review 58 (2025), Article 100806.
  10. [18]C. Hoppen, Y. Kohayakawa, C. G. Moreira, and R. M. Sampaio, Testing permutation properties through subpermutations, Theoretical Computer Science 412 (2011), no. 29, 3555–3567.DOI
  11. [19]C. Hoppen, Y. Kohayakawa, and R. M. Sampaio, A note on permutation regularity, Discrete Applied Mathematics 160 (2012), no. 18, 2716–2727.
  12. [20]T. Klimošová and D. Král’, Hereditary properties of permutations are strongly testable, in Proceedings of the Twenty-Fifth Annual ACM–SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2014, pp. 1164–1173.
  13. [23]I. Z. Ruzsa and E. Szemerédi, Triple systems with no six points carrying three triangles, in Combinatorics (Keszthely, 1976), vol. II, Colloquia Mathematica Societatis János Bolyai, vol. 18, North-Holland, Amsterdam, 1978, pp. 939–945.
  14. [24]E. Szemerédi, Regular partitions of graphs, in Problèmes combinatoires et théorie des graphes, Colloques Internationaux du CNRS, vol. 260, CNRS, Paris, 1978, pp. 399–401.
  15. [25]L. de Moura and S. Ullrich, The Lean 4 theorem prover and programming language, in Automated Deduction – CADE 28, Lecture Notes in Artificial Intelligence 12699, Springer, Cham, 2021, pp. 625–635.DOI
  16. [26]The mathlib Community, The Lean mathematical library, in Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs, ACM, New York, 2020, pp. 367–381.DOI
  17. [27]R. Zhou, formalize-paper: formalize a mathematics paper in Lean 4 with an audit trail, version 0.2.0, 2026, https://github.com/ZRTMRH/formalize-paper.

Paper details

vlnc:W_ka7bnknd
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents