{
  "id": "1309.4643",
  "version": "v1",
  "published": "2013-09-18T13:47:48.000Z",
  "updated": "2013-09-18T13:47:48.000Z",
  "title": "Set Systems Containing Many Maximal Chains",
  "authors": [
    "J. Robert Johnson",
    "Imre Leader",
    "Paul A. Russell"
  ],
  "comment": "5 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "The purpose of this short problem paper is to raise an extremal question on set systems which seems to be natural and appealing. Our question is: which set systems of a given size maximise the number of $(n+1)$-element chains in the power set $\\mathcal{P}(\\{1,2,\\dots,n\\})$? We will show that for each fixed $\\alpha>0$ there is a family of $\\alpha 2^n$ sets containing $(\\alpha+o(1))n!$ such chains, and that this is asymptotically best possible. For smaller set systems we are unable to answer the question. We conjecture that a `tower of cubes' construction is extremal. We finish by mentioning briefly a connection to an extremal problem on posets and a variant of our question for the grid graph.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2013-09-18T13:47:48.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05D05"
    ],
    "keywords": [
      "set systems containing",
      "maximal chains",
      "short problem paper",
      "smaller set systems",
      "extremal question"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 5,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1309.4643J"
    }
  }
}