Pattern Hopf algebras (Q2155549)

A combinatorial presheaf (or species with contraction) is a contravariant functor from the category of finite sets with injections to the category of finite sets with maps. They form a symmetric monoidal category with the Cauchy tensor product. To any monoid \(A\) in this category is associated a Hopf algebra, with the help of pattern functions counting the number of a given pattern in any element of \(A\), in a functorial way. The coproduct is in some sense dual to the product and \(A\) and the product is a sort of quasi-shuffle product. Examples of this construction include the Hopf algebra of symmetric functions, Vargas's Hopf algebra of permutations, examples on graphs or on marked permutations. When \(A\) is commutative and connected, it is proved that the associated Hopf algebra is a free commutative algebra. More results are given on marked permutations, including a decomposition theorem and that the associated Hopf algebra is a free non commutative Hopf algebra, with Lyndon words methods.