{
  "id": "1511.01076",
  "version": "v1",
  "published": "2015-11-03T20:45:32.000Z",
  "updated": "2015-11-03T20:45:32.000Z",
  "title": "An Erdős--Hajnal analogue for permutation classes",
  "authors": [
    "Vincent Vatter"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $\\mathcal{C}$ be a permutation class that does not contain all layered permutations or all colayered permutations. We prove that there is a constant $c$ such that every permutation in $\\mathcal{C}$ of length $n$ contains a monotone subsequence of length $cn$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-11-03T20:45:32.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "permutation class",
      "erdős-hajnal analogue",
      "monotone subsequence"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2015arXiv151101076V"
    }
  }
}