The Hopf monoid and the basic invariant of directed graphs

MaRDI QIDQ2231245zbMATH OpenFDO

Authors Keiju Kato

Publication date 29 September 2021

Published in Osaka Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1907.10825, http://projecteuclid.org/ojm/5136

zbMATH Keywords

directed cutsHopf monoid of generalized permutahedra

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20) Flows in graphs (05C21) Graph polynomials (05C31) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05)

Abstract: Aguiar and Ardila defined the Hopf monoid GP of generalized permutahedra and showed that it contains many submonoids that correspond to combinatorial objects. They also give a basic polynomial invariant of generalized permutahedra, which then specializes to the submonoids. We define the Hopf monoid of directed graphs and show that it also embeds in GP. The resulting basic invariant coincides with the strict chromatic polynomial of Awan and Bernardi.

Recommendations

• The Hopf monoid of hypergraphs and its sub-monoids: basic invariant and reciprocity theorem
• Polynomial invariants and reciprocity theorems for the Hopf monoid of hypergraphs and its sub-monoids
• The Hopf monoid of orbit polytopes
• The Hopf monoid of orbit polytopes
• Hopf algebra methods in graph theory

Cites work

• A quasisymmetric function for matroids
• Acyclic orientations of graphs
• Coalgebras and bialgebras in combinatorics
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Combinatorics and commutative algebra
• Computing the Continuous Discretely
• Hopf Algebras of Combinatorial Structures
• Hopf Monoids and Generalized Permutahedra
• scientific article; zbMATH DE number 1111371 (Why is no real title available?)
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• Monoidal functors, species and Hopf algebras
• Ordered structures and partitions
• Permutohedra, Associahedra, and Beyond
• Submodular functions and optimization.
• Tutte polynomials for directed graphs
• Une théorie combinatoire des séries formelles

Cited in

(7)

• The Hopf monoid of hypergraphs and its sub-monoids: basic invariant and reciprocity theorem
• Polynomial invariants and reciprocity theorems for the Hopf monoid of hypergraphs and its sub-monoids
• Normal form in Hecke-Kiselman monoids associated with simple oriented graphs
• Valuations and the Hopf Monoid of Generalized Permutahedra
• The Hopf monoid of orbit polytopes
• Hopf Monoids and Generalized Permutahedra
• A strong geometric hyperbolicity property for directed graphs and monoids.

This page was built for publication: The Hopf monoid and the basic invariant of directed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2231245)