グラフのホモトピー論

グラフは, 1次元のCW複体とみなすことができるが, そのように見ると \(S^{1}\) のいくつかの wedge 和 (の disjoint union) とホモトピー同値になり, 面白いことは起きない。 しかしながら, グラフについては, 様々な方法でそのホモトピー論が考えられている。

McGuirk と Park の [MP] の Introduction では, Gianella の [Gia77], Malle の [Mal83], Chen と Yau と Yeh の [CYY01] などが挙げられている。

この Chen と Yau と Yeh の仕事は, その後の Grigor\('\)yan と Lin と Muranov と Yau による quiver の homotopy theory の元になったもののようである。

• quiver のホモトピー論

最近では, グラフから様々な方法で単体的複体を作り, そのホモトピー型を調べるということが行なわれている。

• グラフから作られる単体的複体

これらの単体的複体のホモトピー型を調べることにより, 元のグラフの性質を得ようというのは自然なアイデアであり, グラフの chromatic number などの研究に用いられている。

そのアイデアを更に推しすすめて, “graph のホモトピー論”を考えることもできる。 イギリスの物理学者 Atkin のアイデア [Atk74; Atk76] を元に Barcelo と Kramer と Laubenbacher と Weaver が \(A\)-theory として [Bar+01] で提唱している。

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

そして, 単体的複体に対し, “\(A\)-homotopy group” を定義し, それを graph から作られる単体的複体に適用することにより graph のホモトピー群を定義している。 最近の [BS08; BSW11] を見ると, Barcelo らは, その単体的複体のホモトピー群のことを discrete homotopy group と呼ぶことにしたようである。

• discrete homotopy theory

その後 Babson と Barcelo と de Longueville と Laubenbacher よる “A Homotopy Theory for Graphs” [Bab+06] という論文も出ている。

Dochtermann の [Doc09a] によると, グラフの圏での homotopy を考えるのには, \(\Hom \) complex が有効らしい。上記の discrete homotopy theory (\(A\)-homotopy theory) も, その文脈で扱えるらしい。その後, Dochtermann は [Doc09b] でホモトピー群などを調べている。

Goyal と Santhanam [GSa] はグラフの double mapping cylinder を導入し, それが Hom complex により homotopy pushout に変換されることを示している。

• グラフの double mapping cylinder あるいは homotopy pushout

より一般的な homotopy colimit もグラフの圏で作れそうだ, と思うかもしれないが, Goyal と Santhanam は, 彼等の double mapping cylinder をグラフの圏での homotopy pushout と考えてはいけないと言っている。 そして, Carranza, Kapulkin, Kim の [CKK] により, それは難しいことが示されてしまった。 彼等は, グラフの圏を \(A\)-ホモトピー同値で localize してできる quasicategory が colimit で閉じていないことを示している。

\(A\)-homotopy は, グラフの積 (Cartesian product) を用いて定義されたものであるが, category theory の意味での積を用いた homotopy を Dochtermann が [Doc09a] で考えている。

• \(\times \)-homotopy theory of graphs

それについても, Goyal と Santhanam が [GS21] で調べている。 残念ながら, Strøm-type の model structure は存在しないようである。

また, 彼等は [GSb] で Szumło [Szu16] の意味での cofibration category にもならないことを示している。

別の方向では, Corry [Cor12] によるグラフの étale fundamental group もある。これを拡張した, グラフの étale homotopy theory ができないのだろうか。

• グラフの étale fundamental group

グラフからは, \(C^*\)-algebra を作ることもできる。

• グラフの \(C^*\)-algebra

\(C^*\)-algebra のホモトピー論, つまり 非可換トポロジーのテクニックにより, グラフのホモトピー論ができると思うが, 他のアプローチとの関係はどうなっているのだろう。

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.

[Bab+06]

Eric Babson, Hélène Barcelo, Mark de Longueville, and Reinhard Laubenbacher. “Homotopy theory of graphs”. In: J. Algebraic Combin. 24.1 (2006), pp. 31–44. arXiv: math / 0403146. url: http://dx.doi.org/10.1007/s10801-006-9100-0.

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

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

[CKK]

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

[Cor12]

Scott Corry. “Harmonic Galois theory for finite graphs”. In: Galois-Teichmüller theory and arithmetic geometry. Vol. 63. Adv. Stud. Pure Math. Math. Soc. Japan, Tokyo, 2012, pp. 121–140. arXiv: 1103.1648. url: https://doi.org/10.2969/aspm/06310121.

[CYY01]

Beifang Chen, Shing-Tung Yau, and Yeong-Nan Yeh. “Graph homotopy and Graham homotopy”. In: Discrete Math. 241.1-3 (2001). Selected papers in honor of Helge Tverberg, pp. 153–170. url: https://doi.org/10.1016/S0012-365X(01)00115-7.

[Doc09a]

Anton Dochtermann. “Hom complexes and homotopy theory in the category of graphs”. In: European J. Combin. 30.2 (2009), pp. 490–509. arXiv: math/0605275. url: http://dx.doi.org/10.1016/j.ejc.2008.04.009.

[Doc09b]

Anton Dochtermann. “Homotopy groups of Hom complexes of graphs”. In: J. Combin. Theory Ser. A 116.1 (2009), pp. 180–194. arXiv: 0705.2620. url: http://dx.doi.org/10.1016/j.jcta.2008.06.001.

[Gia77]

Gian Mario Gianella. “Su una omotopia regolare dei grafi”. In: Rend. Sem. Mat. Univ. e Politec. Torino 35 (1976/77), 349–360 (1978).

[GSa]

Shuchita Goyal and Rekha Santhanam. Lovász’ original lower bound: Getting tighter bounds and Reducing computational complexity. arXiv: 1604.05135.

[GSb]

Shuchita Goyal and Rekha Santhanam. Study of Cofibration Category structures on finite Graphs. arXiv: 2301.13587.

[GS21]

Shuchita Goyal and Rekha Santhanam. “(Lack of) model structures on the category of graphs”. In: Appl. Categ. Structures 29.4 (2021), pp. 671–683. arXiv: 1902 . 09182. url: https://doi.org/10.1007/s10485-021-09630-4.

[Mal83]

G. Malle. “A homotopy theory for graphs”. In: Glas. Mat. Ser. III 18(38).1 (1983), pp. 3–25.

[MP]

Zachary McGuirk and Byungdo Park. Brown representability for directed graphs. arXiv: 2003.07426.

[Szu16]

Karol Szumiło. “Homotopy theory of cofibration categories”. In: Homology Homotopy Appl. 18.2 (2016), pp. 345–357. url: http://dx.doi.org/10.4310/HHA.2016.v18.n2.a19.