{
  "id": "1603.02901",
  "version": "v1",
  "published": "2016-03-09T14:39:51.000Z",
  "updated": "2016-03-09T14:39:51.000Z",
  "title": "Linear Extensions and Comparable pairs in Partial Orders",
  "authors": [
    "Colin McDiarmid",
    "David Penman",
    "Vasileios Iliopoulos"
  ],
  "comment": "17 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "We study the number of linear extensions of a partial order with a given proportion of comparable pairs of elements, and estimate the maximum and minimum possible numbers. We also show that a random interval partial order on $n$ elements has close to a third of the pairs comparable with high probability, and the number of linear extensions is $n! \\, 2^{-\\Theta(n)}$ with high probability.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-03-09T14:39:51.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "06A07"
    ],
    "keywords": [
      "linear extensions",
      "comparable pairs",
      "random interval partial order",
      "high probability"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 17,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2016arXiv160302901M"
    }
  }
}