Discrete Morse theory の応用

Forman の discrete Morse theory やその変種は, PL topology や組み合せ論など様々な応用が発見されている。

Discrete Morse theory は「計算できる」ため, パターン認識などの具体的な問題にも使われている。 Jerse と Kosta の [JM09] の Introduction を見ると, どのような分野に応用されているかが分かるが, とてもそれらについてはここに書き切れない。 以下は, algebraic topology に近い応用について目についたもののリストである。

• グラフからできる単体的複体 ([Bab+99; Sha01; Jon08])
• poset のホモロジー ([Dia])
• hyperplane arrangement の complement の minimality ([SS07])
• Lie algebra の cohomology (Sköldberg [Skö06] や LampretとVavpetič [LV16])

• minimal resolution の構成 ([Skö06; JW; JW09])

  • 有限生成 associative algebra に対する Anick resolution の構成
  • 有限生成可換環上の minimal resolution の構成
  • bimodule の category での minimal resolution の構成
  • 多項式環の monomial ideal の minimal resolution の構成
  • monomial ideal の hull resolution [Nor]
• 自由群の outer automorphism group \(\mathrm {Out}(F_n)\) の Torelli 群 ([BBM07])
• グラフの braid group (Farley と Sabalka [FS05])
• Lusztig の totally non-negative part ([RW10])
• 離散群の有限性 ([Flu+13])
• persistent homology の計算 (Mischaikov とNanda の [MN13])
• ある種の sheaf cohomology の計算 (Curry, Ghrist, Nanda [CGN16])
• 外積代数の Hochschild (co)homology の計算 (Lampret と Vavpetič [LV17])
• 群の表示 ([Fer])

Romero と Sergeraert の [RS] は, まだ後半が未完成のようであるが, simplicial set の degeneracy operator が discrete Morse theory とうまく合うことを主張していて, それにより simplicial set の chain complex とその normalized chain complex が chain homotopy 同値になることや Eilenberg-Zilber の定理が証明できることを示している。代数的トポロジーの基本的なところは, 彼等のアイデアに従って書き直すのがよいのかもしれない。

References

[Bab+99]

Eric Babson, Anders Björner, Svante Linusson, John Shareshian, and Volkmar Welker. “Complexes of not \(i\)-connected graphs”. In: Topology 38.2 (1999), pp. 271–299. arXiv: math/9705219. url: http://dx.doi.org/10.1016/S0040-9383(98)00009-3.

[BBM07]

Mladen Bestvina, Kai-Uwe Bux, and Dan Margalit. “Dimension of the Torelli group for \(\mathrm {Out}(F_n)\)”. In: Invent. Math. 170.1 (2007), pp. 1–32. arXiv: math/0603177. url: http://dx.doi.org/10.1007/s00222-007-0055-0.

[CGN16]

Justin Curry, Robert Ghrist, and Vidit Nanda. “Discrete Morse theory for computing cellular sheaf cohomology”. In: Found. Comput. Math. 16.4 (2016), pp. 875–897. arXiv: 1312.6454. url: https://doi.org/10.1007/s10208-015-9266-8.

[Dia]

Antonio Diaz. A method for integral cohomology of posets. arXiv: 0706.2118.

[Fer]

Ximena Fernández. Morse theory for group presentations. arXiv: 1912.00115.

[Flu+13]

Martin G. Fluch, Marco Marschler, Stefan Witzel, and Matthew C. B. Zaremsky. “The Brin-Thompson groups \(sV\) are of type \(\mathrm {F}_{\infty }\)”. In: Pacific J. Math. 266.2 (2013), pp. 283–295. arXiv: 1207.4832. url: https://doi.org/10.2140/pjm.2013.266.283.

[FS05]

Daniel Farley and Lucas Sabalka. “Discrete Morse theory and graph braid groups”. In: Algebr. Geom. Topol. 5 (2005), pp. 1075–1109. arXiv: math/0410539. url: http://dx.doi.org/10.2140/agt.2005.5.1075.

[JM09]

Gregor Jerše and Neža Mramor Kosta. “Ascending and descending regions of a discrete Morse function”. In: Comput. Geom. 42.6-7 (2009), pp. 639–651. arXiv: 0812 . 1376. url: http://dx.doi.org/10.1016/j.comgeo.2008.11.001.

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

[JW]

Michael Jöllenbeck and Volkmar Welker. Resolution of the residue class field via algebraic discrete Morse theory. arXiv: math/0501179.

[JW09]

Michael Jöllenbeck and Volkmar Welker. “Minimal resolutions via algebraic discrete Morse theory”. In: Mem. Amer. Math. Soc. 197.923 (2009), pp. vi+74. url: http://dx.doi.org/10.1090/memo/0923.

[LV16]

Leon Lampret and Aleš Vavpetič. “(Co)homology of Lie algebras via algebraic Morse theory”. In: J. Algebra 463 (2016), pp. 254–277. arXiv: 1501 . 02533. url: https://doi.org/10.1016/j.jalgebra.2016.04.036.

[LV17]

Leon Lampret and Aleš Vavpetič. “Hochschild (co)homology of exterior algebras using algebraic Morse theory”. In: Comm. Algebra 45.3 (2017), pp. 911–918. arXiv: 1512 . 08283. url: https://doi.org/10.1080/00927872.2016.1172630.

[MN13]

Konstantin Mischaikow and Vidit Nanda. “Morse Theory for Filtrations and Efficient Computation of Persistent Homology”. In: Discrete Comput. Geom. 50.2 (2013), pp. 330–353. url: http://dx.doi.org/10.1007/s00454-013-9529-6.

[Nor]

Patrik Norén. Algebraic discrete Morse theory for the hull resolution. arXiv: 1512.03045.

[RS]

Ana Romero and Francis Sergeraert. Discrete Vector Fields and Fundamental Algebraic Topology. arXiv: 1005.5685.

[RW10]

Konstanze Rietsch and Lauren Williams. “Discrete Morse theory for totally non-negative flag varieties”. In: Adv. Math. 223.6 (2010), pp. 1855–1884. arXiv: 0810.4314. url: http://dx.doi.org/10.1016/j.aim.2009.10.011.

[Sha01]

John Shareshian. “Discrete Morse theory for complexes of \(2\)-connected graphs”. In: Topology 40.4 (2001), pp. 681–701. url: http://dx.doi.org/10.1016/S0040-9383(99)00076-2.

[Skö06]

Emil Sköldberg. “Morse theory from an algebraic viewpoint”. In: Trans. Amer. Math. Soc. 358.1 (2006), 115–129 (electronic). url: http://dx.doi.org/10.1090/S0002-9947-05-04079-1.

[SS07]

Mario Salvetti and Simona Settepanella. “Combinatorial Morse theory and minimality of hyperplane arrangements”. In: Geom. Topol. 11 (2007), pp. 1733–1766. arXiv: 0705 . 2874. url: http://dx.doi.org/10.2140/gt.2007.11.1733.