{
  "id": "2208.12712",
  "version": "v1",
  "published": "2022-08-26T15:13:11.000Z",
  "updated": "2022-08-26T15:13:11.000Z",
  "title": "Pattern-avoiding permutons and a removal lemma for permutations",
  "authors": [
    "Frederik Garbe",
    "Jan Hladký",
    "Gábor Kun",
    "Kristýna Pekárková"
  ],
  "comment": "16 pages, 3 figures, preliminary version",
  "categories": [
    "math.CO"
  ],
  "abstract": "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$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-08-26T15:13:11.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05A05",
      "G.2.1"
    ],
    "keywords": [
      "removal lemma",
      "permutation",
      "pattern-avoiding permutons",
      "limit objects",
      "borel measures"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 16,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}