Tree

Tree, とは多角形の辺のような, 元に戻ってくる道 (circuit) の無い, 連結な グラフのことである。 正確な定義と基本的な性質については, 例えば, Serre の本 [Ser03] を見るとよい。

• forest
• tree とは連結な forest のこと
• rooted tree

Rooted tree を描くときは, root を一番下にして leaf を一番上にして描くのが普通であるが, それにより辺に向きが付き自然に quiver になる。更に, 頂点に順序が付き poset になる。 その poset の Hasse diagram が元の rooted tree になる。よって, rooted tree は, ある種の poset と同じものである。この視点は, operad の bar construction に関する Ching の [Chi05] で使われている。

Tree は, 一見何でもないものであるが, 多種多様な場面で現われる。 まず グラフを調べる方法の一つとして, spanning tree がある。その数が, グラフの Laplacian の固有値で表されるというのが, Kirchhoff の matrix-tree theorem である。1847年に Kirchhoff により証明されている。

• spanning tree
• Kirchhoff’s matrix-tree theorem

Calaque と Ebrahimi-Fard と Manchon の [CEM11] の Introduction によると, 1889年の Cayley の Quarterly Journal of Mathematics の論文 [Cay89] で既に rooted tree が微分方程式に使われているらしい。 組み合せ論以外にも, 例えば, 次のような場面に登場する:

• operad
• \(A_{\infty }\)-algebra
• numerical analysis [But72; GL89; MW08]
• quantum field theory [Kre98; CK98]
• 計算機科学

計算機科学でよく現われるのは, 日本語で二分木と呼ばれる binary tree というものである。

• binary tree

ちょっと不思議な感じの話題としては, binary tree と \(T^2-T+1 = 0\) という2次方程式の関係がある。\(T\) を binary tree 全体の集合とすると, 自明な tree 以外は, root を取り除くと2つの binary tree に分解するので \[ T = T^2 + 1 \] が成り立つ。よって\(T^3+1 = 0\) であり \(T^6-1 = 0 \), 故に \(T^7=T\) が成り立つ。 実際, \(7\)個の binary tree の組と binary tree の間の一対一対応が, 上の計算を辿ることにより作れるのである。以上のことは, Blass の [Bla95] に書いてある。この一般化が, Fiore と Leinster [FL05] によって得られている。非常に興味深い。

Binary tree からは, complex of trees と呼ばれる simplicial complex を作ることもできる。

• complex of trees

Feichtner の [Fei06] によると, complex of trees が最初に登場したのは, Boardman の higher homotopy commutativity に関する [Boa71] のようである。

その後, complex of trees は, 様々なことに関係していることが発見されている。 例えば, 次のようなこと。

• 系統樹
• nested set complex

Complexes of trees については, Delucchi の [Del07] の Introduction や Feichtner [Fei06] をみるとよい。

Treeから作られた空間としては, 群 \(G\) の作用する tree の成す moduli space のようなもの, deformation space という空間もある。 Forester が [For02] で定義した。

• \(G\)-tree の deformation space

Culler-Vogtmann の outer space の一般化になっている点で興味深い。Forester の deformation space の一般的な性質を調べたものとして, Guirardel と Levitt の [GL07] がある。

群の tree への作用としては, 有名なのはいわゆる Bass-Serre 理論 [Ser03] である。その groupoid への一般化が, [Alv10; Alv08; VW] などで考えられている。

• Bass-Serre 理論

Tree から Hopf algebra を構成することもできる。 Quantum field theory の renormalization [Kre98] や quasisymmetric function などと関係がある。Chapoton と Frabetti の [CF11] には quantum electrodynamics から rooted planar binary tree へ至る過程が解説してある。

• rooted tree の成す Hopf algebra

Graph の braid群のコホモロジーを tree の場合に調べたものとして, Farley らの [FS08; Far07] がある。

Gorsky [Gor] は, tree から filtered chain complex を作る方法を考えている。Ozsvath と Szabo の Heegard Floer homology と関係があるようである。

高次元版として hypergraph を用いた hypertree や simplicial complex を用いた stacked simplicial complex がある。

• hypertree [Ber89]
• stacked simplicial complex [FO23]

References

[Alv08]

Aurélien Alvarez. “Une théorie de Bass-Serre pour les relations d’équivalence et les groupoı̈des boréliens”. PhD thesis. École Normale Supérieure de Lyon, 2008. url: https://www.aurelienalvarez.org/my-app/dist/assets/pdf/ALVAREZ_Bass-Serre-groupoides.pdf.

[Alv10]

Aurélien Alvarez. “Théorème de Kurosh pour les relations d’équivalence boréliennes”. In: Ann. Inst. Fourier (Grenoble) 60.4 (2010), pp. 1161–1200. arXiv: 0902.3956. url: http://aif.cedram.org/item?id=AIF_2010__60_4_1161_0.

[Ber89]

Claude Berge. Hypergraphs. Vol. 45. North-Holland Mathematical Library. Combinatorics of finite sets, Translated from the French. Amsterdam: North-Holland Publishing Co., 1989, pp. x+255. isbn: 0-444-87489-5.

[Bla95]

Andreas Blass. “Seven trees in one”. In: J. Pure Appl. Algebra 103.1 (1995), pp. 1–21. arXiv: math/9405205. url: https://doi.org/10.1016/0022-4049(95)00098-H.

