グラフ

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

• グラフの定義やグラフの間の写像
• グラフや quiver の例
• グラフの不変量

グラフに対する操作としては, 辺を潰す (edge contraction) のと取り除く (deletion) のが基本である。 もちろん, 他にも様々な操作が考えられている。

• グラフに対する各種操作

離散モース理論では, poset の Hasse diagram の上の partial matching が中心となる。他にもgraph を扱うときは, その上での matching を考えることは基本的である。

• matchings on graphs

グラフに関する問題としては, 4色問題などの彩色問題は基本的である。

• colorability problems of graphs

グラフは, 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.