Pattern-avoiding permutons and a removal lemma for permutations

Frederik Garbe, Jan Hladký, Gábor Kun, Kristýna Pekárková

Published 2022-08-26Version 1

The theory of limits of permutations leads to limit objects called permutons, which are certain Borel measures on the unit square. We prove that permutons avoiding a permutation $A$ of order $k$ have a particularly simple structure. Namely, almost every fiber of the support of the permuton consists only of atoms, at most $k-1$ many, and this bound is best-possible. From this, we derive the following removal lemma. Suppose that $A$ is a permutation. Then for every $\varepsilon>0$ there exists $\delta>0$ so that if $\pi$ is a permutation on $\{1,\ldots,n\}$ with density of $A$ less than $\delta$, then there exists a permutation $\tilde{\pi}$ on $\{1,\ldots,n\}$ which is $A$-avoiding and $\sum_i|\pi(i)-\tilde{\pi}(i)|<\varepsilon n^2$.