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 Steingrímsson. 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 Erdős-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.
@article{10_37236_4479,
author = {Andrew M. Baxter and Lara K. Pudwell},
title = {Ascent sequences avoiding pairs of patterns},
journal = {The electronic journal of combinatorics},
year = {2015},
volume = {22},
number = {1},
doi = {10.37236/4479},
zbl = {1308.05001},
url = {http://geodesic.mathdoc.fr/articles/10.37236/4479/}
}
TY - JOUR
AU - Andrew M. Baxter
AU - Lara K. Pudwell
TI - Ascent sequences avoiding pairs of patterns
JO - The electronic journal of combinatorics
PY - 2015
VL - 22
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/4479/
DO - 10.37236/4479
ID - 10_37236_4479
ER -
%0 Journal Article
%A Andrew M. Baxter
%A Lara K. Pudwell
%T Ascent sequences avoiding pairs of patterns
%J The electronic journal of combinatorics
%D 2015
%V 22
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/4479/
%R 10.37236/4479
%F 10_37236_4479
Andrew M. Baxter; Lara K. Pudwell. Ascent sequences avoiding pairs of patterns. The electronic journal of combinatorics, Tome 22 (2015) no. 1. doi: 10.37236/4479
