Configuratioin Spaces of Graphs

グラフ \(G\) を\(1\)次元CW複体とみなすと, その \(n\) 個の異なる点の configuration space \(\mathrm{Conf}_{n}(G)\) を考えることができるが, その点には, \(G\) で道が与えられた \(n\) 個の automated guided vehicle の位置という意味を与えることができる。 よって, その configuration space 上の道は, automated guided vehcle が互いにぶつからないで動く経路を与える。

このように, 工学の問題と関連づけてグラフの configuration space のトポロジーを調べ始めたのは, Ghrist だと思う。 これらのことについては Ghrist の [Ghr01], Abrams と Ghrist の [AG02], Abrams の thesis [Abr00], Farber の [Far] がある。より一般の motion planning については, Farber の本 [Far08] もある。

Harrison, Keating, Robbins [HKR11] や Sawicki [Saw] によると, 物理に登場するモデルとも関係しているようで, 興味深い。

自明でない最も簡単な場合は, Y字型をしたグラフの上の\(2\)点の configuration space であるが, これについては, Ghrist と Koditschek の [GK02] に \(\R ^3\) に埋め込まれた図形として描かれている。

一般のグラフについて, 最も簡単なのは \(2\)点の configuration space であるが, 平面グラフの上の \(2\)点の configuration space については, Barnett と Farber [BF09] が rational cohomology を計算している。Farber と Hanbury による続編 [FH10] では, 辺を付けたり取ったりしたときの影響についても調べられている。

グラフは, 離散的そして組み合せ論的な対象なので, グラフの configuration space を調べるときに, その discrete model を作ろうと考えるのは自然である。実際, そのような model は, 何人もの人により考えられている。

• グラフの discrete configuration space

このような discrete model は, 元の configuration space に deformation retract として埋め込むことができる。 なので, hyperplane arrangement の Salvetti complex に似ている。

このような hyperplane arrangement との類似から, グラフの configuration space の基本群についても, hyperplane arrangement と同様のことが成り立つかという問題が考えられる。 グラフの configuration space の基本群は, グラフの braid 群と呼ばれているようである。

• グラフの braid群
• グラフの configration space の \(K(\pi ,1)\) 問題

グラフの configuration space の \(K(\pi ,1)\) 問題についても, Ghrist らが考えている。

(コ)ホモロジーについては, どこまで分かっているのかよく知らない。 多様体の場合の configuration space のコホモロジーを計算する Bendersky-Gitler spectral sequence [BG91] のグラフ版を, Baranovsky と Sazdanović [BS] が構成し, その \(E_1\)-term の記述を求めている。 Chromatic polynomial の categorification として現れるホモロジーが関係しているようで興味深い。

Chettih と Lütgehetmann [CL] は finite graph の configuration space が torsion free であることを示している。

ホモロジーの stability については, Lütgehetmann [Lüt] が 調べている。

グラフに関係した configuration space としては, Eastwood と Huggett の [EH07] で登場するものもある。 有限グラフのどの頂点とどの頂点が結ばれているかにより, どの座標とどの座標が等しくなってはいけないという条件で定義した configuration space である。グラフの chromatic polynomial をこの種の configuration space の Euler 標数で表わすことができるようで興味深い。

実際には, robot は大きさを持っているので, 大きさを持った点の グラフ上の configuration space も当然調べるべきものである。それについては, Deeley [Dee11] が 2点の場合を調べている。各 robot が異なる大きさを持ってもよい場合は Dover と Özaydin [DÖ] が考えている。

• configuration space of thick particles

References

[Abr00]

Aaron Abrams. “Configuration Spaces and Braid Groups of Graphs”. PhD thesis. University of California at Berkeley, 2000. url: http://www.math.uga.edu/~abrams/research/papers/thesis.ps.

[AG02]

Aaron Abrams and Robert Ghrist. “Finding topology in a factory: configuration spaces”. In: Amer. Math. Monthly 109.2 (2002), pp. 140–150. arXiv: math/0009118. url: http://dx.doi.org/10.2307/2695326.

[BF09]

Kathryn Barnett and Michael Farber. “Topology of configuration space of two particles on a graph. I”. In: Algebr. Geom. Topol. 9.1 (2009), pp. 593–624. arXiv: 0903.2180. url: http://dx.doi.org/10.2140/agt.2009.9.593.

[BG91]

Martin Bendersky and Sam Gitler. “The cohomology of certain function spaces”. In: Trans. Amer. Math. Soc. 326.1 (1991), pp. 423–440. url: http://dx.doi.org/10.2307/2001871.

[BS]

Vladimir Baranovsky and Radmila Sazdanovic. Graph homology and graph configuration spaces. arXiv: 1208.5781.

[CL]

Safia Chettih and Daniel Lütgehetmann. The Homology of Configuration Spaces of Trees with Loops. arXiv: 1612.08290.

[Dee11]

Kenneth Deeley. “Configuration spaces of thick particles on a metric graph”. In: Algebr. Geom. Topol. 11.4 (2011), pp. 1861–1892. url: http://dx.doi.org/10.2140/agt.2011.11.1861.

[DÖ]

James Dover and Murad Özaydın. Homeomorphism and Homotopy Types of Restricted Configuration Spaces of Metric Graphs. arXiv: 1301.5693.

[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.

[Far]

Michael Farber. Collision Free Motion Planning on Graphs. arXiv: math/0406361.

[Far08]

Michael Farber. Invitation to topological robotics. Zurich Lectures in Advanced Mathematics. European Mathematical Society (EMS), Zürich, 2008, pp. x+133. isbn: 978-3-03719-054-8. url: http://dx.doi.org/10.4171/054.

[FH10]

Michael Farber and Elizabeth Hanbury. “Topology of configuration space of two particles on a graph, II”. In: Algebr. Geom. Topol. 10.4 (2010), pp. 2203–2227. arXiv: 1005.2300. url: http://dx.doi.org/10.2140/agt.2010.10.2203.

[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.

[GK02]

Robert W. Ghrist and Daniel E. Koditschek. “Safe cooperative robot dynamics on graphs”. In: SIAM J. Control Optim. 40.5 (2002), pp. 1556–1575. url: https://doi.org/10.1137/S0363012900368442.

[HKR11]

J. M. Harrison, J. P. Keating, and J. M. Robbins. “Quantum statistics on graphs”. In: Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci. 467.2125 (2011), pp. 212–233. arXiv: 1101.1535. url: http://dx.doi.org/10.1098/rspa.2010.0254.

[Lüt]

Daniel Lütgehetmann. Representation Stability for Configuration Spaces of Graphs. arXiv: 1701.03490.

[Saw]

Adam Sawicki. Discrete Morse functions for graph configuration spaces. arXiv: 1206.1986.