{
  "id": "1406.4100",
  "version": "v2",
  "published": "2014-06-16T19:03:39.000Z",
  "updated": "2015-02-15T02:27:45.000Z",
  "title": "Ascent sequences avoiding pairs of patterns",
  "authors": [
    "Andrew M. Baxter",
    "Lara K. Pudwell"
  ],
  "comment": "29 pages, 3 tables, 1 figure",
  "categories": [
    "math.CO"
  ],
  "abstract": "Ascent sequences were introduced by Bousquet-Melou et al. in connection with (2+2)-avoiding posets and their pattern avoidance properties were first considered by Duncan and Steingrimsson. In this paper, we consider ascent sequences of length $n$ avoiding two patterns of length 3, and we determine an exact enumeration for 16 different pairs of patterns. Methods include simple recurrences, bijections to other combinatorial objects (including Dyck paths and pattern-avoiding permutations), and generating trees. We also provide an analogue of the Erdos-Szekeres Theorem to prove that any sufficiently long ascent sequence contains either many copies of the same number or a long increasing subsequence, with a precise bound.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-06-16T19:03:39.000Z",
      "abstract": "Ascent sequences were introduced by Bousquet-Melou et al. in connection with (2+2)-avoiding posets and their pattern avoidance properties were first considered by Duncan and Steingrimsson. We consider the problem of counting the number of ascent sequences of length $n$ avoiding two patterns of length 3, answering the question for each of the 16 pairs. Methods include simple recurrences, bijections to other combinatorial objects (including Dyck paths and pattern-avoiding permutations), and generating trees. We also provide an analogue of the Erdos-Szekeres Theorem to prove that any sufficiently long ascent sequence contains either many copies of the same number or a long increasing subsequence, with a precise bound.",
      "comment": "28 pages, 3 tables, 1 figure",
      "journal": null,
      "doi": null
    },
    {
      "version": "v2",
      "updated": "2015-02-15T02:27:45.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05A05",
      "05A15",
      "05A18",
      "05A19"
    ],
    "keywords": [
      "ascent sequences avoiding pairs",
      "sufficiently long ascent sequence contains",
      "simple recurrences",
      "combinatorial objects",
      "precise bound"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 29,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1406.4100B"
    }
  }
}