組み合せ論と Hopf algebra

かなり以前から, 組み合せ論では Hopf algebra は有用な道具として使われてきたらしい。 有限のデータを合わせたり分解したりする情報を encode するのに Hopf algebra の product と coproduct を使おうというアイデアである。Aguiar と Bergeron と Sottile の [ABS06] によると, このアイデアは Joni と Rota [JR79] によるものらしい。Schmitt の [Sch87; Sch94] という文献もある。 「合わせたり分解したり」という操作を考えたものとして Blasnik の [Bla10] がある。 この手の Hopf algebra についての lecture note としては, Reiner の講義に基づいた Grinberg と Reiner の [GR] もある。

Aguiar と Bergeron と Sottile は, その論文で combinatorial Hopf algebra という概念を導入した。これは multiplicative linear functional を持つ graded Hopf algebra である。彼らはその linear functional を zeta関数と呼んでいる。

• combinatorial Hopf algebra
• cocommutative combinatorial Hopf algebra の圏の terminal object は symmetric function の成す Hopf algebra
• combinatorial Hopf algebra の圏の terminal object は quasisymmetric function の成す Hopf algebra

Symmetric function の成す algebra を \(\mathrm {BU}\) の cohomology と同一視したときに, それが cocommutative combinatorial Hopf algebra の category での terminal object であるという事実の topological, つまり空間レベルでの類似を Lam が [Lam11] で考えている。最後に quasisymmetric function についても同様のことが成り立つだろうということが述べてある。その根拠は, quasisymmetric function の成す Hopf algebra と \(\Omega \Sigma \CP ^{\infty }\) の cohomology との同型 [BR08] である。

Quasisymmetric function function の成す Hopf algebra と類似の Hopf algebra, つまり symmetric function の成す Hopf algebra, noncommutative symmetric function の成す Hopf algebra, Malvenuto-Reutenauer Hopf algebra [MR95] の関係については, Lam と Pylyavskyy の [LP07] の Introduction に簡潔にまとめられている。 また, Chapoton の [Cha] の Introduction に書いてあるように, Loday と Ronco の dendriform algebra [LR98] も関係がある。

Menous と Novelli と Thibon の [MNT13] では, 他にも free quasisymmetric function, word quasisymmetric function, matrix quasisymmetric function の成す Hopf algebra が使われている。 高次の quasisymmetric function に対応する multi-graded Hopf algebra については, Hsiao と Karaali の [HK11] で調べられている。

• Malvenuto-Reutenauer Hopf algebra

Malvenuto-Reutenauer Hopf algebra は, Aguiar と Sottile [AS05] によると, Malvenuto の [Mal94] で導入されたらしい。出版されたものとしては, [MR95] が最初なので, Malvenuto-Reutenauer (Hopf) algebra と呼ばれているようである。

標数 \(0\) の体 \(k\) 上で, 対称群の group algebra の直和 \(\bigoplus _{n\ge 0} k[\Sigma _n]\) に Hopf algebra の構造を定義したものである, 様々な combinatorial Hopf algebra と関係がある Hopf algebra である。 Aguiar と Sottile の [AS05; AS] を見るとよい。

Buchstaber と Erokhovets [BEb; BEa] は, 全ての polytope の集合から生成される自由アーベル群からできる Hopf algebra を考えている。

Bergeron と Hohlweg [BH06] は, colored version, つまり有限アーベル群の作用がある場合を考えている。

Schmitt の simple graph から作られる Hopf algebra の一般化として, Grujić と Stajadinović [GS12] が building set から Hopf algebra を作っている。 彼等は, [GSJ16] で hypergraph から作られる combinatorial Hopf algebra について調べている。そこでは simplicial complex に対する類似も定義されている。その character を少し変えたものを Benedetti, Halam, Machacek [BHM16] が考えている。

• simplicial complex から作られる Hopf algebra
• hypergraph から作られる Hopf algebra

これらの Hopf algebra と関係が深いのが, tree から作られる Hopf algebraである。

• tree の成す Hopf algebra

graph やhypergraph から作られる Hopf algebra としては, Novelli と Thibon と Thiéry の [NTT04] などもある。 他に, グラフに関係したものとしては, Novelli と Thibon の parking function から定義されるもの [NT; NT07] がある。

グラフの抽象化としては matroid という概念があるが, matroid の族から Hopf algebra を作ることも考えられている。Schmitt の [Sch94] や Crapo と Schmitt の [CS05; CS08] である。

