The Hopf monoid and the basic invariant of directed graphs. (English) Zbl 1473.05110
Summary: M. Aguiar and F. Ardila [“Hopf monoids and generalized permutahedra”, Preprint, arXiv:1709.07504] 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 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 J. Awan and O. Bernardi [J. Comb. Theory, Ser. B 140, 192–247 (2020; Zbl 1430.05057)].
MSC:
| 05C20 | Directed graphs (digraphs), tournaments |
| 05C15 | Coloring of graphs and hypergraphs |
| 05C31 | Graph polynomials |
| 05C21 | Flows in graphs |
| 52B05 | Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) |
Citations:
Zbl 1430.05057References:
| [1] | M. Aguiar and F. Ardila: Hopf monoids and generalized permutahedra, arXiv:1709.07504. · Zbl 07753149 |
| [2] | M. Aguiar and S. Mahajan: Monoidal functors, species and Hopf algebras, American Mathematical Society, Providence, R.I., New York, 2010. · Zbl 1209.18002 |
| [3] | J. Awan and O. Bernardi: Tutte polynomials for directed graphs, J. Combin. Theory, Seri. B 140 (2019), 192-247. · Zbl 1430.05057 |
| [4] | M. Beck and S. Robins: Computing the Continuous Discretely, Springer, New York, 2015. · Zbl 1339.52002 |
| [5] | F. Bergeron, G. Labelle, and P. Leroux: Combinatorial species and tree-like structures, Cambridge University Press, Cambridge, 1998. · Zbl 0888.05001 |
| [6] | L.J. Billera, N. Jia, and V. Reiner: A quasisymmetric function for matroids, European J. Combin. 30 (2009), 1727-1757. · Zbl 1179.05025 |
| [7] | J. Edmonds: Submodular functions, matroids, and certain polyhedral; in Combinatorial Structures and their Applications (Proc. Calgary Internat. Conf., Calgary, Alta., 1969), Gordon and Breach, New York, 1970, 69-87. · Zbl 0268.05019 |
| [8] | S. Fujishige: Submodular functions and optimization, second edition, Annals of Discrete Mathematics 58, Elsevier B. V., Amsterdam, 2005. · Zbl 1119.90044 |
| [9] | S.A. Joni and G.C. Rota: Coalgebras and bialgebras in combinatorics; in Umbral Calculus and Hopf Algebras (Norman, OKla, 1978), Contemporary Mathematics 6, Amer. Math. Soci., Providence, R.I., 1982, 1-47. · Zbl 0491.05021 |
| [10] | A. Joyal: Une théorie combinatoire des séries formelles, Adva. Math. 42 (1981), 1-82. · Zbl 0491.05007 |
| [11] | A. Postnikov: Permutohedra, Associahedra, and Beyond, Int. Math. Re. Not. IMRN (2009), 1026-1106. · Zbl 1162.52007 |
| [12] | W.R. Schmitt: Hopf algebras of combinatorial structures, Canad. J. Math. 45 (1993), 412-428. · Zbl 0781.16026 |
| [13] | A. Schrijver: Combinatorial optimization: polyhedra and efficiency, Springer-Verlag, Berlin Heidelberg, 2003. · Zbl 1041.90001 |
| [14] | P.R. Stanley: Ordered structures and partitions, Memoirs of American Mathematical Society, no. 119, American Mathematical Society, Providence, New York, 1972. · Zbl 0246.05007 |
| [15] | P.R. Stanley: Acyclic orientations of graphs, Discrete Math. 5 (1973), 171-178. · Zbl 0258.05113 |
| [16] | R.P. Stanley: Combinatorics and commutative algebra, Progress in Mathematics 41, Springer, New York, 2007. · Zbl 1157.13302 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