[Boa71]

J. M. Boardman. “Homotopy structures and the language of trees”. In: Algebraic topology (Proc. Sympos. Pure Math., Vol. XXII, Univ. Wisconsin, Madison, Wis., 1970). 1971, pp. 37–58.

[But72]

J. C. Butcher. “An algebraic theory of integration methods”. In: Math. Comp. 26 (1972), pp. 79–106.

[Cay89]

Arthur Cayley. “A theorem on trees”. In: Quart. J. Math. 23 (1889), pp. 376–378.

[CEM11]

Damien Calaque, Kurusch Ebrahimi-Fard, and Dominique Manchon. “Two interacting Hopf algebras of trees: a Hopf-algebraic approach to composition and substitution of B-series”. In: Adv. in Appl. Math. 47.2 (2011), pp. 282–308. arXiv: 0806.2238. url: http://dx.doi.org/10.1016/j.aam.2009.08.003.

[CF11]

Frédéric Chapoton and Alessandra Frabetti. “From quantum electrodynamics to posets of planar binary trees”. In: Combinatorics and physics. Vol. 539. Contemp. Math. Providence, RI: Amer. Math. Soc., 2011, pp. 53–66. arXiv: 0811.4712.

[Chi05]

Michael Ching. “Bar constructions for topological operads and the Goodwillie derivatives of the identity”. In: Geom. Topol. 9 (2005), 833–933 (electronic). arXiv: math/0501429. url: http://dx.doi.org/10.2140/gt.2005.9.833.

[CK98]

Alain Connes and Dirk Kreimer. “Hopf algebras, renormalization and noncommutative geometry”. In: Comm. Math. Phys. 199.1 (1998), pp. 203–242. arXiv: hep-th/9808042. url: http://dx.doi.org/10.1007/s002200050499.

[Del07]

Emanuele Delucchi. “Nested set complexes of Dowling lattices and complexes of Dowling trees”. In: J. Algebraic Combin. 26.4 (2007), pp. 477–494. arXiv: math/0603383. url: http://dx.doi.org/10.1007/s10801-007-0067-2.

[Far07]

Daniel Farley. “Presentations for the cohomology rings of tree braid groups”. In: Topology and robotics. Vol. 438. Contemp. Math. Providence, RI: Amer. Math. Soc., 2007, pp. 145–172. arXiv: math/0610424. url: http://dx.doi.org/10.1090/conm/438/08451.

[Fei06]

Eva Maria Feichtner. “Complexes of trees and nested set complexes”. In: Pacific J. Math. 227.2 (2006), pp. 271–286. arXiv: math/0409235. url: http://dx.doi.org/10.2140/pjm.2006.227.271.

[FL05]

Marcelo Fiore and Tom Leinster. “Objects of categories as complex numbers”. In: Adv. Math. 190.2 (2005), pp. 264–277. arXiv: math/0212377. url: http://dx.doi.org/10.1016/j.aim.2004.01.002.

[FO23]

Gunnar Fløystad and Milo Orlich. “Triangulations of polygons and stacked simplicial complexes: separating their Stanley-Reisner ideals”. In: J. Algebraic Combin. 57.3 (2023), pp. 659–686. arXiv: 2108.06520. url: https://doi.org/10.1007/s10801-022-01174-7.

[For02]

Max Forester. “Deformation and rigidity of simplicial group actions on trees”. In: Geom. Topol. 6 (2002), 219–267 (electronic). arXiv: math/0107008. url: http://dx.doi.org/10.2140/gt.2002.6.219.

[FS08]

Daniel Farley and Lucas Sabalka. “On the cohomology rings of tree braid groups”. In: J. Pure Appl. Algebra 212.1 (2008), pp. 53–71. arXiv: math/0602444. url: http://dx.doi.org/10.1016/j.jpaa.2007.04.011.

[GL07]

Vincent Guirardel and Gilbert Levitt. “Deformation spaces of trees”. In: Groups Geom. Dyn. 1.2 (2007), pp. 135–181. arXiv: math/0605545. url: https://doi.org/10.4171/GGD/8.

[GL89]

Robert Grossman and Richard G. Larson. “Hopf-algebraic structure of families of trees”. In: J. Algebra 126.1 (1989), pp. 184–210. url: http://dx.doi.org/10.1016/0021-8693(89)90328-1.

[Gor]

E. Gorsky. Seifert cohomology of trees. arXiv: 0901.1298.

[Kre98]

Dirk Kreimer. “On the Hopf algebra structure of perturbative quantum field theories”. In: Adv. Theor. Math. Phys. 2.2 (1998), pp. 303–334. arXiv: q-alg/9707029.

[MW08]

H. Z. Munthe-Kaas and W. M. Wright. “On the Hopf algebraic structure of Lie group integrators”. In: Found. Comput. Math. 8.2 (2008), pp. 227–257. arXiv: math/0603023. url: http://dx.doi.org/10.1007/s10208-006-0222-5.

[Ser03]

Jean-Pierre Serre. Trees. Springer Monographs in Mathematics. Translated from the French original by John Stillwell, Corrected 2nd printing of the 1980 English translation. Berlin: Springer-Verlag, 2003, pp. x+142. isbn: 3-540-44237-5.

[VW]

Giulia dal Verme and Thomas Weigel. Bass-Serre theory for groupoids. arXiv: 2107.09576.