Georgia Institute of Technology College of Sciences

The permutation removal lemma was first proved by Klimosová and Král’, and later reproved by Fox and Wei in the context of permutation property testing. In this talk, we study a local version of the permutation removal problem. We show that for any permutation σ not equal to 12, 21, 132, 231, 213, or 312, there exists ε(σ) > 0 such that for any sufficiently large integer N, there is a permutation π of length N that is ε-far from being σ-free with respect to the ρ∞ distance, yet contains only a single copy of σ. Here, the ρ∞ distance is defined as an L∞-variant of the Earth Mover’s Distance between two permutations. We will also discuss our result on the local induced graph removal problem. This is joint work with Fan Wei.