グラフ

グラフとは, 頂点と辺を持ち, 二つの頂点が辺で結ばれているものであり, ト ポロジーの視点から見れば, 1次元のCW複体のことである。

1次元のCW複体として考えるとそれほど興味深いものには思えないが, 組み合せ 論的なデータを表わすのに重要である。例えば, Dynkin図形もグラフの一種 である。また, 統計物理などでdiscrete modelを構成するときには, グラフが使われることが多い。LinとLipperとYauの [LLY12]など。

幾何学的構造を離散的に考える際にも使われる。例えば, Forman [For93]はグラフ上のline bundle を考えて, Kirchhoffの matrix-tree theorem の一般化を得ている。Kenyon [Ken11] は更に グラフ上の vector bundle を導入している。

  • グラフ上の vector bundle とその上の connection

グラフの埋め込みを結び目の一般化とみなして調べている 人もいて, その視点からはトポロジーでも重要である。またグラフからは様々 な方法で 単体的複体が構成され, そのホモ トピー型が活発に研究されていて, 代数的トポロジーの研究対象としても興味 深い。

組み合せ論では, 色を付けたり方向を付けたりし たものも考えるようであるが。重要なものとしてquiver (oriented graph, directed graph) がある。 組み合せ論の中には, いわゆる, グラフ理論とい う分野があり, グラフのことを専門に調べているが, quivertreeのように, 他分野で活 発に研究されているものもある。 \(k\)-graphのように, 他分野の研究から生まれたグ ラフの一般化もある。

グラフ理論における未解決問題については, 次のサイトにまとめられている。

グラフ理論に関する問題に限らず, 未解決問題を集めようという趣旨のようで あるが, 現在のところグラフ理論が中心になっている。

References

[For93]

Robin Forman. “Determinants of Laplacians on graphs”. In: Topology 32.1 (1993), pp. 35–46. url: http://dx.doi.org/10.1016/0040-9383(93)90035-T.

[Ken11]

Richard Kenyon. “Spanning forests and the vector bundle Laplacian”. In: Ann. Probab. 39.5 (2011), pp. 1983–2017. arXiv: 1001.4028. url: https://doi.org/10.1214/10-AOP596.

[LLY12]

Yong Lin, Gábor Lippner, and Shing-Tung Yau. “Quantum tunneling on graphs”. In: Comm. Math. Phys. 311.1 (2012), pp. 113–132. arXiv: 1101.2660. url: https://doi.org/10.1007/s00220-012-1453-8.