An official website of the United States government
Abstract The goal of this paper is to show that valuation theory and Hopf theory are compatible on the class of generalized permutahedra. We prove that the Hopf structure $$\textbf {GP}^+$$ on these polyhedra descends, modulo the inclusion-exclusion relations, to an indicator Hopf monoid $$\mathbb {I}(\textbf {GP}^+)$$ of generalized permutahedra that is isomorphic to the Hopf monoid of weighted ordered set partitions. This quotient Hopf monoid $$\mathbb {I}(\textbf {GP}^+)$$ is cofree. It is the terminal object in the category of Hopf monoids with polynomial characters; this partially explains the ubiquity of generalized permutahedra in the theory of Hopf monoids. This Hopf theoretic framework offers a simple, unified explanation for many new and old valuations on generalized permutahedra and their subfamilies. Examples include, for matroids: the Chern–Schwartz–MacPherson cycles, Eur’s volume polynomial, the Kazhdan–Lusztig polynomial, the motivic zeta function, and the Derksen–Fink invariant; for posets: the order polynomial, Poincaré polynomial, and poset Tutte polynomial; for generalized permutahedra: the universal Tutte character and the corresponding class in the Chow ring of the permutahedral variety. We obtain several algebraic and combinatorial corollaries; for example, the existence of the valuative character group of $$\textbf {GP}^+$$ and the indecomposability of a nestohedron into smaller nestohedra.
more »
« less
Hopf Monoids and Generalized Permutahedra
Generalized permutahedra are polytopes that arise in combinatorics, algebraic geometry, representation theory, topology, and optimization. They possess a rich combinatorial structure. Out of this structure we build a Hopf monoid in the category of species. Species provide a unifying framework for organizing families of combinatorial objects. Many species carry a Hopf monoid structure and are related to generalized permutahedra by means of morphisms of Hopf monoids. This includes the species of graphs, matroids, posets, set partitions, linear graphs, hypergraphs, simplicial complexes, and building sets, among others. We employ this algebraic structure to define and study polynomial invariants of the various combinatorial structures. We pay special attention to the antipode of each Hopf monoid. This map is central to the structure of a Hopf monoid, and it interacts well with its characters and polynomial invariants. It also carries information on the values of the invariants on negative integers. For our Hopf monoid of generalized permutahedra, we show that the antipode maps each polytope to the alternating sum of its faces. This fact has numerous combinatorial consequences. We highlight some main applications: We obtain uniform proofs of numerous old and new results about the Hopf algebraic and combinatorial structures of these families. In particular, we give optimal formulas for the antipode of graphs, posets, matroids, hypergraphs, and building sets. They are optimal in the sense that they provide explicit descriptions for the integers entering in the expansion of the antipode, after all coefficients have been collected and all cancellations have been taken into account. We show that reciprocity theorems of Stanley and Billera–Jia–Reiner (BJR) on chromatic polynomials of graphs, order polynomials of posets, and BJR-polynomials of matroids are instances of one such result for generalized permutahedra. We explain why the formulas for the multiplicative and compositional inverses of power series are governed by the face structure of permutahedra and associahedra, respectively, providing an answer to a question of Loday. We answer a question of Humpert and Martin on certain invariants of graphs and another of Rota on a certain class of submodular functions. We hope our work serves as a quick introduction to the theory of Hopf monoids in species, particularly to the reader interested in combinatorial applications. It may be supplemented with Marcelo Aguiar and Swapneel Mahajan’s 2010 and 2013 works, which provide longer accounts with a more algebraic focus.
more »
« less
- PAR ID:
- 10479588
- Publisher / Repository:
- American Mathematical Society
- Date Published:
- Journal Name:
- Memoirs of the American Mathematical Society
- Volume:
- 289
- Issue:
- 1437
- ISSN:
- 0065-9266
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Inspired by methods in prime characteristic in commutative algebra, we introduce and study combinatorial invariants of seminormal monoids. We relate such numbers with the singularities and homological invariants of the semigroup ring associated to the monoid. Our results are characteristic independent.more » « less
-
Abstract In this paper, we investigate the degree of h-polynomials of edge ideals of finite simple graphs. In particular, we provide combinatorial formulas for the degree of the h-polynomial for various fundamental classes of graphs such as paths, cycles, and bipartite graphs. To the best of our knowledge, this study represents the first investigation into the combinatorial interpretation of this algebraic invariant. Additionally, we characterize all connected graphs in which the sum of the Castelnuovo–Mumford regularity and the degree of theh-polynomial of an edge ideal achieve its maximum value, equal to the number of vertices in the graph.more » « less
-
Ferroni and Larson gave a combinatorial interpretation of the braid Kazhdan-Lusztig polynomials in terms of series-parallel matroids. As a consequence, they confirmed an explicit formula for the leading Kazhdan-Lusztig coefficients of braid matroids with odd rank, as conjectured by Elias, Proudfoot, and Wakefield. Based on Ferroni and Larson’s work, we further explore the combinatorics behind the leading Kazhdan-Lusztig coefficients of braid matroids. The main results of this paper include an explicit formula for the leading Kazhdan-Lusztig coefficients of braid matroids with even rank, a simple expression for the number of simple series-parallel matroids of rank $k + 1$ on $2k$ elements, and explicit formulas for the leading coefficients of inverse Kazhdan-Lusztig polynomials of braid matroids. The binomial identity for the Abel polynomials plays an important role in the proofs of these formulas.more » « less
-
Ćirić, M.; Droste, M.; Pin, JÉ. (Ed.)We initiate an algebraic approach to study DNA origami structures. We identify two types of basic building blocks and describe a DNA origami structure by their composition. These building blocks are taken as generators of a monoid, called the origami monoid, and motivated by the well studied Temperley-Lieb algebras, we identify a set of relations that characterize the origami monoid. We present several observations about Green’s relations for the origami monoid and study the relations to a direct product of Jones monoids, which is a morphic image of an origami monoid.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1090/memo/1437
