{
  "id": "1708.02436",
  "version": "v1",
  "published": "2017-08-08T10:09:42.000Z",
  "updated": "2017-08-08T10:09:42.000Z",
  "title": "Subsets of posets minimising the number of chains",
  "authors": [
    "Wojciech Samotij"
  ],
  "comment": "13 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "A well-known theorem of Sperner describes the largest collections of subsets of an $n$-element set none of which contains another set from the collection. Generalising this result, Erd\\H{o}s characterised the largest families of subsets of an $n$-element set that do not contain a chain of sets $A_1 \\subset \\dotsc \\subset A_k$ of an arbitrary length $k$. The extremal families contain all subsets whose cardinalities belong to an interval of length $k-1$ centred at $n/2$. In a far-reaching extension of Sperner's theorem, Kleitman determined the smallest number of chains of length two that have to appear in a collection of a given number $a$ of subsets of an $n$-element set. For every $a$, this minimum is achieved by the collection comprising $a$ sets whose cardinalities are as close to $n/2+1/4$ as possible. We show that the same is true about chains of an arbitrary length $k$, for all $a$ and $n$, confirming the prediction Kleitman made fifty years ago. We also characterise all families of $a$ subsets with the smallest number of chains of length $k$ for all $a$ for which this smallest number is positive. Our argument is inspired by an elegant probabilistic lemma from a recent paper of Noel, Scott, and Sudakov, which in turn can be traced back to Lubell's proof of Sperner's theorem.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-08-08T10:09:42.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05D05",
      "06A07"
    ],
    "keywords": [
      "posets minimising",
      "element set",
      "smallest number",
      "arbitrary length",
      "sperners theorem"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 13,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}