Recall the notion of dual of a finite dimensional vector space.

Theorem 4If C is a cogebra, with , then the vector sapce dual is an algebra with product and unit , defined by

The unit is defined in a similar dual manner.

If C is cocommutative (not required for Hopf), then is commutative.

Theorem 5If A is an algebra, with product , then is a cogebra, . We work with Sweedler dual is A is infinite dimensional.

Now we give QSYM a Hopf algebra structure. It’s already an algebra under function multiplication. So we need a cogebra structure. Define

for instance . And we extend by .

For co-unit we let the constant term ( coefficient) in .

Recall QSYM, because the monomial symmetric polynomial . In fact is a sub-Hopf algebra of QSYM. The coproduct for is given on the particular power sum polynomial by

This gives

Basically the sum just means we arrange the into two piles with weights the same as inverse riffle shuffle.

Next we introduce NCSYM (noncommutative symmetric polynomials) with generators , . forms an algebra by concateation, with grading given by . The basis for the degree part is

with .

One can construct a cogebra structure on NCSYM by , and the counit given by the constant term as usual. NCSYM and QSYM are in duality, . The ideal I in NCSYM generated by commutators is a Hopf ideal

with mapped to .

Combinatorial Hopf-algebra has a character which is a linear function from to a field, that is multiplicative. They form a group and can be tensored. If H is cocommutative, then the character is abelian. More formally,

Definition 6A combinatorial Hopf algebra is a graded, connected Hopf algebra with a character .

For QSYM, the constant part.

Theorem 7For an combinatorial Hopf algebra , there is a unique morphism , given bywhere the nth grading of , and

For example, .

Example: Let be the vector space with basis being the isomorphism classes of graphs. For two graphs and we can define the product of the basis elements they represent by the disjoint union. Then we can define

where denotes the induced subgraph on from .

Theorem 8The above defines a co-commutative Hopf algebra, with if is a discrete, i.e., has no edges, and otherwise.

Theorem 9For cocommutative combinatorial Hopf algebras, there is a unique morphism given by the same formula as before.

For the graph algebra described above, gives the *Stanley chromatic symmetric function*, which has connections to the birthday problem, which can be phrased the following way.

What is the proportion of the set of proper colorings of the complete graph on vertices in the set of all colorings of with colors? The answer is of course .

More general, given a graph , let be the number of proper colorings of with colors, which is a polynomial, whose computation is -P.

Motivated by the fact that not all birthdays are equal because doctors don’t like to work on weekends, we introduce the model whereby is the probability that color is chosen, . Then it is easy to see

where stands for the probability of having a proper coloring given the chance of each color , and denotes the th elementary symmetric polynomial. For more general graph , gives the Stanley chromatic polynomial.