## Algebraic combinatorics lecture 13: Quasi-symmetric functions as a Hopf algebra, generalized birthday problem

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

Theorem 4 If C is a cogebra, with ${\Delta,\epsilon}$, then the vector sapce dual ${C^*}$ is an algebra with product ${\Delta^*}$ and unit ${\epsilon^*}$, defined by

$\displaystyle l_1.l_2(v) = l_1 \otimes l_2(\Delta v) = l_1 \otimes l_2(\sum v_i \otimes v_j) = \sum l_1(v_1) l_2(v_2). \ \ \ \ \ (12)$

The unit is defined in a similar dual manner.

If C is cocommutative (not required for Hopf), then ${C^*}$ is commutative.

Theorem 5 If A is an algebra, with product ${m}$, then ${A^*}$ is a cogebra, ${\Delta = m^*}$. We work with Sweedler dual ${A^\circ}$ 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

$\displaystyle \Delta m_\alpha= \sum_{\beta.\gamma = \alpha} m_\beta \otimes m_\gamma \ \ \ \ \ (13)$

for instance ${\Delta(m_{21}) = 1 \otimes m_{21} + m_2 \otimes m_1 + m_{21} \otimes 1}$. And we extend ${\Delta}$ by ${\Delta(m_\alpha m_\beta) = \Delta(m_\alpha) \Delta(m_\beta)}$.
For co-unit we let ${\epsilon(f)=}$ the constant term (${m_\emptyset}$ coefficient) in ${f}$.
Recall ${\Lambda \subset}$ QSYM, because the monomial symmetric polynomial ${m_\lambda = \sum_{\rm{par}(\alpha) = \lambda} m^Q_\alpha}$. In fact ${\Lambda}$ is a sub-Hopf algebra of QSYM. The coproduct for ${\Lambda}$ is given on the particular power sum polynomial ${p_n=p_{(n)} = m_{(n)}}$ by

$\displaystyle \Delta(p_n) = 1 \otimes p_n + p_n \otimes 1. \ \ \ \ \ (14)$

This gives

$\displaystyle \Delta(p_{n_1} \ldots p_{n_k}) = \sum_{\text{inverse riffle shuffle}} p_{\vec{a}} \otimes p_{\vec{b}}. \ \ \ \ \ (15)$

Basically the sum just means we arrange the ${p_{n_1}, \ldots, p_{n_k}}$ into two piles with weights the same as inverse riffle shuffle.
Next we introduce NCSYM (noncommutative symmetric polynomials) with generators ${H_i}$, ${1 \le i < \infty}$. ${k\langle H_i: 1 \le i < \infty \rangle}$ forms an algebra by concateation, with grading given by ${\deg H_n = n}$. The basis for the degree ${n}$ part is

$\displaystyle H_\alpha = H_{\alpha_1} H_{\alpha_2} \ldots H_{\alpha_n} \ \ \ \ \ (16)$

with ${\sum \alpha_i = n}$.
One can construct a cogebra structure on NCSYM by ${\Delta(H_n) = \sum_{i=0}^n H_i \otimes H_{n-i}}$, and the counit given by the constant term as usual. NCSYM and QSYM are in duality, ${\langle m_\alpha, H_\beta^* \rangle = \delta_{\alpha,\beta}}$. The ideal I in NCSYM generated by commutators is a Hopf ideal

$\displaystyle NCSYM / I \cong \Lambda \ \ \ \ \ (17)$

with ${H_\alpha}$ mapped to ${h_{\rm{par}(\alpha)}}$.
Combinatorial Hopf-algebra has a character which is a linear function from ${H}$ to ${k}$ a field, that is multiplicative. They form a group and can be tensored. If H is cocommutative, then the character ${\chi}$ is abelian. More formally,

Definition 6 A combinatorial Hopf algebra is a graded, connected Hopf algebra with a character ${\zeta}$.

For QSYM, ${\zeta(f) = f_0}$ the constant part.

Theorem 7 For an combinatorial Hopf algebra ${(H, \zeta)}$, there is a unique morphism ${\psi: (H,\zeta) \rightarrow (QSYM, \zeta_Q)}$, given by

$\displaystyle \psi(h) = \sum_{\alpha \models n} \zeta_\alpha(h) m_\alpha \ \ \ \ \ (18)$

where ${h \in H_n}$ the nth grading of ${H}$, and

$\displaystyle \zeta_\alpha: H \overset{\Delta^{k-1}}{\rightarrow} H^{\otimes k} \rightarrow H_{\alpha_1} \otimes \ldots \otimes H_{\alpha_k} \overset{\zeta^{\otimes k}}{\rightarrow} k. \ \ \ \ \ (19)$

For example, ${\Delta^2(h) =\Delta (\Delta h) = \Delta \sum h_i \otimes h_j = \sum \Delta h_i \otimes h_j + h_i \otimes \Delta h_j}$.

Example: Let ${\mathcal{G}}$ be the vector space with basis being the isomorphism classes of graphs. For two graphs ${G_1}$ and ${G_2}$ we can define the product of the basis elements they represent by the disjoint union. Then we can define

$\displaystyle \Delta(G) = \sum_{S \subseteq V(G)} G_S \otimes G_{V(G) \setminus S} \ \ \ \ \ (20)$

where ${G_S}$ denotes the induced subgraph on ${S}$ from ${G}$.

Theorem 8 The above defines a co-commutative Hopf algebra, with ${\zeta(G) = 1}$ if ${G}$ is a discrete, i.e., has no edges, and ${0}$ otherwise.

Theorem 9 For cocommutative combinatorial Hopf algebras, there is a unique morphism ${\psi: H \rightarrow \Lambda}$ given by the same formula as before.

For the graph algebra described above, ${\psi(G)}$ 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 ${K_n}$ the complete graph on ${n}$ vertices in the set of all colorings of ${K_n}$ with ${c}$ colors? The answer is of course ${\frac{c(c-1) \ldots (c-n+1)}{c^n}}$.
More general, given a graph ${G}$, let ${\chi_G(c)}$ be the number of proper colorings of ${G}$ with ${c}$ 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 ${x_i}$ is the probability that color ${i}$ is chosen, ${\sum x_i = 1}$. Then it is easy to see

$\displaystyle p_{K_n}(x_1, \ldots, x_c) = e_n(x_1, \ldots, x_c) \ \ \ \ \ (21)$

where ${p_{K_n}}$ stands for the probability of having a proper coloring given the chance of each color ${i=1, \ldots, c}$, and ${e_n(x_1, \ldots, x_c) = \sum_{i_1 < \ldots < i_n} x_{i_1} \ldots x_{i_n}}$ denotes the ${n}$th elementary symmetric polynomial. For more general graph ${G}$, ${p_G}$ gives the Stanley chromatic polynomial.