Tree

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

• tree の定義
• rooted tree の定義

Tree は, 一見何でもないものであるが, 多種多様な場面で現われる。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 の [Bla] に書いてある。この一般化が, 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 が [For] で定義した。

• \(G\)-tree の deformation space

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

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 と関係があるようである。

References

[Bla]

Andreas Blass. Seven Trees in One. arXiv: math/9405205.

[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.

[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.

[For]

Max Forester. Deformation and rigidity of simplicial group actions on trees. arXiv: math/0107008.

[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.

[GL]

Vincent Guirardel and Gilbert Levitt. Deformation spaces of trees. arXiv: math/0605545.

[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.