?
Shuffle Algebras, Homology and Consecutive Pattern Avoidance
This paper has been started as a particular application of the method of resolutions via Grobner bases we suggested here. We introduce a notion of a shuffle algebra. A shuffle algebra is a Z+-graded vector space V=∪∞i=1 such that for any pair (i,j) there exists a collection of operations ∗σ:Vi⊗Vj→Vi+j numbered by (i,j)-shuffle permutations σ∈Si+j (i.e. σ preserves the order of the first i elements and the order of the last j elements) yielding the natural associativity conditions. Enumerative problems for monomial shuffle algebras are in one-to-one correspondence with the pattern avoidance problems for permutations. We present two homological results on shuffle algebras with monomial relations, and use them to prove exact and asymptotic results on consecutive pattern avoidance in permutations. Both results generalizes the classical results for associative algebras. The first homological result is a generalization of the Golod-Shafarevich theorem and the second one generalizes the theory of Anick chains. It seems that most of particular applications we discuss are known to specialists but the general method was definitely not known. We hope that it will simplify a lot of work in this area. It is not hard to see that shuffle algebras form an interesting class of binary shuffle operads and illustrates quite well the importance of the latter notion.