Schmitt の Hopf algebra は Hall algebra の dual として得られることを, Eppolito, Jun, Szczesny [EJS20] が示している。

Crapo と Schmitt の Hopf algebra は, Duchamp と Hoang-Nghia と Krajewskiと Tanasa [Duc+13] で matroid の Tutte polynomial に関する公式を証明するのに使われている。 彼らの証明は, quantum field theory の renormalization に現われる微分方程式を使ったもののようである。Quantum field theory の renormalization に現れる combinatorial Hopf algebra についての文献も多い。 [FG; Sui09a; Sui09b; Tan10] など。

Ronco は, [Ron11] で permutahedra やassociahedra から定義される Hopf algebra を調べている。Multiplihedra については, Forcey らの [FLS10] がある。

Finite space の全体から Hopf algebra 的な構造を定義することも考えられている。Foissy らの [FMP16; FM15; FFM17] などである。これらも combinatorial Hopf algebra の一種である。

様々な組み合せ論的構造から combinatorial Hopf algebra が定義されるため, 組み合せ論的構造を統一して扱うための枠組みとしても有用のようである。例えば, Tutte polynomial など。

• combinatorial Hopf algebra の Tutte polynomial [KMT18]

他の応用としては, mixed Tate motives についての Dupont の [Dup14] もある。

Tree が登場することから分かるように, これらの Hopf algebra は operad とも関係が深い。Holtkamp の[Hol; Hol06] など。 Loday の [Lod08] もある。

References

[ABS06]

Marcelo Aguiar, Nantel Bergeron, and Frank Sottile. “Combinatorial Hopf algebras and generalized Dehn-Sommerville relations”. In: Compos. Math. 142.1 (2006), pp. 1–30. arXiv: math/0310016. url: http://dx.doi.org/10.1112/S0010437X0500165X.

[AS]

Marcelo Aguiar and Frank Sottile. Structure of the Malvenuto-Reutenauer Hopf algebra of permutations (Extended Abstract). arXiv: math/0203101.

[AS05]

Marcelo Aguiar and Frank Sottile. “Structure of the Malvenuto-Reutenauer Hopf algebra of permutations”. In: Adv. Math. 191.2 (2005), pp. 225–275. arXiv: math/0203282. url: http://dx.doi.org/10.1016/j.aim.2004.03.007.

[BEa]

Victor M. Buchstaber and Nickolai Erokhovets. Polytopes, Hopf algebras and Quasi-symmetric functions. arXiv: 1011.1536.

[BEb]

Victor M. Buchstaber and Nickolai Erokhovets. Ring of Polytopes, Quasi-symmetric functions and Fibonacci numbers. arXiv: 1002. 0810.

[BH06]

Nantel Bergeron and Christophe Hohlweg. “Coloured peak algebras and Hopf algebras”. In: J. Algebraic Combin. 24.3 (2006), pp. 299–330. arXiv: math/0505612. url: http://dx.doi.org/10.1007/s10801-006-0009-4.

[BHM16]

Carolina Benedetti, Joshua Hallam, and John Machacek. “Combinatorial Hopf algebras of simplicial complexes”. In: SIAM J. Discrete Math. 30.3 (2016), pp. 1737–1757. arXiv: 1505.04458. url: https://doi.org/10.1137/15M1038281.

[Bla10]

Pawel Blasiak. “Combinatorial route to algebra: the art of composition & decomposition”. In: Discrete Math. Theor. Comput. Sci. 12.2 (2010), pp. 381–400. arXiv: 1008.4685.

[BR08]

Andrew Baker and Birgit Richter. “Quasisymmetric functions from a topological point of view”. In: Math. Scand. 103.2 (2008), pp. 208–242. arXiv: math/0605743.

[Cha]

Frédéric Chapoton. Flows on rooted trees and the Narayana idempotents. arXiv: 1203.1780.

[CS05]

Henry Crapo and William Schmitt. “A free subalgebra of the algebra of matroids”. In: European J. Combin. 26.7 (2005), pp. 1066–1085. arXiv: math / 0409028. url: http://dx.doi.org/10.1016/j.ejc.2004.05.006.

[CS08]

Henry Crapo and William Schmitt. “Primitive elements in the matroid-minor Hopf algebra”. In: J. Algebraic Combin. 28.1 (2008), pp. 43–64. arXiv: math/0511033. url: http://dx.doi.org/10.1007/s10801-007-0066-3.

