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

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

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

  • neighborhood complex [Lov78]
  • neighhorhood complexはfree \(\Z _2\)-simplicial complex
  • complex of directed forests [Koz99]
  • Hom complex \(\Hom (G,H)\)と \(\Hom _{+}(G,H)\) [BK06]
  • box complex [MZ04]
  • clique complex
  • coloring complex [Ste01]
  • unipolar complex [Jon05]
  • matching complex
  • independence complex

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

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

Hersh と Swartz は [HS08] で coloring complex と unipolar complex の arrangement による解釈を考えている。

Wachs の [Wac03] によると, matching complex は, Bouc の [Bou92] で初めて登場したらしい。 Bouc は, 有限群の\(p\)部分群の成す poset の order complex のホモトピー型を考えるために, matching complex を用いた。 この Wachs の survey では, chessboard complex (complete bipartite graph の matching complex) など関連した話題について, その歴史も含めて解説してある。

具体的な問題への応用としては, まずは Lovász による chromatic number への応用 [Lov78] を知っておくべきだろう。これが, 代数的トポロジーの手法のグラフの問題への応用の先駆けとなった仕事, だと思う。 90年代初期には Kriz の [Křı́92; 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 が [Kaha; Kahb] で調べている。

以上は, グラフを調べるために考えられた 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 の [Jonb; Jona] など。

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 の [PPP] では, 次が挙げられている。

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

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

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

[00]

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

[AF]

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

[AIR]

Takahide Adachi, Osamu Iyama, and Idun Reiten. \(\tau \)-tilting theory. arXiv: 1210.1036.

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

[Bou92]

S. Bouc. “Homologie de certains ensembles de \(2\)-sous-groupes des groupes symétriques”. In: J. Algebra 150.1 (1992), pp. 158–186. url: http://dx.doi.org/10.1016/S0021-8693(05)80054-7.

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

[CDI]

Carina Curto, Anda Degeratu, and Vladimir Itskov. Flexible Memory Networks. arXiv: 1009.4958.

[Cso]

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

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

[HS08]

Patricia Hersh and Ed Swartz. “Coloring complexes and arrangements”. In: J. Algebraic Combin. 27.2 (2008), pp. 205–214. arXiv: 0706.3657. url: http://dx.doi.org/10.1007/s10801-007-0086-z.

[Jona]

Jakob Jonsson. Five-Torsion in the Homology of the Matching Complex on 14 Vertices. arXiv: 1203.5650.

[Jonb]

Jakob Jonsson. On the 3-torsion Part of the Homology of the Chessboard Complex. arXiv: 1203.5644.

[Jon05]

Jakob Jonsson. “The topology of the coloring complex”. In: J. Algebraic Combin. 21.3 (2005), pp. 311–329. url: http://dx.doi.org/10.1007/s10801-005-6914-0.

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

[Kaha]

Matthew Kahle. The neighborhood complex of a random graph. arXiv: math/0512077.

[Kahb]

Matthew Kahle. Topology of random clique complexes. arXiv: math/0605536.

[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: http://dx.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řı́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.

[PPP]

Yann Palu, Vincent Pilaud, and Pierre-Guy Plamondon. Non-kissing complexes and tau-tilting for gentle algebras. arXiv: 1707.07574.

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

[Ste01]

Einar Steingrı́msson. “The coloring ideal and coloring complex of a graph”. In: J. Algebraic Combin. 14.1 (2001), pp. 73–84. arXiv: math/0104063. url: http://dx.doi.org/10.1023/A:1011222121664.

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

[Wac03]

Michelle L. Wachs. “Topology of matching, chessboard, and general bounded degree graph complexes”. In: Algebra Universalis 49.4 (2003). Dedicated to the memory of Gian-Carlo Rota, pp. 345–385. url: http://dx.doi.org/10.1007/s00012-003-1825-1.