Discrete Homotopy Theory of Graphs

最近, 組み合せ論的な構造に, ホモトピーのアイデアや手法を適用することが盛んになっている。Barcelo らの discrete homotopy theory もその一つである。Barcelo と Smith の [BS08] によると, Kramer と Laubenbacher [KL98] により考えられた単体的複体に対する新しいホモトピー論である。 Atkin の仕事 [Atk74; Atk76] に基いたものらしい。 Barcelo, Kramer, Laubenbacher, Weaver の [Bar+01] が基本的な文献である。 上記の論文では, \(A\)-homotopy theory と呼ばれていたが, その後の [BSW11] では discrete homotopy theory と呼ばれているので, このページのタイトルもそれに従った。

もともとは, グラフに対し考えられていた。

• グラフ準同型の間の \(A\)-homotopy
• グラフ \(\Gamma \) の \(A\)-homotopy group \(A_n(\Gamma )\)

そして, 単体的複体に拡張された。

• 有限次元単体的複体 \(K\) と \(0\le q \le \dim K\) に対し, \(K\) の \(n\) 次 \(q\)-connectivity discrete homotopy group \(A^q_n(K)\)
• 単体的複体の対に対する relative discrete homotopy group と long exact sequence
• 単体的複体 \(K\) と \(0\le q\le \dim K\) に対し, その \(q\) 次元 connectivity graph \(\Gamma ^q(K)\)
• 単体的複体 \(K\) の connectivity \(q\) の \(A\)-homotopy group と \(\Gamma ^q(K)\) の graph としての \(A\)-homotopy group は同型になる。
• グラフ \(\Gamma \) に対し, \(A_n(\Gamma ) \cong \pi _n(X_{\Gamma })\) となる cell complex \(X_{\Gamma }\) の構成

Barcelo と Smith は, [BS08] で Boolean lattice の order complex の discrete fundamental group を計算している。\(3\)-equal arrangement と呼ばれる subspace arrangement の complement の基本群になっているようである。 Permutohedron の discrete fundamental group を計算していることにもなっているらしい。 Subspace arrangement の視点からの一般化が, Barcelo と Severs と White [BSW11] により得られている。一方で, convex polytope の視点から, 彼等は [BSW13] で associahedron の discrete fundamental group を調べている。

対応するホモロジーについては, Barcelo らが [BCW14] で構成している。Eilenberg-Steenrod の公理の類似や Hurewicz の定理の類似も成り立つようである。

• discrete homology

グラフの場合, Carranza と Kapulkin [CKa] が cubical set を用いることを提案している。彼等は, グラフから cubical Kan complex を構成し, そのホモトピー群が \(A\)-homotopy group と一致することを示している。そこで使われている cubical set のホモトピー群については, [CKb] にまとめられている。

このように, 位相空間のホモトピー論の類似ができるということは, \(A\)-ホモトピー同値や discrete homotopy group の同型を誘導する morphism を weak equivalence とする単体的複体の圏 (の拡張) に, model structure が定義できるのではないか, と考えたくなる。

しかしながら, Carranza, Kapulkin, Kim の [CKK] により, グラフの場合は, \(A\)-ホモトピー同値を weak equivalence とする model structure が存在しないことが示されてしまった。

単体的複体の discrete homotopy theory の場合は, まだ可能性がある, と思う。

References

[Atk74]

R. H. Atkin. “An algebra for patterns on a complex. I”. In: Internat. J. Man-Machine Studies 6 (1974), pp. 285–307.

[Atk76]

R. H. Atkin. “An algebra for patterns on a complex. II”. In: Internat. J. Man-Mach. Stud. 8.5 (1976), pp. 483–498.

[Bar+01]

Hélène Barcelo, Xenia Kramer, Reinhard Laubenbacher, and Christopher Weaver. “Foundations of a connectivity theory for simplicial complexes”. In: Adv. in Appl. Math. 26.2 (2001), pp. 97–128. url: http://dx.doi.org/10.1006/aama.2000.0710.

[BCW14]

Hélène Barcelo, Valerio Capraro, and Jacob A. White. “Discrete homology theory for metric spaces”. In: Bull. Lond. Math. Soc. 46.5 (2014), pp. 889–905. arXiv: 1306 . 3915. url: https://doi.org/10.1112/blms/bdu043.

[BS08]

Hélène Barcelo and Shelly Smith. “The discrete fundamental group of the order complex of \(B_n\)”. In: J. Algebraic Combin. 27.4 (2008), pp. 399–421. arXiv: 0711.0915. url: http://dx.doi.org/10.1007/s10801-007-0094-z.

[BSW11]

Hélène Barcelo, Christopher Severs, and Jacob A. White. “\(k\)-parabolic subspace arrangements”. In: Trans. Amer. Math. Soc. 363.11 (2011), pp. 6063–6083. arXiv: 0909 . 0720. url: http://dx.doi.org/10.1090/S0002-9947-2011-05336-5.

[BSW13]

Hélène Barcelo, Christopher Severs, and Jacob A. White. “The discrete fundamental group of the associahedron, and the exchange module”. In: Internat. J. Algebra Comput. 23.4 (2013), pp. 745–762. arXiv: 1012.2810. url: https://doi.org/10.1142/S0218196713400079.

[CKa]

Daniel Carranza and Chris Kapulkin. Cubical setting for discrete homotopy theory, revisited. arXiv: 2202.03516.

[CKb]

Daniel Carranza and Chris Kapulkin. Homotopy groups of cubical sets. arXiv: 2202.03511.

[CKK]

Daniel Carranza, Chris Kapulkin, and Jinho Kim. Nonexistence of colimits in naive discrete homotopy theory. arXiv: 2306.02219.

[KL98]

Xenia H. Kramer and Reinhard C. Laubenbacher. “Combinatorial homotopy of simplicial complexes and complex information systems”. In: Applications of computational algebraic geometry (San Diego, CA, 1997). Vol. 53. Proc. Sympos. Appl. Math. Providence, RI: Amer. Math. Soc., 1998, pp. 91–118.