[Duc+13]

Gérard H. E. Duchamp, Nguyen Hoang-Nghia, Thomas Krajewski, and Adrian Tanasa. “Recipe theorem for the Tutte polynomial for matroids, renormalization group-like approach”. In: Adv. in Appl. Math. 51.3 (2013), pp. 345–358. arXiv: 1301.0782. url: https://doi.org/10.1016/j.aam.2013.04.006.

[Dup14]

Clément Dupont. “The combinatorial Hopf algebra of motivic dissection polylogarithms”. In: Adv. Math. 264 (2014), pp. 646–699. arXiv: 1307.3177. url: https://doi.org/10.1016/j.aim.2014.07.027.

[EJS20]

Chris Eppolito, Jaiung Jun, and Matt Szczesny. “Proto-exact categories of matroids, Hall algebras, and K-theory”. In: Math. Z. 296.1-2 (2020), pp. 147–167. arXiv: 1805 . 02281. url: https://doi.org/10.1007/s00209-019-02429-z.

[FFM17]

Frédéric Fauvet, Loı̈c Foissy, and Dominique Manchon. “The Hopf algebra of finite topologies and mould composition”. In: Ann. Inst. Fourier (Grenoble) 67.3 (2017), pp. 911–945. arXiv: 1503.03820. url: http://aif.cedram.org/item?id=AIF_2017__67_3_911_0.

[FG]

Hector Figueroa and Jose M. Gracia-Bondia. Combinatorial Hopf algebras in quantum field theory I. arXiv: hep-th/0408145.

[FLS10]

Stefan Forcey, Aaron Lauve, and Frank Sottile. “Hopf structures on the multiplihedra”. In: SIAM J. Discrete Math. 24.4 (2010), pp. 1250–1271. arXiv: 0911.2057. url: http://dx.doi.org/10.1137/090776834.

[FM15]

Loı̈c Foissy and Claudia Malvenuto. “The Hopf algebra of finite topologies and \(T\)-partitions”. In: J. Algebra 438 (2015), pp. 130–169. arXiv: 1407 . 0476. url: https://doi.org/10.1016/j.jalgebra.2015.04.024.

[FMP16]

Loı̈c Foissy, Claudia Malvenuto, and Frédéric Patras. “Infinitesimal and \(B_\infty \)-algebras, finite spaces, and quasi-symmetric functions”. In: J. Pure Appl. Algebra 220.6 (2016), pp. 2434–2458. arXiv: 1403.7488. url: https://doi.org/10.1016/j.jpaa.2015.11.014.

[GR]

Darij Grinberg and Victor Reiner. Hopf Algebras in Combinatorics. arXiv: 1409.8356.

[GS12]

Vladimir Grujić and Tanja Stojadinović. “Hopf algebra of building sets”. In: Electron. J. Combin. 19.4 (2012), Paper 42, 25. arXiv: 1212.2910. url: https://doi.org/10.37236/2413.

[GSJ16]

Vladimir Grujić, Tanja Stojadinović, and Duško Jojić. “Generalized Dehn-Sommerville relations for hypergraphs”. In: Eur. J. Math. 2.2 (2016), pp. 459–473. arXiv: 1402.0421. url: https://doi.org/10.1007/s40879-015-0089-6.

[HK11]

Samuel K. Hsiao and Gizem Karaali. “Multigraded combinatorial Hopf algebras and refinements of odd and even subalgebras”. In: J. Algebraic Combin. 34.3 (2011), pp. 451–506. arXiv: 0910.5773. url: https://doi.org/10.1007/s10801-011-0279-3.

[Hol]

Ralf Holtkamp. On Hopf algebra structures over operads. arXiv: math/0407074.

[Hol06]

Ralf Holtkamp. “On Hopf algebra structures over free operads”. In: Adv. Math. 207.2 (2006), pp. 544–565. arXiv: math/0504531. url: https://doi.org/10.1016/j.aim.2005.12.004.

[JR79]

S. A. Joni and G.-C. Rota. “Coalgebras and bialgebras in combinatorics”. In: Stud. Appl. Math. 61.2 (1979), pp. 93–139.

[KMT18]

Thomas Krajewski, Iain Moffatt, and Adrian Tanasa. “Hopf algebras and Tutte polynomials”. In: Adv. in Appl. Math. 95 (2018), pp. 271–330. arXiv: 1508.00814. url: https://doi.org/10.1016/j.aam.2017.12.001.

