その他グラフに関連した話題

グラフは, いくつかのデータの関係を抽象化して表示したものとして考えることができる。 様々な数学的構造からグラフが構成される。

• グラフや quiver の例

逆にグラフから色々なものを作ることができる。例えば, hyperplane arrangement もできる。 様々な単体的複体を構成することもできる。

• グラフや hypergraph からできる arrangement
• グラフからできる単体的複体
• グラフからできる代数

個々のグラフではなく, ある種の有限グラフから成る集合を考え, そこから chain complex を構成したものが, Kontsevich の graph complex である。グラフからできる単体的複体とまぎらわしいので, graph chain complex と呼んだ方がいいと思うが。 そして, グラフからできる単体的複体は, graph simplicial complex と呼ぶといいと思う。

• Kontsevich の graph complex

もちろん, トポロジーの結果や手法をグラフの研究に用いるというのは, Euler の時代から行なわれてきたことであり, その意味でトポロジーと関係があると言えなくもない。最近でも Matouse と Ziegler の [MZ04] などがある。

Laplacian などが定義でき, 微分幾何の真似事をすることもできる。Majid の [Maj13] は, その非可換版を考えようという試みである。

グラフというと, 平面や \(\R ^3\) 内のグラフのことを考えることが多いが, より一般の多様体の中のグラフを考えることも重要である。

• グラフの埋め込み

R. Cohen と Norbury は [CN] で metric graph の moduli を考え, 多様体のGromov-Witten 型の不変量を得ている。 Steenrod operation などとも関係あるらしい。これは, 「graph は代数曲線の discrete analogue である」という視点に基づいたアイデアだと思われる。

• グラフと代数曲線

例えば, tropical な世界では, 代数曲線とは metric graph のことを意味するらしい。

Toric 多様体の equivariant cohomology が組み合せ論的データで表せることを発見したのは, Goresky と Kottwitz と MacPherson [GKM98] である。所謂, GKM theory と呼ばれるものであり, GKM manifold と GKM graph の対応を与えている。\(\Z /2\Z \) の直積の作用を考えた mod \(2\) GKM theory (Biss と Guillemin と Holm の [BGH04]) もある。

Equivariant intersection cohomology を考えるためには, graph 上の sheaf という概念が有効のようである。Braden と MacPherson は, [BM01] で moment graph という辺が射影空間の点てラベル付けされたグラフの上の sheaf を用いている。

• moment graph

他にもグラフに様々なデータを付加したものが考えられている。例えば, 辺に向きをつけると quiver になる。

• quiver

グラフは \(C^*\)-algebra の理論でも重要な役割を果たしている。

• グラフの \(C^*\)環

作用素環との関係では, グラフの quantum automorphism group がある。

有限グラフ (の同型類) 全体を基底として持つ Hopf algebra を作ることもできる。Humbert と Martin の [HM] では, graph algebra と呼ばれている。これは, 所謂 combinatorial Hopf algebra の例になっている。

• combinatorial Hopf algebra

Random graph と言って, 決まった頂点集合に対し, ある確率で辺を貼付けてできるgraphの性質について, 確率論的に何が言えるかを調べることも行われている。

• random graph

References

[BGH04]

Daniel Biss, Victor W. Guillemin, and Tara S. Holm. “The mod 2 cohomology of fixed point sets of anti-symplectic involutions”. In: Adv. Math. 185.2 (2004), pp. 370–399. arXiv: math/0107151. url: http://dx.doi.org/10.1016/j.aim.2003.07.007.

[BM01]

Tom Braden and Robert MacPherson. “From moment graphs to intersection cohomology”. In: Math. Ann. 321.3 (2001), pp. 533–551. arXiv: math/0008200. url: http://dx.doi.org/10.1007/s002080100232.

[CN]

Ralph L. Cohen and Paul Norbury. Morse field theory. arXiv: math/ 0509681.

[GKM98]

Mark Goresky, Robert Kottwitz, and Robert MacPherson. “Equivariant cohomology, Koszul duality, and the localization theorem”. In: Invent. Math. 131.1 (1998), pp. 25–83. url: http://dx.doi.org/10.1007/s002220050197.

[HM]

Brandon Humpert and Jeremy L. Martin. The incidence Hopf algebra of graphs. arXiv: 1012.4786.

[Maj13]

Shahn Majid. “Noncommutative Riemannian geometry on graphs”. In: J. Geom. Phys. 69 (2013), pp. 74–93. arXiv: 1011.5898. url: https://doi.org/10.1016/j.geomphys.2013.02.004.

[MZ04]

Jiří Matoušek and Günter M. Ziegler. “Topological lower bounds for the chromatic number: a hierarchy”. In: Jahresber. Deutsch. Math.-Verein. 106.2 (2004), pp. 71–90. arXiv: math/0208072.