Hopf Monoids and Generalized Permutahedra
Hopf Monoids and Generalized Permutahedra
复制标题
DOI：
10.1090/memo/1437
复制
发表时间：
2017-09
影响因子：
1.9
通讯作者：
M. Aguiar;Federico Ardila
中科院分区：
文献类型：
--
作者：
M. Aguiar;Federico Ardila
广义置换面体是出现在组合学、代数几何、表示论、拓扑和优化中的多面体。它们具有丰富的组合结构。根据这个结构，我们在物种范畴中构建了一个 Hopf 幺半群。物种为组织组合对象家族提供了一个统一的框架。许多物种都带有 Hopf 幺半群结构，并通过 Hopf 幺半群的态射与广义置换面体相关。这包括图、拟阵、偏序集、集合划分、线性图、超图、单纯复形和构建集等。我们利用这种代数结构来定义和研究各种组合结构的多项式不变量。我们特别关注每个 Hopf 幺半群的对映体。该映射是 Hopf 幺半群结构的核心，并且与其特征和多项式不变量相互作用良好。它还携带有关负整数不变量值的信息。对于广义置换面体的 Hopf 幺半群，我们证明对映体将每个多面体映射到其面的交替和。这一事实会产生许多组合后果。我们重点介绍一些主要应用：我们获得了有关这些族的 Hopf 代数和组合结构的大量新旧结果的统一证明。特别是，我们给出了图、偏序集、拟阵、超图和构建集的对映体的最佳公式。它们是最优的，因为它们在收集了所有系数并考虑了所有消去之后，为进入对映点展开的整数提供了明确的描述。我们证明了 Stanley 和 Billera–Jia–Reiner (BJR) 关于图色多项式、偏序集阶多项式和拟阵 BJR 多项式的互反定理是广义置换面体的此类结果的实例。我们解释了为什么幂级数的乘法和组合逆元的公式分别受排列面体和联合面体的面结构控制，为洛迪问题提供了答案。我们回答了 Humpert 和 Martin 关于图的某些不变量的问题以及 Rota 关于某类子模函数的问题。我们希望我们的工作能够快速介绍物种中的 Hopf 幺半群理论，特别是对组合应用感兴趣的读者。 Marcelo Aguiar 和 Swapneel Mahajan 2010 年和 2013 年的作品可能会对其进行补充，这些作品提供了更长的叙述，并且更加关注代数。
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.