AMS eBook CollectionsOne of the world's most respected mathematical collections, available in digital format for your library or institution
Hopf Monoids and Generalized Permutahedra
About this Title
Marcelo Aguiar and Federico Ardila
Publication: Memoirs of the American Mathematical Society
Publication Year:
2023; Volume 289, Number 1437
ISBNs: 978-1-4704-6708-1 (print); 978-1-4704-7592-5 (online)
DOI: https://doi.org/10.1090/memo/1437
Published electronically: August 24, 2023
Table of Contents
Chapters
- Introduction
- 1. The Hopf monoid of generalized permutahedra
- 2. Permutahedra, associahedra, and inversion
- 3. Submodular functions, graphs, matroids, and posets
- 4. Characters, polynomial invariants, and reciprocity
- 5. Hypergraphs, simplicial complexes, and building sets
Abstract
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:
- Marcelo Aguiar, Nantel Bergeron, and Frank Sottile, Combinatorial Hopf algebras and generalized Dehn-Sommerville relations, Compos. Math. 142 (2006), no. 1, 1–30. MR 2196760, DOI 10.1112/S0010437X0500165X
- Marcelo Aguiar and Swapneel Mahajan, Monoidal functors, species and Hopf algebras, CRM Monograph Series, vol. 29, American Mathematical Society, Providence, RI, 2010. With forewords by Kenneth Brown and Stephen Chase and André Joyal. MR 2724388, DOI 10.1090/crmm/029
- Marcelo Aguiar and Swapneel Mahajan, Hopf monoids in the category of species, Hopf algebras and tensor categories, Contemp. Math., vol. 585, Amer. Math. Soc., Providence, RI, 2013, pp. 17–124. MR 3077234, DOI 10.1090/conm/585/11665
- Marcelo Aguiar and Swapneel Mahajan, Topics in hyperplane arrangements, Mathematical Surveys and Monographs, vol. 226, American Mathematical Society, Providence, RI, 2017. MR 3726871, DOI 10.1090/surv/226
- M. Aguiar and S. Mahajan, Bimonoids for hyperplane arrangements, Encyclopedia of Mathematics and its Applications, vol. 173, Cambridge University Press, 2020.
- Federico Ardila, Algebraic and geometric methods in enumerative combinatorics, Handbook of enumerative combinatorics, Discrete Math. Appl. (Boca Raton), CRC Press, Boca Raton, FL, 2015, pp. 3–172. MR 3409342
- Federico Ardila, Carolina Benedetti, and Jeffrey Doker, Matroid polytopes and their volumes, Discrete Comput. Geom. 43 (2010), no. 4, 841–854. MR 2610473, DOI 10.1007/s00454-009-9232-9
- Federico Ardila, Federico Castillo, Christopher Eur, and Alexander Postnikov, Coxeter submodular functions and deformations of Coxeter permutahedra, Adv. Math. 365 (2020), 107039, 36. MR 4064768, DOI 10.1016/j.aim.2020.107039
- Federico Ardila, Caroline Klivans, and Lauren Williams, The positive Bergman complex of an oriented matroid, European J. Combin. 27 (2006), no. 4, 577–591. MR 2215218, DOI 10.1016/j.ejc.2004.12.006
- Federico Ardila and Caroline J. Klivans, The Bergman complex of a matroid and phylogenetic trees, J. Combin. Theory Ser. B 96 (2006), no. 1, 38–49. MR 2185977, DOI 10.1016/j.jctb.2005.06.004
- Federico Ardila, Victor Reiner, and Lauren Williams, Bergman complexes, Coxeter arrangements, and graph associahedra, Sém. Lothar. Combin. 54A (2005/07), Art. B54Aj, 25. MR 2317682
- F. Ardila and M. Sanchez, Valuations and the hopf monoid of generalized permutahedra, International Mathematics Research Notices (2023), 4149-4224.
- Jose Bastidas, The polytope algebra of generalized permutahedra, Algebr. Comb. 4 (2021), no. 5, 909–946. MR 4339357, DOI 10.5802/alco.185
- Carolina Benedetti, Joshua Hallam, and John Machacek, Combinatorial Hopf algebras of simplicial complexes, SIAM J. Discrete Math. 30 (2016), no. 3, 1737–1757. MR 3543152, DOI 10.1137/15M1038281
- F. Bergeron, G. Labelle, and P. Leroux, Combinatorial species and tree-like structures, Encyclopedia of Mathematics and its Applications, vol. 67, Cambridge University Press, Cambridge, 1998. Translated from the 1994 French original by Margaret Readdy; With a foreword by Gian-Carlo Rota. MR 1629341
- F. Bergeron, G. Labelle, and P. Leroux, Combinatorial species and tree-like structures, Encyclopedia of Mathematics and its Applications, vol. 67, Cambridge University Press, Cambridge, 1998. Translated from the 1994 French original by Margaret Readdy; With a foreword by Gian-Carlo Rota. MR 1629341
- Louis J. Billera, Ning Jia, and Victor Reiner, A quasisymmetric function for matroids, European J. Combin. 30 (2009), no. 8, 1727–1757. MR 2552658, DOI 10.1016/j.ejc.2008.12.007
- Anders Björner, Michel Las Vergnas, Bernd Sturmfels, Neil White, and Günter M. Ziegler, Oriented matroids, 2nd ed., Encyclopedia of Mathematics and its Applications, vol. 46, Cambridge University Press, Cambridge, 1999. MR 1744046, DOI 10.1017/CBO9780511586507
- Anders Björner, Michel Las Vergnas, Bernd Sturmfels, Neil White, and Günter M. Ziegler, Oriented matroids, Encyclopedia of Mathematics and its Applications, vol. 46, Cambridge University Press, Cambridge, 1993. MR 1226888
- Joseph E. Bonin and Anna de Mier, Lattice path matroids: structural properties, European J. Combin. 27 (2006), no. 5, 701–738. MR 2215428, DOI 10.1016/j.ejc.2005.01.008
- Alexandre V. Borovik, I. M. Gelfand, and Neil White, Coxeter matroids, Progress in Mathematics, vol. 216, Birkhäuser Boston, Inc., Boston, MA, 2003. MR 1989953, DOI 10.1007/978-1-4612-2066-4
- Alexandre V. Borovik, I. M. Gelfand, and Neil White, Coxeter matroids, Progress in Mathematics, vol. 216, Birkhäuser Boston, Inc., Boston, MA, 2003. MR 1989953, DOI 10.1007/978-1-4612-2066-4
- Felix Breuer and Caroline J. Klivans, Scheduling problems, J. Combin. Theory Ser. A 139 (2016), 59–79. MR 3436052, DOI 10.1016/j.jcta.2015.11.001
- E. Bucher, C. Eppolito, J. Jun, and J. P. Matherne, Matroid-minor hopf algebra: a cancellation-free antipode formula and other applications of sign-reversing involutions, 2018.
- E. Bucher and J. P. Matherne, A cancellation-free antipode formula (for uniform matroids) for the restriction-contraction matroid Hopf algebra, 2016.
- Michael P. Carr and Satyan L. Devadoss, Coxeter complexes and graph-associahedra, Topology Appl. 153 (2006), no. 12, 2155–2168. MR 2239078, DOI 10.1016/j.topol.2005.08.010
- Cesar Ceballos, Francisco Santos, and Günter M. Ziegler, Many non-equivalent realizations of the associahedron, Combinatorica 35 (2015), no. 5, 513–551. MR 3437894, DOI 10.1007/s00493-014-2959-9
- Cesar Ceballos, Francisco Santos, and Günter M. Ziegler, Many non-equivalent realizations of the associahedron, Combinatorica 35 (2015), no. 5, 513–551. MR 3437894, DOI 10.1007/s00493-014-2959-9
- Cesar Ceballos and Günter M. Ziegler, Realizing the associahedron: mysteries and questions, Associahedra, Tamari lattices and related structures, Progr. Math., vol. 299, Birkhäuser/Springer, Basel, 2012, pp. 119–127. MR 3221537, DOI 10.1007/978-3-0348-0405-9_{7}
- A. P. Dawid, Conditional independence in statistical theory, J. Roy. Statist. Soc. Ser. B 41 (1979), no. 1, 1–31. MR 535541
- C. De Concini and C. Procesi, Wonderful models of subspace arrangements, Selecta Math. (N.S.) 1 (1995), no. 3, 459–494. MR 1366622, DOI 10.1007/BF01589496
- Harm Derksen and Alex Fink, Valuative invariants for polymatroids, Adv. Math. 225 (2010), no. 4, 1840–1892. MR 2680193, DOI 10.1016/j.aim.2010.04.016
- Hans Dobbertin, About polytopes of valuations on finite distributive lattices, Order 2 (1985), no. 2, 193–198. MR 815864, DOI 10.1007/BF00334856
- Peter Doubilet, On the foundations of combinatorial theory. VII. Symmetric functions through the theory of distribution and occupancy, Studies in Appl. Math. 51 (1972), 377–396. MR 429577, DOI 10.1002/sapm1972514377
- Kurusch Ebrahimi-Fard and Frédéric Fauvet (eds.), Faà di Bruno Hopf algebras, Dyson-Schwinger equations, and Lie-Butcher series, IRMA Lectures in Mathematics and Theoretical Physics, vol. 21, European Mathematical Society (EMS), Zürich, 2015. Papers from the Workshop Dyson-Schwinger Equations and Faà di Bruno Hopf Algebras in Physics and Combinatorics (DSFdB2011) held at Strasbourg University, Strasbourg, June 27–July 1, 2011. MR 3380567, DOI 10.4171/143
- Jack Edmonds, Submodular functions, matroids, and certain polyhedra, Combinatorial Structures and their Applications (Proc. Calgary Internat. Conf., Calgary, Alta., 1969) Gordon and Breach, New York-London-Paris, 1970, pp. 69–87. MR 270945
- Eva-Maria Feichtner and Dmitry N. Kozlov, Incidence combinatorics of resolutions, Selecta Math. (N.S.) 10 (2004), no. 1, 37–60. MR 2061222, DOI 10.1007/s00029-004-0298-1
- Eva Maria Feichtner and Bernd Sturmfels, Matroid polytopes, nested sets and Bergman fans, Port. Math. (N.S.) 62 (2005), no. 4, 437–468. MR 2191630
- Héctor Figueroa and José M. Gracia-Bondía, Combinatorial Hopf algebras in quantum field theory. I, Rev. Math. Phys. 17 (2005), no. 8, 881–976. MR 2167639, DOI 10.1142/S0129055X05002467
- Sergey Fomin and Andrei Zelevinsky, $Y$-systems and generalized associahedra, Ann. of Math. (2) 158 (2003), no. 3, 977–1018. MR 2031858, DOI 10.4007/annals.2003.158.977
- Satoru Fujishige, Submodular functions and optimization, 2nd ed., Annals of Discrete Mathematics, vol. 58, Elsevier B. V., Amsterdam, 2005. MR 2171629
- William Fulton and Joe Harris, Representation theory, Graduate Texts in Mathematics, vol. 129, Springer-Verlag, New York, 1991. A first course; Readings in Mathematics. MR 1153249, DOI 10.1007/978-1-4612-0979-9
- Ladnor Geissinger, The face structure of a poset polytope, Proceedings of the Third Caribbean Conference on Combinatorics and Computing (Bridgetown, 1981) Univ. West Indies, Cave Hill, 1981, pp. 125–133. MR 657196
- I. M. Gel′fand, R. M. Goresky, R. D. MacPherson, and V. V. Serganova, Combinatorial geometries, convex polyhedra, and Schubert cells, Adv. in Math. 63 (1987), no. 3, 301–316. MR 877789, DOI 10.1016/0001-8708(87)90059-4
- Ira M. Gessel, Multipartite $P$-partitions and inner products of skew Schur functions, Combinatorics and algebra (Boulder, Colo., 1983) Contemp. Math., vol. 34, Amer. Math. Soc., Providence, RI, 1984, pp. 289–317. MR 777705, DOI 10.1090/conm/034/777705
- Ira M. Gessel, Lagrange inversion, J. Combin. Theory Ser. A 144 (2016), 212–249. MR 3534068, DOI 10.1016/j.jcta.2016.06.018
- I. J. Good, The number of orderings of $n$ candidates when ties are permitted, Fibonacci Quart. 13 (1975), 11–18. MR 376367
- Vladimir Grujić, Quasisymmetric functions for nestohedra, SIAM J. Discrete Math. 31 (2017), no. 4, 2570–2585. MR 3723317, DOI 10.1137/16M105914X
- Vladimir Grujić and Tanja Stojadinović, Hopf algebra of building sets, Electron. J. Combin. 19 (2012), no. 4, Paper 42, 25. MR 3007177, DOI 10.37236/2413
- V. Grujić and T. Stojadinović, Counting faces of nestohedra, Sém. Lothar. Combin. 78B (2017), Art. 17, 7.
- Branko Grünbaum, Convex polytopes, 2nd ed., Graduate Texts in Mathematics, vol. 221, Springer-Verlag, New York, 2003. Prepared and with a preface by Volker Kaibel, Victor Klee and Günter M. Ziegler. MR 1976856, DOI 10.1007/978-1-4613-0019-9
- M. Haiman, Constructing the associahedron, unpublished notes, 1984.
- Mark Haiman and William Schmitt, Incidence algebra antipodes and Lagrange inversion in one and several variables, J. Combin. Theory Ser. A 50 (1989), no. 2, 172–185. MR 989192, DOI 10.1016/0097-3165(89)90013-7
- Christophe Hohlweg and Carsten E. M. C. Lange, Realizations of the associahedron and cyclohedron, Discrete Comput. Geom. 37 (2007), no. 4, 517–543. MR 2321739, DOI 10.1007/s00454-007-1319-6
- Christophe Hohlweg, Carsten E. M. C. Lange, and Hugh Thomas, Permutahedra and generalized associahedra, Adv. Math. 226 (2011), no. 1, 608–640. MR 2735770, DOI 10.1016/j.aim.2010.07.005
- Christophe Hohlweg, Carsten E. M. C. Lange, and Hugh Thomas, Permutahedra and generalized associahedra, Adv. Math. 226 (2011), no. 1, 608–640. MR 2735770, DOI 10.1016/j.aim.2010.07.005
- Christophe Hohlweg, Vincent Pilaud, and Salvatore Stella, Polytopal realizations of finite type $\mathbf {g}$-vector fans, Adv. Math. 328 (2018), 713–749. MR 3771140, DOI 10.1016/j.aim.2018.01.019
- Brandon Humpert and Jeremy L. Martin, The incidence Hopf algebra of graphs, SIAM J. Discrete Math. 26 (2012), no. 2, 555–570. MR 2967484, DOI 10.1137/110820075
- James E. Humphreys, Reflection groups and Coxeter groups, Cambridge Studies in Advanced Mathematics, vol. 29, Cambridge University Press, Cambridge, 1990. MR 1066460, DOI 10.1017/CBO9780511623646
- S. A. Joni and G.-C. Rota, Coalgebras and bialgebras in combinatorics, Umbral calculus and Hopf algebras (Norman, Okla., 1978) Contemp. Math., vol. 6, Amer. Math. Soc., Providence, RI, 1982, pp. 1–47. MR 646798
- André Joyal, Une théorie combinatoire des séries formelles, Adv. in Math. 42 (1981), no. 1, 1–82 (French, with English summary). MR 633783, DOI 10.1016/0001-8708(81)90052-9
- G. Kreweras, Sur les partitions non croisées d’un cycle, Discrete Math. 1 (1972), no. 4, 333–350 (French). MR 309747, DOI 10.1016/0012-365X(72)90041-6
- Joseph P. S. Kung, Gian-Carlo Rota, and Catherine H. Yan, Combinatorics: the Rota way, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 2009. MR 2483561, DOI 10.1017/CBO9780511803895
- Carsten Lange and Vincent Pilaud, Associahedra via spines, Combinatorica 38 (2018), no. 2, 443–486. MR 3800847, DOI 10.1007/s00493-015-3248-y
- Jean-Louis Loday, Realization of the Stasheff polytope, Arch. Math. (Basel) 83 (2004), no. 3, 267–278. MR 2108555, DOI 10.1007/s00013-004-1026-y
- J.-L. Loday, The multiple faces of the asociahedron, Clay Mathematics Institute Publication, 2005.
- László Lovász and Michael D. Plummer, Matching theory, AMS Chelsea Publishing, Providence, RI, 2009. Corrected reprint of the 1986 original [MR0859549]. MR 2536865, DOI 10.1090/chel/367
- I. G. Macdonald, Symmetric functions and Hall polynomials, 2nd ed., Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 1995. With contributions by A. Zelevinsky; Oxford Science Publications. MR 1354144
- C. Malvenuto, Produits et coproduits des fonctions quasi-symétriques et de l’algèbre des descentes, Ph.D. thesis, Université du Québec à Montréal, 1994.
- Peter McMullen, The polytope algebra, Adv. Math. 78 (1989), no. 1, 76–130. MR 1021549, DOI 10.1016/0001-8708(89)90029-7
- Jason Morton, Lior Pachter, Anne Shiu, Bernd Sturmfels, and Oliver Wienand, Convex rank tests and semigraphoids, SIAM J. Discrete Math. 23 (2009), no. 3, 1117–1134. MR 2538642, DOI 10.1137/080715822
- James G. Oxley, Matroid theory, Oxford Science Publications, The Clarendon Press, Oxford University Press, New York, 1992. MR 1207587
- Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, The Morgan Kaufmann Series in Representation and Reasoning, Morgan Kaufmann, San Mateo, CA, 1988. MR 965765
- Vincent Pilaud and Viviane Pons, Permutrees, Algebr. Comb. 1 (2018), no. 2, 173–224. MR 3856522, DOI 10.5802/alco
- Vincent Pilaud and Francisco Santos, The brick polytope of a sorting network, European J. Combin. 33 (2012), no. 4, 632–662. MR 2864447, DOI 10.1016/j.ejc.2011.12.003
- Alex Postnikov, Victor Reiner, and Lauren Williams, Faces of generalized permutohedra, Doc. Math. 13 (2008), 207–273. MR 2520477
- Alexander Postnikov, Permutohedra, associahedra, and beyond, Int. Math. Res. Not. IMRN 6 (2009), 1026–1106. MR 2487491, DOI 10.1093/imrn/rnn153
- Victor Reiner, Signed posets, J. Combin. Theory Ser. A 62 (1993), no. 2, 324–360. MR 1207741, DOI 10.1016/0097-3165(93)90052-A
- A. Rodríguez Rey, Hopf structures on coxeter species, Master’s thesis, San Francisco State University, 2018.
- G.-C . Rota, Combinatorial Theory, 18.315 Lecture Notes, Fall 1998, Audio transcribed by John N. Guidi, 1998.
- M. Sánchez, Poset hopf monoids, preprint, arXiv:2005.13707 (2020).
- Mario Sanchez, Hopf Monoids and the Theory of Valuations, ProQuest LLC, Ann Arbor, MI, 2021. Thesis (Ph.D.)–University of California, Berkeley. MR 4326528
- William R. Schmitt, Antipodes and incidence coalgebras, J. Combin. Theory Ser. A 46 (1987), no. 2, 264–290. MR 914660, DOI 10.1016/0097-3165(87)90006-9
- William R. Schmitt, Hopf algebras of combinatorial structures, Canad. J. Math. 45 (1993), no. 2, 412–428. MR 1208124, DOI 10.4153/CJM-1993-021-5
- William R. Schmitt, Incidence Hopf algebras, J. Pure Appl. Algebra 96 (1994), no. 3, 299–330. MR 1303288, DOI 10.1016/0022-4049(94)90105-8
- William R. Schmitt, Hopf algebra methods in graph theory, J. Pure Appl. Algebra 101 (1995), no. 1, 77–90. MR 1346429, DOI 10.1016/0022-4049(95)90925-B
- Alexander Schrijver, Combinatorial optimization. Polyhedra and efficiency. Vol. B, Algorithms and Combinatorics, vol. 24, Springer-Verlag, Berlin, 2003. Matroids, trees, stable sets; Chapters 39–69. MR 1956925
- Richard P. Stanley, A chromatic-like polynomial for ordered sets, Proc. Second Chapel Hill Conf. on Combinatorial Mathematics and its Applications (Univ. North Carolina, Chapel Hill, N.C., 1970) University of North Carolina, Chapel Hill, NC, 1970, pp. 421–427. MR 269545
- Richard P. Stanley, Ordered structures and partitions, Memoirs of the American Mathematical Society, No. 119, American Mathematical Society, Providence, RI, 1972. MR 332509
- Richard P. Stanley, Acyclic orientations of graphs, Discrete Math. 5 (1973), 171–178. MR 317988, DOI 10.1016/0012-365X(73)90108-8
- Richard P. Stanley, Two poset polytopes, Discrete Comput. Geom. 1 (1986), no. 1, 9–23. MR 824105, DOI 10.1007/BF02187680
- Richard P. Stanley, Enumerative combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, vol. 62, Cambridge University Press, Cambridge, 1999. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin. MR 1676282, DOI 10.1017/CBO9780511609589
- R. P. Stanley, Combinatorics and commutative algebra, vol. 41, Springer Science & Business Media, 2007.
- Richard P. Stanley, Enumerative combinatorics. Volume 1, 2nd ed., Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, Cambridge, 2012. MR 2868112
- James Dillon Stasheff, Homotopy associativity of $H$-spaces. I, II, Trans. Amer. Math. Soc. 108 (1963), 293–312. 108 (1963), 275-292; ibid. MR 158400, DOI 10.1090/S0002-9947-1963-0158400-5
- John R. Stembridge, Coxeter cones and their $h$-vectors, Adv. Math. 217 (2008), no. 5, 1935–1961. MR 2388082, DOI 10.1016/j.aim.2007.09.002
- Milan Studený, Probabilistic conditional independence structures, Information Science and Statistics, Springer, London, 2005. MR 3183760
- Bernd Sturmfels, Gröbner bases and convex polytopes, University Lecture Series, vol. 8, American Mathematical Society, Providence, RI, 1996. MR 1363949, DOI 10.1090/ulect/008
- Bernd Sturmfels, Solving systems of polynomial equations, CBMS Regional Conference Series in Mathematics, vol. 97, Published for the Conference Board of the Mathematical Sciences, Washington, DC; by the American Mathematical Society, Providence, RI, 2002. MR 1925796, DOI 10.1090/cbms/097
- D. J. A. Welsh, Matroid theory, L. M. S. Monographs, No. 8, Academic Press [Harcourt Brace Jovanovich, Publishers], London-New York, 1976. MR 427112
- Neil White (ed.), Theory of matroids, Encyclopedia of Mathematics and its Applications, vol. 26, Cambridge University Press, Cambridge, 1986. MR 849389, DOI 10.1017/CBO9780511629563
- Thomas Zaslavsky, Signed graphs, Discrete Appl. Math. 4 (1982), no. 1, 47–74. MR 676405, DOI 10.1016/0166-218X(82)90033-6
- Günter M. Ziegler, Lectures on polytopes, Graduate Texts in Mathematics, vol. 152, Springer-Verlag, New York, 1995. MR 1311028, DOI 10.1007/978-1-4613-8431-1
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.