{
  "id": "1401.5709",
  "version": "v1",
  "published": "2014-01-22T15:53:21.000Z",
  "updated": "2014-01-22T15:53:21.000Z",
  "title": "Three Generalizations of Davenport-Schinzel Sequences",
  "authors": [
    "Seth Pettie"
  ],
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "We present new, and mostly sharp, bounds on the maximum length of certain generalizations of Davenport-Schinzel sequences. Among the results are sharp bounds on order-$s$ {\\em double DS} sequences, for all $s$, sharp bounds on sequences avoiding {\\em catenated permutations} (aka formation free sequences), and new lower bounds on sequences avoiding {\\em zig-zagging} patterns.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-01-22T15:53:21.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "davenport-schinzel sequences",
      "generalizations",
      "sharp bounds",
      "aka formation free sequences",
      "maximum length"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1401.5709P"
    }
  }
}