{
  "id": "1406.1887",
  "version": "v2",
  "published": "2014-06-07T11:32:29.000Z",
  "updated": "2015-07-06T13:23:14.000Z",
  "title": "Supersaturation and stability for forbidden subposet problems",
  "authors": [
    "Balazs Patkos"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "We address a supersaturation problem in the context of forbidden subposets. A family $\\mathcal{F}$ of sets is said to contain the poset $P$ if there is an injection $i:P \\rightarrow \\mathcal{F}$ such that $p \\le_P q$ implies $i(p) \\subset i (q)$. The poset on four elements $a,b,c,d$ with $a,b \\le c,d$ is called butterfly. The maximum size of a family $\\mathcal{F} \\subseteq 2^{[n]}$ that does not contain a butterfly is $\\Sigma(n,2)=\\binom{n}{\\lfloor n/2 \\rfloor}+\\binom{n}{\\lfloor n/2 \\rfloor+1}$ as proved by De Bonis, Katona, and Swanepoel. We prove that if $\\mathcal{F} \\subseteq 2^{[n]}$ contains $\\Sigma(n,2)+E$ sets, then it has to contain at least $(1-o(1))E(\\lceil n/2 \\rceil +1)\\binom{\\lceil n/2\\rceil}{2}$ copies of the butterfly provided $E\\le 2^{n^{1-\\varepsilon}}$ for some positive $\\varepsilon$. We show by a construction that this is asymptotically tight and for small values of $E$ we show that the minimum number of butterflies contained in $\\mathcal{F}$ is exactly $E(\\lceil n/2 \\rceil +1)\\binom{\\lceil n/2\\rceil}{2}$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-06-07T11:32:29.000Z",
      "comment": null,
      "journal": null,
      "doi": null
    },
    {
      "version": "v2",
      "updated": "2015-07-06T13:23:14.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "forbidden subposet problems",
      "supersaturation problem",
      "small values",
      "minimum number",
      "construction"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1406.1887P"
    }
  }
}