幾何学的なグラフの不変量

グラフから, 様々な幾何学的対象を構成する方法が知られている。 このようなものも, グラフの不変量と思ってよいだろう。

まず combinatorial algebraic topology の対象として有名なのは, グラフの Hom complex という単体的複体の構成だろう。

• グラフの Hom complex

Kozlov ら [BK06; BK07; Koz08] を中心に研究されている。Kozlov の survey [Koz07] が詳しい。 その主題は, graph の chromatic number であるが。

\(\Hom (G,H)\) のように, グラフから simplicial set (simplicial complex) を作って, そのホモトピー型を調べることにより, 元のグラフの性質を得る, というのは重要な手法である。Hom complex 以外にも, 実に様々な方法で単体的複体が作られている。

• グラフからできる単体的複体
• グラフのホモトピー論

単体的複体でなく, 凸多面体を作ることも考えられている。 例えば, グラフの cut から \(0/1\)-polytope を作ることができる。また, associahedron の一般化として, graph associahedron というものもある。

• グラフからできる多面体

Eastwood と Huggett [EH07] は, グラフ \(G\) から多様体を作ることを考えている。その多様体は各 \(t\) に対し複素射影空間 \(\CP ^{t-1}\) から作ることができ, その Euler標数を \(t\) の関数と考えたときに, 元のグラフ \(G\) のchromatic polynomial と一致するように作られている。その構成は, configuration space の一般化である。

このように, graph の研究にはトポロジーの手法が非常に有効である。

• topological combinatorics

グラフのconfiguration space のホモトピー型もグラフの不変量として有効らしい。Ghrist の [Ghr01] では, その motivation の一つとして, 工場の床を指定された経路に沿って動く複数のロボットの動きが挙げてある。

• グラフの configuration space
• グラフの braid群

グラフから代数多様体を作り, それを調べることにより graph の組み合せ論的な性質を得ることもできるようである。 Aluffi の構成 [Alu95] である。

有限グラフの十分高い次元への埋め込みの moduli space を考えているのは, Gartler と Thurston [GT] である。 辺の長さをパラメータとして考えている。

References

[Alu95]

Paolo Aluffi. “A blow-up construction and graph coloring”. In: Discrete Math. 145.1-3 (1995), pp. 11–35. url: http://dx.doi.org/10.1016/0012-365X(94)00051-J.

[BK06]

Eric Babson and Dmitry N. Kozlov. “Complexes of graph homomorphisms”. In: Israel J. Math. 152 (2006), pp. 285–312. arXiv: math/0310056. url: http://dx.doi.org/10.1007/BF02771988.

[BK07]

Eric Babson and Dmitry N. Kozlov. “Proof of the Lovász conjecture”. In: Ann. of Math. (2) 165.3 (2007), pp. 965–1007. arXiv: math/0402395. url: http://dx.doi.org/10.4007/annals.2007.165.965.

[EH07]

Michael Eastwood and Stephen Huggett. “Euler characteristics and chromatic polynomials”. In: European J. Combin. 28.6 (2007), pp. 1553–1560. url: http://dx.doi.org/10.1016/j.ejc.2006.09.005.

[Ghr01]

Robert Ghrist. “Configuration spaces and braid groups on graphs in robotics”. In: Knots, braids, and mapping class groups—papers dedicated to Joan S. Birman (New York, 1998). Vol. 24. AMS/IP Stud. Adv. Math. Providence, RI: Amer. Math. Soc., 2001, pp. 29–40. arXiv: math/9905023.

[GT]

Steven J. Gortler and Dylan P. Thurston. Measurement Isomorphism of Graphs. arXiv: 1212.6551.

[Koz07]

Dmitry N. Kozlov. “Chromatic numbers, morphism complexes, and Stiefel-Whitney characteristic classes”. In: Geometric combinatorics. Vol. 13. IAS/Park City Math. Ser. Providence, RI: Amer. Math. Soc., 2007, pp. 249–315. arXiv: math/0505563.

[Koz08]

Dmitry N. Kozlov. “Cohomology of colorings of cycles”. In: Amer. J. Math. 130.3 (2008), pp. 829–857. arXiv: math/0507117. url: http://dx.doi.org/10.1353/ajm.0.0007.