グラフ

グラフとは, 頂点と辺を持ち, 二つの頂点が辺で結ばれているものであり, トポロジーの視点から見れば, 1次元のCW複体のことである。 様々なことに使われるので, 人によって異なる定義が使われていて, 以外と最も一般的な定義を見付けるのが難しい。

私は, 2つの集合 \(\Gamma _{0}\) と \(\Gamma _{1}\) と写像 \[ v: \Gamma _{1} \rarrow {} \Gamma _{0}^{2}/\Sigma _{2} \] の3つ組 \(\Gamma =(\Gamma _{0},\Gamma _{1},v)\) と定義するのが良いと思う。\(\Gamma _{0}\) が頂点の集合, \(\Gamma _{1}\) が辺の集合, そして \(v\) が辺に対してその両端の頂点を対応させる写像である。 このように考えると, quiver (directed graph) との対応を付け易い。

• グラフの基本
• グラフや quiver の例
• グラフの不変量

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

• グラフ上の離散モデル

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

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

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

• グラフのホモトピー論

組み合せ論では, 辺や頂点に「色」や weight を付けたりしたものも考えるが, 辺に方向を付けたものが quiver (oriented graph, directed graph) である。

組み合せ論の中には, いわゆる, グラフ理論という分野があり, グラフのことを専門に調べているが, quiver や tree のように, 他分野で活発に研究されているものもある。 \(k\)-graph のように, 他分野の研究から生まれたグラフの一般化もある。

• 重要なグラフのクラス
• quiver
• tree
• hypergraph
• 無限グラフ
• グラフの一般化や変種
• その他グラフに関連した話題

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

• Open Problem Garden

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

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.