グラフの Hom complex

2つのグラフ \(G\) と \(H\) に対し, poset あるいは regular cell complex \(\Hom (G,H)\) を構成する方法がある。 元々は Lovász によるアイデアのようであるが, まずは, Babson と Kozlov の [BK06] を見るとよいだろう。グラフの Hom complex と呼ばれ, トポロジーの手法を用いてグラフを調べる際には, 重要な役割を果す。Kozlov の本 [Koz08a] の Part III で扱われているが, Kozlov の本は必要なことが Part I と Part II にまとめられているので便利である。

最も有名な応用としては, Babson と Kozlov による Lovász conjecture の証明 [BK07] がある。Schultz の [Sch09] も見るとよい。

• Lovász conjecture

グラフの彩色問題への応用のためには, \(\Hom (G,K_n)\) を調べることになる。ここで, \(K_{n}\) は完全グラフである。 Čukić と Kozlov はこのような Hom complex を graph coloring complex と呼んでいる。

• graph coloring complex

彼等の結果は \(\Hom (G,K_n)\) の連結性に関する Babson と Kozlov の予想を証明したことである。その連結性の評価の改良を Malen が [Mal18] で行なっている。

Hom complex によりグラフの組み合せ論的構造を regular cell complex の性質に翻訳し, ホモロジーなどの位相不変量を調べることにより, グラフの性質を得るというのは, トポロジーの応用として興味深い。 そこで, Hom complex のホモトピー型を調べる方法が色々開発されてきた。

まずは functor としての性質を知っておいた方がよい。 それについては Dochtermann の [Doc09a] を見るのが良いと思う。Kozlov の本にも書いてあるが。 例えば, 同型 \[ \begin {split} \Hom (A\amalg B,C) & \cong \Hom (A,C)\times \Hom (B,C) \\ \Hom (C,A\amalg B) & \cong \Hom (C,A)\amalg \Hom (C,B) \end {split} \] が成り立つ。ただし後者には少し条件が必要であるが。直積と power graph の間の adjoint 性は up to homotopy で成り立つ \[ \Hom (A\times B,C) \simeq \Hom (A,C^B). \] この Dochtermann の論文には, Hom complex のホモトピー型が folding という graph の操作で不変であることも書かれている。 元々は, Kozlov が [Koz06a; Koz06c] で示したことであるが。

• \(H\) が \(G\) の fold ならば任意のグラフ \(T\) に対しホモトピー同値 \[ \begin {split} \Hom (H,T) & \simeq \Hom (G,T) \\ \Hom (T,H) & \simeq \Hom (T,G) \end {split} \] がある。

他にも色々ホモトピー型を調べる手法はある。Schultz の [Sch08] では, \(I\) が independent のとき restriction \[ \Hom (G,H) \longrightarrow \Hom (G\setminus I,H) \] の像 \(\Hom _{I}(G,H)\) と \(\Hom (G,H)\) がホモトピー同値であることが示されている。

Schultz はこのことを用いて \(\Hom (C_5,K_n)\) が \(n\ge 2\) のとき \(\R ^{n+1}\) の中の orthonormal \(2\)-frame の成す Stiefel多様体 になることを示している。ここで, \(C_{5}\) は五角形型のグラフである。 これは Csorba の予想だったものである。

このように, Hom complex としてどのような空間ができるか, というのも興味深い問題である。例えば, Dochtermann は, [Doc09c] でこの「Hom complex としてどのような空間ができるか」という問題について考え, 適当に \(G\) と \(H\) を選べば, 任意の有限単体的複体のホモトピー型が得られることを示している。 また Csorba は [Cso]で, free \(\Z _2\)-action を持つ有限単体的複体は, \(\Hom (K_2,G)\) の形の \(\Z _2\)-homotopy type を持つことを示している。 この結果は, Dochtermann と Schultz [DS12] により対称群の作用に拡張されている。

• \(X\) が free \(\Sigma _n\)-action を持つ有限単体複体ならば, あるグラフ \(G\) により \[ X \simeq _{\Sigma _n} \Hom (K_n,G) \] と表わすことができる。

更に, 特定の種類のグラフに対してどのような空間ができるかという問題もある。 Csorba と Lutz [CL06] によると, complete graph \(K_n\) を値域とする Hom complex は, PL多様体になることが多い。

• \(n\ge \chi (G)\) である任意の \(n\) に対し, \(\Hom (G,K_n)\) がPL多様体になるための必要十分条件は, \(G\) が flag simplicial PL-sphere の \(1\)-skeleton であること。[CL06]

更に, \(G\) が cyclic graph \(C_{2r+1}\) のときの \(\Hom \) complex \(X_{r,n} = \Hom (C_{2r+1},K_n)\) について, double covering \[ X_{r,n} \longrightarrow X_{r,n}/\Z _2 \] の Stiefel-Whitney class について Babson-Kozlov conjecture という予想があった。Kozlov の [Koz06b] に, その簡潔な証明がある。Babson-Kozlov conjecture は, Lovász conjecture の一般化になっているものである。 Kozlov は, 他にも [Koz08b] で cyclic graph から complete graph への \(\Hom \) complex のコホモロジーについて調べている。

