Asymptotics of Pattern Avoidance in the Permutation-Tuple and Klazar Set Partition Settings

MaRDI QIDQ6277705zbMATH OpenFDO

Authors Benjamin Gunby

Publication date 20 September 2016

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Asymptotic enumeration (05A16) Partitions of sets (05A18) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Partial orders, general (06A06)

Abstract: We consider asymptotics of set partition pattern avoidance in the sense of Klazar. One of the results of this paper extends work of Alweiss, and finds a classification for set partitions $pi$ such that the number of set partitions of $[n]$ avoiding $pi$ grows more slowly than $n^{cn}$ for all $c>0$. Several conjectures are proposed, and the related question of asymptotics of parallel ($k$-tuple) permutation pattern avoidance is considered and solved completely to within an exponential factor, generalizing Marcus and Tardos's 2004 proof of the Stanley-Wilf Conjecture.

This page was built for publication: Asymptotics of Pattern Avoidance in the Permutation-Tuple and Klazar Set Partition Settings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6277705)