グラフからできる単体的複体や胞体複体

グラフから, 単体的複体を作り, そのホモトピー型を調べることにより元のグラフの性質を得る, というのは, 最近ではかなり popular な手法のようである。また, Jonsson の monograph [Jon08] の §1.1 を見ると, グラフ理論以外にも様々な分野と関係があることが分かる。

グラフから作られる単体的複体として, 例えば以下のようなものがある。 多分, 他にも色々あるだろう。

• neighborhood complex [Lov78]
• neighhorhood complex は free \(\Z _2\)-simplicial complex
• complex of directed forests [Koz99]
• Hom complex
• box complex [MZ04]
• clique complex
• coloring complex や unipolar coloring complex や bipolar coloring complex
• matching complex などの matching から定義される simplicial complex
• independence complex

Csorba は graph の box complex の \(\Z /2\Z \) index について, [Cso07] で Hopf invarinat を用いた例を考えている。そこでは, neighborhood complex は任意の \(\Z _2\)-simplicial complex のホモトピー型を取り得ることも示されている。

Clique complex は, neuron の network の研究に使える [CDI12] ようである。

具体的な問題への応用としては, まずは Lovász による chromatic number への応用 [Lov78] を知っておくべきだろう。これが, 代数的トポロジーの手法の グラフの問題への応用の先駆けとなった仕事, だと思う。 90年代初期には Kriz の [Kří92; Kří00] がある。 そこでは, graph に対し resolution という poset を導入し, その分類空間のホモロジーの連結性により chromatic number が評価できることを示している。Equivariant cohomology ( Bredon cohomology) と Bredon spectral sequence を用いて証明しているのは興味深い。

もちろん, Babson と Kozlov が Lovász のアイデアを発展させて, Hom complex の理論を構築し [BK06], Lovász予想を解決した[BK07] ことは大きい。

Random graph の neighborhood complex や clique complex の連結性などについては, Kahle が [Kah07; Kah09] で調べている。

以上は, グラフを調べるために考えられた simplicial complex であるが, 別の問題意識から構成された simplicial complex が結局は一般のグラフに対する構成だった, という類のものもある。

• chessboard complex
• Boolean complex

Vrecica と Zivajlevic の [VŽ09; VŽ11] によると, chessboard complex は, 元々対称群の coset から定義されたものらしいが, その後様々な問題との関連が発見されている。 Algebraic topologyと の関連では, Ault と Fiedorowicz の symmetric homology [AF] との関係がある。

Matching complex や chessboard complex のホモロジーは, たくさんtorsion を含むらしい。Jonsson の [Jon10; Jon09] など。

Boolean complex は, Ragnarsson と Tenner の [RT09] で Coxeter system に対し定義された。その元になっているのは, Tenner の [Ten] のようである。Ragnarsson と Tenner は, 球面の wedge のホモトピー型を持つことを示しているが, Coxeter system の場合に, [RT11] でそのホモロジーの基底を構成し, その意味付けを考えている。

Graph から 単体的複体を作るというアイデアを更に推しすすめて, “graphのホモトピー論”を考えることもできる。

• グラフのホモトピー論

Hom complex は, 作り方によっては, 単体的複体ではなく, 単体の直積を貼り合せた cell complex として定義することもできる。 他にも, グラフから作られる単体的複体ではない cell complex はある。 例えば, Turaev [Tur] は, perfect matching に関係した dimer complex という cubical set の幾何学的実現としてできる cell complex を構成している。

• dimer complex

辺に向きの付いたグラフ, つまり quiver に対する単体的複体の構成もあってもよいと思うのだが, あまり見かけない。 Palu, Pilaud, Plamondon の [PPP21] では, 次が挙げられている。

• non-kissing complex
• support \(\tau \)-tilting complex

Support \(\tau \)-tilting complex は, quiver の path algebra の support \(\tau \)-tilting module [AIR14] から定義されるものである。

Bustamante [Bus04] による bound quiver の分類空間も quiver から定義される複体のようなものである。

Conant [CT10] のように, hypergraph から単体複体を作ることを考えている人もいる。Kozlov の本 [Koz08] にも, hypergraph や simplicial complex への Hom complex の一般化が書かれている。 別の一般化として, Engström [Eng] が simplicial complex に対して Ramsey complex という simplicial complex を定義している。 グラフの場合は, Ramsey numberの評価に使えるようである。

• Ramsey complex

Turaev の dimer complex も hypergraph に一般化できるようである。

References

[AF]

Shaun Ault and Zbigniew Fiedorowicz. Symmetric Homology of Algebras. arXiv: 0708.1575.

[AIR14]

Takahide Adachi, Osamu Iyama, and Idun Reiten. “\(\tau \)-tilting theory”. In: Compos. Math. 150.3 (2014), pp. 415–452. arXiv: 1210.1036. url: https://doi.org/10.1112/S0010437X13007422.

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

[Bus04]

Juan Carlos Bustamante. “The classifying space of a bound quiver”. In: J. Algebra 277.2 (2004), pp. 431–455. arXiv: math/0305338. url: http://dx.doi.org/10.1016/j.jalgebra.2004.02.024.

[CDI12]

Carina Curto, Anda Degeratu, and Vladimir Itskov. “Flexible memory networks”. In: Bull. Math. Biol. 74.3 (2012), pp. 590–614. arXiv: 1009.4958. url: https://doi.org/10.1007/s11538-011-9678-9.

