Tree, とは多角形の辺のような, 元に戻ってくる道 (circuit) の無い, 連結なグラフのことである。 正確な定義と基本的な性質については,
例えば, Serre の本 [Ser03] を見るとよい。
Tree は, 一見何でもないものであるが, 多種多様な場面で現われる。Calaque と Ebrahimi-Fard と Manchon の
[CEM11] の Introduction によると, 1889年の Cayley の Quarterly Journal of Mathematics
の論文 [Cay89] で既に rooted 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 を作ることもできる。
Feichtner の [Fei06] によると, complex of trees が最初に登場したのは, Boardman の higher
homotopy commutativity に関する [Boa71] のようである。
その後, complex of trees は, 様々なことに関係していることが発見されている。 例えば, 次のようなこと。
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 へ至る過程が解説してある。
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.
|