Asymptotics of pattern avoidance in the Klazar set partition and permutation-tuple settings

摘要

We consider asymptotics of set partition pattern avoidance in the sense of Klazar. Our main result derives the asymptotics of the number of set partitions avoiding a given set partition within an exponential factor, which leads to a classification of possible growth rates of set partition pattern classes. We further define a notion of permutation-tuple avoidance, which generalizes notions of Aldred et al. and the usual permutation pattern setting, and similarly determine the number of permutation-tuples avoiding a given tuple to within an exponential factor. We note a seeming connection to previous results on hereditary properties of labelled graphs, prompting the question of if there is a generalization to ordered graphs. (C) 2019 Elsevier Ltd. All rights reserved.