{
  "id": "1511.00192",
  "version": "v1",
  "published": "2015-11-01T00:15:00.000Z",
  "updated": "2015-11-01T00:15:00.000Z",
  "title": "Pattern avoidance for set partitions à la Klazar",
  "authors": [
    "Jonathan Bloom",
    "Dan Saracino"
  ],
  "comment": "21 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "In 2000 Klazar introduced a new notion of pattern avoidance in the context of set partitions of $[n]=\\{1,\\ldots, n\\}$. The purpose of the present paper is to undertake a study of the concept of Wilf-equivalence based on Klazar's notion. We determine all Wilf-equivalences for partitions with exactly two blocks, one of which is a singleton block, and we conjecture that, for $n\\geq 4$, these are all the Wilf-equivalences except for those arising from complementation. If $\\tau$ is a partition of $[k]$ and $\\Pi_n(\\tau)$ denotes the set of all partitions of $[n]$ that avoid $\\tau$, we establish inequalities between $|\\Pi_n(\\tau_1)|$ and $|\\Pi_n(\\tau_2)|$ for several choices of $\\tau_1$ and $\\tau_2$, and we prove that if $\\tau_2$ is the partition of $[k]$ with only one block, then $|\\Pi_n(\\tau_1)| <|\\Pi_n(\\tau_2)|$ for all $n>k$ and all partitions $\\tau_1$ of $[k]$ with exactly two blocks. We conjecture that this result holds for all partitions $\\tau_1$ of $[k]$. Finally, we enumerate $\\Pi_n(\\tau)$ for all partitions $\\tau$ of $[4]$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-11-01T00:15:00.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05A18"
    ],
    "keywords": [
      "set partitions",
      "pattern avoidance",
      "wilf-equivalence",
      "singleton block",
      "conjecture"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 21,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2015arXiv151100192B"
    }
  }
}