The work of Aguiar and Ardila (https://arxiv.org/abs/1709.07504) on Hopf monoids for generalized permutohedra gives a Hopf monoid structure on the collection of hypergraphs; see sections 19 and 20 of that paper. (Apparently there is also a different Hopf structure on hypergraphs considered by Benedetti and Bergeron (https://arxiv.org/abs/1611.01657) and Benedetti, Bergeron, and Machacek (https://arxiv.org/abs/1712.08848), although I do not fully understand how the two structures differ. I would be interested in an answer to my question for either Hopf structure.)

There is an important duality of hypergraphs, considered for instance by Postnikov (https://arxiv.org/abs/math/0507163) in the context of generalized permutohedra, that can be described as follows. We first interpret our hypergraph as a bipartite graph, with the left part representing edges, the right part representing vertices, and a graph edge representing containment. Then we reverse the roles of the left and right parts of our bipartite graph, and biject back to a hypergraph.

Does this duality have a nice interpretation in terms of the Hopf monoid structure?

EDIT: a recent paper posted to the arxiv (https://arxiv.org/abs/1812.09770v1) explains a Hopf algebraic meaning for the integer points of the hypergraph polytope, which might be a starting point for understanding the duality I’m talking about above in Hopf algebra terms.

  • $\begingroup$ This question is difficult to answer at the level of combinatorial species. A hypergraph h is an element of H[V], the vector space indexed by the vertex set of the hypergraph. It's dual lies in H[E], indexed by the edge set. Most operations for Hopf monoids involve decompositions of V, by working with the Cauchy product. Thus I do not see how to make duality into a morphism of species. This is similar to why graphs are not a submonoid of matroids: the graphic matroid is defined on the edges, so the map sending a graph to its matroid is not a morphism of species. $\endgroup$ – Jacob White Sep 14 '18 at 3:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.