[Cso07]

Péter Csorba. “Homotopy types of box complexes”. In: Combinatorica 27.6 (2007), pp. 669–682. arXiv: math/0406118. url: https://doi.org/10.1007/s00493-007-2204-x.

[CT10]

James Conant and Oliver Thistlethwaite. “Boolean formulae, hypergraphs and combinatorial topology”. In: Topology Appl. 157.16 (2010), pp. 2449–2461. arXiv: 0808.0739. url: http://dx.doi.org/10.1016/j.topol.2010.08.016.

[Eng]

Alexander Engström. Cohomological Ramsey Theory. arXiv: 1002.4074.

[Jon08]

Jakob Jonsson. Simplicial complexes of graphs. Vol. 1928. Lecture Notes in Mathematics. Berlin: Springer-Verlag, 2008, pp. xiv+378. isbn: 978-3-540-75858-7. url: http://dx.doi.org/10.1007/978-3-540-75859-4.

[Jon09]

Jakob Jonsson. “Five-torsion in the homology of the matching complex on 14 vertices”. In: J. Algebraic Combin. 29.1 (2009), pp. 81–90. arXiv: 1203.5650. url: https://doi.org/10.1007/s10801-008-0123-6.

[Jon10]

Jakob Jonsson. “On the 3-torsion part of the homology of the chessboard complex”. In: Ann. Comb. 14.4 (2010), pp. 487–505. arXiv: 1203.5644. url: https://doi.org/10.1007/s00026-011-0073-x.

[Kah07]

Matthew Kahle. “The neighborhood complex of a random graph”. In: J. Combin. Theory Ser. A 114.2 (2007), pp. 380–387. arXiv: math/0512077. url: https://doi.org/10.1016/j.jcta.2006.05.004.

[Kah09]

Matthew Kahle. “Topology of random clique complexes”. In: Discrete Math. 309.6 (2009), pp. 1658–1671. arXiv: math/0605536. url: https://doi.org/10.1016/j.disc.2008.02.037.

[Koz08]

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: https://doi.org/10.1007/978-3-540-71962-5.

[Koz99]

Dmitry N. Kozlov. “Complexes of directed trees”. In: J. Combin. Theory Ser. A 88.1 (1999), pp. 112–122. url: http://dx.doi.org/10.1006/jcta.1999.2984.

[Kří00]

Igor Kříž. “A correction to: “Equivariant cohomology and lower bounds for chromatic numbers” [Trans. Amer. Math. Soc. 333 (1992), no. 2, 567–577; MR1081939 (92m:05085)]”. In: Trans. Amer. Math. Soc. 352.4 (2000), pp. 1951–1952. url: http://dx.doi.org/10.1090/S0002-9947-99-02494-0.

[Kří92]

Igor Kříž. “Equivariant cohomology and lower bounds for chromatic numbers”. In: Trans. Amer. Math. Soc. 333.2 (1992), pp. 567–577. url: http://dx.doi.org/10.2307/2154049.

[Lov78]

L. Lovász. “Kneser’s conjecture, chromatic number, and homotopy”. In: J. Combin. Theory Ser. A 25.3 (1978), pp. 319–324. url: http://dx.doi.org/10.1016/0097-3165(78)90022-5.

[MZ04]

Jiří Matoušek and Günter M. Ziegler. “Topological lower bounds for the chromatic number: a hierarchy”. In: Jahresber. Deutsch. Math.-Verein. 106.2 (2004), pp. 71–90. arXiv: math/0208072.

[PPP21]

Yann Palu, Vincent Pilaud, and Pierre-Guy Plamondon. “Non-kissing complexes and tau-tilting for gentle algebras”. In: Mem. Amer. Math. Soc. 274.1343 (2021), pp. vii+110. arXiv: 1707.07574. url: https://doi.org/10.1090/memo/1343.

[RT09]

Kári Ragnarsson and Bridget Eileen Tenner. “Homotopy type of the Boolean complex of a Coxeter system”. In: Adv. Math. 222.2 (2009), pp. 409–430. arXiv: 0806.0906. url: http://dx.doi.org/10.1016/j.aim.2009.05.007.

[RT11]

Kári Ragnarsson and Bridget Eileen Tenner. “Homology of the boolean complex”. In: J. Algebraic Combin. 34.4 (2011), pp. 617–639. arXiv: 1005.4411. url: http://dx.doi.org/10.1007/s10801-011-0285-5.

[Ten]

Bridget Eileen Tenner. Pattern Avoidance and the Bruhat Order. arXiv: math/0604322.

[Tur]

Vladimir Turaev. Dimer spaces and gliding systems. arXiv: 1211.3975.

[VŽ09]

Siniša T. Vrećica and Rade T. Živaljević. “Cycle-free chessboard complexes and symmetric homology of algebras”. In: European J. Combin. 30.2 (2009), pp. 542–554. arXiv: 0710.5252. url: http://dx.doi.org/10.1016/j.ejc.2008.03.006.

[VŽ11]

Siniša T. Vrećica and Rade T. Živaljević. “Chessboard complexes indomitable”. In: J. Combin. Theory Ser. A 118.7 (2011), pp. 2157–2166. arXiv: 0911.3512. url: http://dx.doi.org/10.1016/j.jcta.2011.04.007.