Hopf Monoids and Generalized Permutahedra

DOI10.1090/MEMO/1437MaRDI QIDQ6051923zbMATH OpenFDO

Publication date 23 October 2023

Published in Memoirs of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1709.07504

Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Exact enumeration problems, generating functions (05A15) Combinatorial aspects of matroids and geometric lattices (05B35) Coloring of graphs and hypergraphs (05C15) Graph polynomials (05C31) Research exposition (monographs, survey articles) pertaining to associative rings and algebras (16-02) Connections of Hopf algebras with combinatorics (16T30) Species, Hopf monoids, operads in combinatorics (18M80) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40)

Abstract: Generalized permutahedra are a family of polytopes with a rich combinatorial structure and strong connections to optimization. We prove that they are the universal family of polyhedra with a certain Hopf algebraic structure. Their antipode is remarkably simple: the antipode of a polytope is the alternating sum of its faces. Our construction provides a unifying framework to organize numerous combinatorial structures, including graphs, matroids, posets, set partitions, linear graphs, hypergraphs, simplicial complexes, building sets, and simple graphs. We highlight three applications: 1. We obtain uniform proofs of numerous old and new results about the Hopf algebraic and combinatorial structures of these families. In particular, we give the optimal formula for the antipode of graphs, posets, matroids, hypergraphs, and building sets, and we answer questions of Humpert--Martin and Rota. 2. We show that the reciprocity theorems of Stanley and Billera--Jia--Reiner on chromatic polynomials of graphs, order polynomials of posets, and BJR-polynomials of matroids are instances of the same reciprocity theorem for generalized permutahedra. 3. 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, answering a question of Loday. Along the way, we offer a combinatorial user's guide to Hopf monoids.

Recommendations

Cites work

Cited in

(46)

This page was built for publication: Hopf Monoids and Generalized Permutahedra

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