Combinatorial Hopf Algebras

Recent developments have linked heretofore distinct subjects within combinatorics, algebra, geometry, and theoretical physics thereby uncovering exciting new avenues for research. Our workshop would bring together experts in these newly linked subjects, many of whom have not previously interacted, to focus attention on these topics. We expect to follow a leisurely pace at the workshop, reserving time for consultation among the participants. The talks would concentrate on new developments and open problems, serving to define this area and its future directions.

An old theme in algebraic combinatorics initiated by Rota is that many combinatorial objects possess natural product and coproduct structures. Enumeration and classification of these structures often give rise to an associated graded Hopf algebra. This theme has matured with recent work of Ehrenborg, Aguiar, and others, who give a natural Hopf morphism from these Hopf algebras of combinatorial objects to the Hopf algebra of quasi-symmetric functions Qsym. This morphism arises from a universal property of the Hopf algebra Qsym as a terminal object in the category of graded Hopf algebras equipped with a zeta-function. In particular, many enumerative combinatorial invariants (among them flag f-vectors, Littlewood-Richardson coefficients, and chromatic symmetric polynomials) are obtained from this universal property. In light of this, the Hopf algebra Qsym and its sub-structures are bound to play a very important role in algebraic combinatorics.

The Hopf algebra Qsym of quasi-symmetric functions was introduced by Gessel as a source of generating functions for Stanley's P-partitions. Since then, quasi-symmetric functions have appeared in many combinatorial contexts. For example, Gessel showed that multiplication in Qsymm is given by a shuffle product, giving showing that the descent sets of all shuffles of two sequences depends only on the decent sets of the sequences being shuffled. The relation of Qsym to the ring of symmetric functions was first clarified by Malvenuto and Reutenauer via graded Hopf duality to the Solomon descent algebras, and then Gelfand, et al., defined the graded Hopf algebra NC of non- commutative symmetric functions and identified it with the Solomon descent algebra. Recently, there is a growing interest in symmetric and quasi- symmetric functions and their non-commutative analogs.

The dual pair NC and Qsym of Hopf algebras are only the first of a growing number of combinatorial Hopf algebras which possess interesting structures and are related to NC and Qsym. For example, Malvenuto and Reutenauer studied a non-commutative graded Hopf algebra whose basis is all permutations having a natural map to Qsym, and which contains NC as a subalgebra. This map factors through a Hopf algebra of planar binary trees studied by Loday and Ronco, and others. Loday and Ronco discovered the notion of dendriform algebra studying this Hopf algebra. Other combinatorial Hopf algebras possess interesting operadic structures, some of which have been elucidated by Loday and Chapoton. Brouder and Frabetti studied a related (actually isomorphic) Hopf algebra of planar binary trees, linking it to renormalization of Quantum Electrodynamics. This is similar to, but different from, the Hopf algebra of rooted trees of Connes and Kreimer which encodes some renormalization in Quantum Field Theory. Relations between these algebras have yet to be fully studied, and we believe that special structures of these algebras will have relevance to the original combinatorics we began with.

To give one important example, the connections uncovered by the work of Aguiar suggest a number of exciting possibilities. This includes a unified approach to positivity questions in different realms of enumerative combinatorics or using these results as a bridge to transfer ideas and techniques between these heretofore different realms. For example, both the Schubert calculus and polytope/poset theory have important open positivity questions and well-developed techniques to study these (Schensted insertion and geometry/representation theory for the Schubert calculus and shelling/homology of posets for polytopes and posets). It would be very fruitful to connect these techniques or to apply them to other areas.

For example, Billera and Liu considered elements of the algebra NC as flag- enumeration functionals on all graded posets, and they defined a quotient E of NC consisting of all such functionals on Eulerian posets. Bergeron, Mykytiuk, Sottile and van Willigenburg showed that the algebra E is dual to Stembridge's algebra Pi of peak quasi-symmetric functions. More precisely, they showed that both algebras have natural coproducts that make them into Hopf algebras, and that these Hopf algebras are, in fact, dual. This duality links the study of the enumerative properties of Eulerian posets, including associated geometric objects such as spheres, convex polytopes and hyperplane arrangements, with that of Stembridge's enriched P-partitions and related questions having to do with peaks and shuffles in permutations. More recently, Billera, Hsiao, and van Willigenburg showed a direct connection between the cd-index for Eulerian posets and the standard basis for the algebra Pi, giving a direct link between natural non-negativity questions in each field. This line of study also shows an interesting connection between the map relating "descents" to "peaks" and the classical theory of Zaslavsky relating enumeration in geometric lattices to that of the regions in an associated arrangement of hyperplanes. This is yet to be completely understood. They also showed this map to define a random walk on the collection of all peak sets whose stationary distribution is the distribution of peak sets in the symmetric group. This is a direct outgrowth of a shuffle interpretation for multiplication in Pi.

Another exciting line of study is the investigation of Qsym (in finitely many variables) considered as a subalgebra of the polynomial algebra. In recent work, Aval and Bergeron and Bergeron have shown that the quotient of the polynomial ring over the ideal generated by Qsym is linked to Catalan numbers. This new investigation promises a wealth of research as it is related to the analogous quotients in invariant theory involving symmetric polynomials. The later are intensively studied in geometry and representation theory as they encode cohomology of various (partial) flag manifolds. Its generalization leads to the famous n!-conjecture of Garsia and Haiman, in relation to the positivity conjecture of the Macdonald symmetric functions. Haiman recently proved these conjectures. It would be extremely stimulating to construct an analogous theory for the quasi-symmetric functions.

Because the work connecting these areas is quite recent, its implications for future research have only just begun to be disseminated within the research community. Our workshop would foster deeper connections and enable future collaborations between researchers in these various areas.

Confirmed Participants

Programme (pdf file)