[Lam11]

Thomas Lam. “Affine Schubert classes, Schur positivity, and combinatorial Hopf algebras”. In: Bull. Lond. Math. Soc. 43.2 (2011), pp. 328–334. arXiv: 0906.0385. url: http://dx.doi.org/10.1112/blms/bdq110.

[Lod08]

Jean-Louis Loday. “Generalized bialgebras and triples of operads”. In: Astérisque 320 (2008), pp. x+116. arXiv: math/0611885.

[LP07]

Thomas Lam and Pavlo Pylyavskyy. “Combinatorial Hopf algebras and \(K\)-homology of Grassmannians”. In: Int. Math. Res. Not. IMRN 24 (2007), Art. ID rnm125, 48. arXiv: 0705.2189. url: http://dx.doi.org/10.1093/imrn/rnm125.

[LR98]

Jean-Louis Loday and María O. Ronco. “Hopf algebra of the planar binary trees”. In: Adv. Math. 139.2 (1998), pp. 293–309. url: http://dx.doi.org/10.1006/aima.1998.1759.

[Mal94]

C. Malvenuto. Produits et coproduits des fonctions quasi-symétriques et de l’algèbre des descentes. Publications du Laboratoire de Combinatoire et d’Informatique, Universite du Quebec a Montreal. 1994.

[MNT13]

Frédéric Menous, Jean-Christophe Novelli, and Jean-Yves Thibon. “Mould calculus, polyhedral cones, and characters of combinatorial Hopf algebras”. In: Adv. in Appl. Math. 51.2 (2013), pp. 177–227. arXiv: 1109.1634. url: https://doi.org/10.1016/j.aam.2013.02.003.

[MR95]

Clauda Malvenuto and Christophe Reutenauer. “Duality between quasi-symmetric functions and the Solomon descent algebra”. In: J. Algebra 177.3 (1995), pp. 967–982. url: http://dx.doi.org/10.1006/jabr.1995.1336.

[NT]

Jean-Christophe Novelli and Jean-Yves Thibon. A Hopf algebra of parking functions. arXiv: math/0312126.

[NT07]

Jean-Christophe Novelli and Jean-Yves Thibon. “Hopf algebras and dendriform structures arising from parking functions”. In: Fund. Math. 193.3 (2007), pp. 189–241. url: http://dx.doi.org/10.4064/fm193-3-1.

[NTT04]

Jean-Christophe Novelli, Jean-Yves Thibon, and Nicolas M. Thiéry. “Algèbres de Hopf de graphes”. In: C. R. Math. Acad. Sci. Paris 339.9 (2004), pp. 607–610. arXiv: 0812.3407. url: http://dx.doi.org/10.1016/j.crma.2004.09.012.

[Ron11]

María Ronco. “Shuffle bialgebras”. In: Ann. Inst. Fourier (Grenoble) 61.3 (2011), pp. 799–850. arXiv: math/0703437. url: https://doi.org/10.5802/aif.2630.

[Sch87]

William R. Schmitt. “Antipodes and incidence coalgebras”. In: J. Combin. Theory Ser. A 46.2 (1987), pp. 264–290. url: http://dx.doi.org/10.1016/0097-3165(87)90006-9.

[Sch94]

William R. Schmitt. “Incidence Hopf algebras”. In: J. Pure Appl. Algebra 96.3 (1994), pp. 299–330. url: http://dx.doi.org/10.1016/0022-4049(94)90105-8.

[Sui09a]

Walter D. van Suijlekom. “Renormalization of gauge fields using Hopf algebras”. In: Quantum field theory. Birkhäuser, Basel, 2009, pp. 137–154. arXiv: 0801 . 3170. url: https://doi.org/10.1007/978-3-7643-8736-5_8.

[Sui09b]

Walter D. van Suijlekom. “The structure of renormalization Hopf algebras for gauge theories. I. Representing Feynman graphs on BV-algebras”. In: Comm. Math. Phys. 290.1 (2009), pp. 291–319. arXiv: 0807.0999. url: https://doi.org/10.1007/s00220-009-0829-x.

[Tan10]

A. Tanasa. “Combinatorial Hopf algebras in (noncommutative) quantum field theory”. In: Romanian J. Phys. 55.9-10 (2010), pp. 1142–1155. arXiv: 1008.1471.