{
  "id": "1608.06326",
  "version": "v1",
  "published": "2016-08-22T21:56:40.000Z",
  "updated": "2016-08-22T21:56:40.000Z",
  "title": "On the longest monotone and alternating subsequences of pattern-avoiding permutations",
  "authors": [
    "Neal Madras",
    "Gökhan Yıldırım"
  ],
  "comment": "26 pages, 7 figures, 1 table",
  "categories": [
    "math.CO"
  ],
  "abstract": "We consider the distributions of the lengths of the longest monotone and alternating subsequences in classes of permutations of size $n$ that avoid a specific pattern or set of patterns, with respect to the uniform distribution on each such class. We obtain exact results for any class that avoids two patterns of length 3, as well as results for classes that avoid one pattern of length 4 or more. Typically, the longest monotone subsequences have expected length proportional to $n$ for pattern-avoiding classes, in contrast with the $\\sqrt n$ behaviour that holds for unrestricted permutations. As a byproduct, we derive some new properties of the \"rare region\" in the graph of a random permutation avoiding a pattern $\\tau$ of length $k$ of the form $k\\tau_2\\cdots\\tau_k$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-08-22T21:56:40.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05A05",
      "05A16"
    ],
    "keywords": [
      "alternating subsequences",
      "pattern-avoiding permutations",
      "longest monotone subsequences",
      "uniform distribution",
      "exact results"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 26,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}