The Redei–Berge Hopf algebra of digraphs

Abstract

In a series of recent talks Richard Stanley introduced a symmetric function associated to digraphs, called the Redei–Berge symmetric function. This symmetric function enumerates descent sets of permutations corresponding to digraphs. We show that such constructed symmetric function arises from a suitable structure of combinatorial Hopf algebra on digraphs. The induced Redei–Berge polynomial satisfies the deletion-contraction property which makes it similar to the chromatic polynomial. The Berge’s classical result on the number of Hamiltonian paths in digraphs is a consequence of the reciprocity formula for the Redei–Berge polynomial.