Cocommutative Hopf Algebra Of Parking Functions

The notions of atomic partition and unsplitable partition arise in the study of thefreeness of the Hopf algebra of symmetric functions in noncommuting variables. Inthis thesis, we first construct a bijection from atomic partitions to unsplitable partitionsand so solve the open problem proposed by Can and Sagan. Then we generalize thesetwo notions to parking functions and show that the set of atomic parking functionsis also in bijection with the set of unsplitable parking functions. As the third mainresult, we construct a cocommutative Hopf algebra of parking functions which hastwo free generating sets indexed by atomic parking functions and unsplitable parkingfunctions respectively. The structure and various Hopf subalgebras of this Hopf algebraare studied in detail.This thesis is structured as follows.We start by giving an overview of the background of our results in combinatorialHopf algebra in Chapter1. For the sake of completeness, we introduce some basicdefinitions and results from the theory of Hopf algebras in Chapter2.In Chapter3, we first review some basic definitions about combinatorics of setpartitions that will be used in this thesis, including the notion of set partition, the slashproduct and the split product on partitions, the notions of atomic partition and un-splitable partition. Then we introduce briefly the Hopf algebra NCSym of symmetricfunctions in noncommuting variables in a combinatorial way and recall some relevantresults about its structure, including freeness, cofreeness, primitive elements and theantipode. This Hopf algebra has two free generating sets which are indexed by atomicpartitions and unsplitable partitions respectively. This means that there must exist abijection between atomic partitions and unsplitable partitions, we find such a bijectionin the last section of this chapter and so solve the open problem proposed by Can andSagan.By introducing two associative binary operations, the slash product and the splitproduct, on the set P of parking functions, we generalize the notions of atomic par- tition and unsplitable partition to parking function in Chapter4. As will be seen, theslash product is just a variant of shifted concatenation, while the split product is de-fined via the notion of LR-decomposition for parking functions. In the third section, wefind an injection from partitions to parking functions that preserves the slash productand the split product, which means that these two operations on parking functions arenatural generalizations of those on partitions. In the fourth section, it is shown thatP and P are free monoids generated by atomic parking functions and unsplitableparking functions respectively. At the end of this chapter, we show that for each n1,atomic parking functions of length n are in bijection with unsplitable parking functionsof length n, extending the result on set partitions.In Chapter5, we construct a cocommutative Hopf algebra P of parking func-tions. The product of P mimics that of NCSym and the coproduct is defined bymaking use of the notion of parkization. We end this chapter by showing that Pincludes NCSym as Hopf subalgebra by presenting a natural injective homomorphism.Chapter6is devoted to the detailed study of the structure of the Hopf algebra P.It is shown that this Hopf algebra is both free and cofree. Besides, primitive elementsand the antipode are described explicitly in a combinatorial way. The last section ofthis chapter is concerned with various Hopf subalgebras of P. Among them, we findHopf algebras isomorphic to the Grossman-Larson Hopf algebras of ordered trees andheap-ordered trees respectively.