Volume 45_4_(2024)_293-318

The Fortuin-Kasteleyn polynomial as a bialgebra morphism and applications to the Tutte polynomial
Loïc Foissy, Claudia Malvenuto

Abstract. We compute an explicit formula for the antipode of the double bialgebra of graphs in terms of totally acyclic partial orientations, using some general results on double bialgebras. In analogy to what was already proven in Hopf-algebraic terms for the chromatic polynomial of a graph, we show that the Fortuin-Kasteleyn polynomial (a variant of the Tutte polynomial) is a morphism of the double algebra of graphs into that of polynomials, which generalizes the chromatic polynomial. When specialized at particular values, we give combinatorial interpretations of the Tutte polynomial of a graph, via covering graphs and covering forests, and of the Fortuin-Kasteleyn polynomial, via pairs of vertex-edge colorings. Finally we show that the map associating to a graph all its orientations is a Hopf morphism from the double bialgebra of graphs into the one of oriented graphs, allowing to give interpretations of the Fortuin-Kasteleyn polynomial when computed at negative values

Rend. Mat. Appl. (7) 45 (2024) 293-318;  pdf