\(\Hom (C_{2r+1},G)\) 達をある図式に配置し, その colimit を取ると \(\Hom (K_2,G)\) 上の \(\Z _2\)-equivariant free loop space が (up to homotopy で) 得られることを, Schultz が [Sch] で示している。更に, \(\Hom (C_{2r},G)\) の colimit が \(\Hom (K_2,G)\) 上の (通常の) free loop space とホモトピー同値であることも示している。特に, \(G=K_{n 2}\) のとき, \(S^n\) 上の free loop space を得る。

Kozlov の本 [Koz08a] の p.144 には, グラフの configuration space の discrete model との関係も書いてある。

Dochtermann は [Doc09b] で \(\Hom \) complex のホモトピー群などについて調べている。

一般化としては, Kozlovの本にある simplicial complex や hypergraph への拡張がある。Matsushita [Mat16] は \(X^r\) の部分集合へ一般化している。 また, Engström [Eng] による Ramsey complex というものもある。

• hypergraph の Hom complex
• \(r\)-set の Hom complex [Mat16]
• Ramsey complex

Bakuradze と Gamkrelidzeと Gubeladze [BGG16] は, simplicial complex の Hom complex は simplicial complex ではなく 単体の直積を cell にする cell complexであることに着目し, 多面体を貼り合せた polytopal complex に対する変種, affine Hom complex, を導入している。

• polytopal complex の affine Hom complex

Directed graph (quiver) に対しては, Dochtermann と Singh [DS] が調べ始めたようである。

• directed Hom complex

References

[BGG16]

Malkhaz Bakuradze, Alexander Gamkrelidze, and Joseph Gubeladze. “Affine hom-complexes”. In: Port. Math. 73.3 (2016), pp. 183–205. arXiv: 1407.6870. url: https://doi.org/10.4171/PM/1984.

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

[CL06]

Péter Csorba and Frank H. Lutz. “Graph coloring manifolds”. In: Algebraic and geometric combinatorics. Vol. 423. Contemp. Math. Amer. Math. Soc., Providence, RI, 2006, pp. 51–69. arXiv: math/ 0510177. url: https://doi.org/10.1090/conm/423/08074.

[Cso]

Peter Csorba. Homotopy types of box complexes. arXiv: math / 0406118.

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

[Doc09c]

Anton Dochtermann. “The universality of Hom complexes of graphs”. In: Combinatorica 29.4 (2009), pp. 433–448. arXiv: math/0702471. url: http://dx.doi.org/10.1007/s00493-009-2376-7.

[DS]

Anton Dochtermann and Anurag Singh. Homomorphism complexes, reconfiguration, and homotopy for directed graphs. arXiv: 2108. 10948.

[DS12]

Anton Dochtermann and Carsten Schultz. “Topology of Hom complexes and test graphs for bounding chromatic number”. In: Israel J. Math. 187 (2012), pp. 371–417. arXiv: 0907.5079. url: http://dx.doi.org/10.1007/s11856-011-0085-6.

[Eng]

Alexander Engström. Cohomological Ramsey Theory. arXiv: 1002. 4074.

[Koz06a]

Dmitry N. Kozlov. “A simple proof for folds on both sides in complexes of graph homomorphisms”. In: Proc. Amer. Math. Soc. 134.5 (2006), 1265–1270 (electronic). arXiv: math/0408262. url: http://dx.doi.org/10.1090/S0002-9939-05-08105-0.

[Koz06b]

Dmitry N. Kozlov. “Cobounding odd cycle colorings”. In: Electron. Res. Announc. Amer. Math. Soc. 12 (2006), 53–55 (electronic). arXiv: math/0602561. url: http://dx.doi.org/10.1090/S1079-6762-06-00161-2.

[Koz06c]

Dmitry N. Kozlov. “Collapsing along monotone poset maps”. In: Int. J. Math. Math. Sci. (2006), Art. ID 79858, 8. arXiv: math/0503416.

[Koz08a]

Dmitry Kozlov. Combinatorial algebraic topology. Vol. 21. Algorithms and Computation in Mathematics. Berlin: Springer, 2008, pp. xx+389. isbn: 978-3-540-71961-8. url: http://dx.doi.org/10.1007/978-3-540-71962-5.

[Koz08b]

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.

[Mal18]

Greg Malen. “Homomorphism complexes and \(k\)-cores”. In: Discrete Math. 341.9 (2018), pp. 2567–2574. arXiv: 1601 . 07854. url: https://doi.org/10.1016/j.disc.2018.06.014.

[Mat16]

Takahiro Matsushita. “Morphism complexes of sets with relations”. In: Osaka J. Math. 53.1 (2016), pp. 267–283. arXiv: 1402.0311. url: http://projecteuclid.org/euclid.ojm/1455892633.

[Sch]

Carsten Schultz. Graph colourings, spaces of edges and spaces of circuits. arXiv: math/0606763.

[Sch08]

Carsten Schultz. “Small models of graph colouring manifolds and the Stiefel manifolds \(\Hom (C_5,K_n)\)”. In: J. Combin. Theory Ser. A 115.1 (2008), pp. 84–104. arXiv: math / 0510535. url: http://dx.doi.org/10.1016/j.jcta.2007.04.004.

[Sch09]

Carsten Schultz. “A short proof of \(w^n_1(\Hom (C_{2r+1},K_{n+2}))=0\) for all \(n\) and a graph colouring theorem by Babson and Kozlov”. In: Israel J. Math. 170 (2009), pp. 125–134. arXiv: math / 0507346. url: http://dx.doi.org/10.1007/s11856-009-0023-z.