# Hopf algebra of graphs

Let $B$ be the set of isomorphism classes of finite graphs. Let $V$ be the $k$-vector space freely generated by $B$. I have heard that $V$ carries the structure of a Hopf algebra, and would like to understand the details.

The multiplication is defined by linear extension of the disjoint union of graphs. The unit is the empty graph. The comultiplication sends a graph $G$ to the sum $\sum_{S \subseteq V(G)} G|_S \otimes G|_{V(G) \setminus S}$, running over all subsets of vertices of $G$. The counit maps the empty graph to $1$, and all other graphs to $0$. I have checked that we get a commutative cocommutative bialgebra.

Question. How to define the antipode?

Although the antipode $S$ of a Hopf algebra is unique, I cannot come up with it. I am pretty sure that the antipode maps a graph to an alternating sum of graphs. Only then $V \to V \otimes V \xrightarrow{S \otimes V} V \otimes V \to V$ can cancel to $V \to k \to V$.

• Interesting, very interesting indeed! – baharampuri Jul 24 '15 at 7:29
• dmtcs.org/pdfpapers/dmAO0146.pdf this might be of interest. This article gives a formula for the antipode in a special case, for the general you may see : google.co.in/… – baharampuri Jul 24 '15 at 7:31
• Thank you. It contains the answer on page 519. So feel free to make this an answer. – Martin Brandenburg Jul 24 '15 at 7:33

For the incidence Hopf algebras arising out of graphs the author in the article http://www.dmtcs.org/pdfpapers/dmAO0146.pdf gives a formula. For general incidence Hopf algebras one can look at http://home.gwu.edu/~wschmitt/papers/iha.pdf for the antipode formula.

• So the formula is: If $G$ is a graph, then $S(G)=\sum_{\pi} (-1)^{|\pi|} |\pi|! G_{\pi}$, where the sum runs over all ordered partitions $\pi$ of $V(G)$ into nonempty sets, and $G_{\pi}$ is the disjoint union of the induced subgraphs. – Martin Brandenburg Jul 24 '15 at 8:24