The incidence Hopf algebra of graphs. (Q2910935)

\(G=G_{(V,E)}\) will denote a finite undirected graph with vertex set \(V=V(G)\) and edge set \(E=E(G)\). Isomorphism classes of such \(G\) are basis elements of the graph algebra \(\mathcal G\). This is a graded connected Hopf algebra with multiplication given by disjoint union, and comultiplication of \(G\) given by the sum of all \(T\otimes T\), where \(T\) ranges over all subsets of \(V(G)\). As such, the antipode \(S\) of \(\mathcal G\) can be described recursively. \textit{W. R. Schmitt} gave such a description of \(S\) [J. Pure Appl. Algebra 96, No. 3, 299-330 (1994; Zbl 0808.05101)].NEWLINENEWLINE In the paper under review, the authors give a non-recursive formula in terms of acyclic orientations, i.e., choices of orientations of the edges which admit no directed cycles. A set \(F\) of edges is called a flat if whenever the endpoints of an edge \(e\) are connected by a path in \(F\), then \(e\) is in \(F\). The rank of a set of edges is the size of a maximal acyclic subset. The authors' formula is that \(S(G)\) is the sum over all flats \(F\) in \(G\) of \((-1)^{(|V|-\text{rank\,}F)}|\text{all acyclic orientations of }G/F|G_{(V,F)}\), where \(G/F\) is the graph obtained by successively contracting every edge of \(F\), i.e., identifying two endpoints, and then removing the edge. Some applications are given, one of which involves the Tutte polynomial \((T_G)(x,y)\), which is the sum over all subsets \(A\) of \(E\) of \((x-1)^{(\text{rank\,}G-\text{rank\,}A)}(y-1)^{(\text{null\,}A)}\), where \(\text{null\,}A=|A|-\text{rank\,}A\).