{
  "id": "1909.13348",
  "version": "v1",
  "published": "2019-09-29T19:35:18.000Z",
  "updated": "2019-09-29T19:35:18.000Z",
  "title": "Wilf collapse in permutation classes",
  "authors": [
    "Michael Albert",
    "Vít Jelínek",
    "Michal Opler"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "For a hereditary permutation class $\\mathcal{C}$, we say that two permutations $\\pi$ and $\\sigma$ of $\\mathcal{C}$ are Wilf-equivalent in $\\mathcal{C}$, if $\\mathcal{C}$ has the same number of permutations avoiding $\\pi$ as those avoiding $\\sigma$. We say that a permutation class $\\mathcal{C}$ exhibits a Wilf collapse if the number of permutations of size $n$ in $\\mathcal{C}$ is asymptotically larger than the number of Wilf-equivalence classes formed by these permutations. In this paper, we show that Wilf collapse is a surprisingly common phenomenon. Among other results, we show that Wilf collapse occurs in any permutation class with unbounded growth and finitely many sum-indecomposable permutations. Our proofs are based on encoding the elements of a permutation class $\\mathcal{C}$ as words, and analyzing the structure of a random permutation in $\\mathcal{C}$ using this representation.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-09-29T19:35:18.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05A05",
      "05A15",
      "05A16"
    ],
    "keywords": [
      "hereditary permutation class",
      "wilf collapse occurs",
      "surprisingly common phenomenon",
      "random permutation",
      "wilf-equivalence classes"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}