Hopf algebra methods in graph theory (Q1898416): Difference between revisions

The author studies, in a Hopf algebraic context, the invariants of Whitney systems, a wide category of combinatorial objects which generalize graphs and matroids. Let \(\mathcal P\) be a family of isomorphism types of Whitney systems, closed under formation of restrictions and sums. On \(\mathcal P\) one can define a product as the disjoint union of types. Let \({\mathcal C} ({\mathcal P})\) denote the monoid algebra of \(\mathcal P\) over any field \(K\) of characteristic 0. The author defines then a coproduct \(\Delta\) in the following way. Let \([H]\in{\mathcal P}\), denote the \(S(H)\) the support of the Whitney system \(H\) and by \([H|U]\) the type of the restriction \(H|U\) of \(H\) to a subset \(U\) of \(S(H)\). Then \(\Delta[H]=\sum[H|U_1]\otimes [H|U_2]\), where the sum runs over all ordered pairs of not necessarily disjoint sets \(U_1\) and \(U_2\) whose union is equal to \(S(H)\). \({\mathcal C}(\mathcal P)\) with respect to the above product and coproduct is a Hopf algebra. The author extends this structure to the completion of \({\mathcal C}({\mathcal P})\) and gives an explicit formula for the antipode. He proves then that the continuous dual \({\mathcal C}({\mathcal P})'\) of such a Hopf algebra is isomorphic to the polynomial Hopf algebra \(K [{\mathcal P}_0]\) in the primitive indeterminates \({\mathcal P}_0\), where \({\mathcal P}_0\) is the subset of the connected types of \(\mathcal P\). This approach explains the results of \textit{H. Whitney} [Ann. Math., II. Ser. 33, 688-718 (1932; Zbl 0005.31301)], in which he showed that any graph invariant which counts subgraphs of a particular isomorphism type can be expressed as a unique polynomial, with rational coefficients, in the invariants which count doubly connected subgraphs, and these latter invariants are algebraically independent over the rationals. Another coproduct \(\delta\) is defined on the monoid algebra of \(\mathcal P\) by \(\delta [H]=[H ]\otimes [H]\). With this coproduct, the monoid algebra is a bialgebra, denoted by \(M({\mathcal P})\). It is shown that the subalgebra \(M({\mathcal P})'\) of the full dual \(M({\mathcal P})^*\), generated by the restriction invariants, is isomorphic to \({\mathcal C} ({\mathcal P})'\). A transformation between the class of restriction invariants and the set of additive invariants is defined via the log map. A special case of this transformation is found in the mentioned work of Whitney: he introduced an invertible transformation from a set of graph invariants which determine the chromatic polynomial and satisfy a kind of multiplicative property, to a set of invariants which are additive, and also determine the chromatic polynomial. The same techniques could apply successfully to other combinatorial structures.