Hopf algebra methods in graph theory
type: Item
instance of: scholarly article
title: Hopf algebra methods in graph theory
zbMATH Open document ID: 0833.16035
DOI: 10.1016/0022-4049(95)90925-B
author: William R. Schmitt
published in: Journal of Pure and Applied Algebra
publication date: 1996-01-23T00:00:00Z
review text: 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 monoi…
reviewed by: Claudia Malvenuto
Mathematics Subject Classification ID: 16W30
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05B35
Mathematics Subject Classification ID: 16S36
Mathematics Subject Classification ID: 57T05
zbMATH DE Number: 797259
zbMATH Keywords: invariants of Whitney systems
zbMATH Keywords: coproducts
zbMATH Keywords: antipodes
zbMATH Keywords: continuous duals
zbMATH Keywords: polynomial Hopf algebras
zbMATH Keywords: monoid algebras
zbMATH Keywords: bialgebras
zbMATH Keywords: chromatic polynomials
MaRDI profile type: Publication
cites work: Q3912821
cites work: ON CLUSTER EXPANSIONS IN GRAPH THEORY AND PHYSICS
cites work: Q4154891
cites work: Q3912837
cites work: Q3901604
cites work: On the foundations of combinatorial theory I. Theory of M�bius Functions
cites work: Antipodes and incidence coalgebras
cites work: Q5590089
cites work: On dichromatic polynomials
description: scientific article; zbMATH DE number 797259