AMS eBook CollectionsOne of the world's most respected mathematical collections, available in digital format for your library or institution
Organized Collapse: An Introduction to Discrete Morse Theory
About this Title
Dmitry N. Kozlov, Okinawa Institute of Science and Technology, Okinawa, Japan
Publication: Graduate Studies in Mathematics
Publication Year:
2020; Volume 207
ISBNs: 978-1-4704-5701-3 (print); 978-1-4704-6008-2 (online)
DOI: https://doi.org/10.1090/gsm/207
ReadershipTable of Contents
Download chapters as PDF
Front/Back Matter
Introduction to homology
Further aspects of homology theory
- Category of chain complexes
- Chain homotopy
- Connecting homomorphism
- Singular homology
- Cellular homology
- Suggested further reading for parts 1 and 2
Basic discrete Morse theory
- Simplicial collapses
- Organizing collapsing sequences
- Internal collapses and discrete Morse theory
- Explicit homology classes associated to critical cells
- The critical Morse complex
- Implications and variations
- Suggested further reading for part 3
Extensions of discrete Morse theory
- Algebraic Morse theory
- Discrete Morse theory for posets
- Discrete Morse theory for CW complexes
- Disctrete Morse theory and persistence
- Suggested further reading for part 4
- Seth E. Aaronson, Marie E. Meyer, Nicholas A. Scoville, Mitchell T. Smith, and Laura M. Stibich, Graph isomorphisms in discrete Morse theory, AKCE Int. J. Graphs Comb. 11 (2014), no. 2, 163–176. MR 3243115
- Karim A. Adiprasito, Bruno Benedetti, and Frank H. Lutz, Extremal examples of collapsible complexes and random discrete Morse theory, Discrete Comput. Geom. 57 (2017), no. 4, 824–853. MR 3639606, DOI 10.1007/s00454-017-9860-4
- Michael Agiorgousis, Brian Green, Alex Onderdonk, Kim Rich, and Nicholas A. Scoville, Homologically equivalent discrete Morse functions, Topology Proc. 54 (2019), 283–294. MR 3949263
- R. Ayala, L. M. Fernández, D. Fernández-Ternero, and J. A. Vilches, Discrete Morse theory on graphs, Topology Appl. 156 (2009), no. 18, 3091–3100. MR 2556069, DOI 10.1016/j.topol.2009.01.022
- Eric Babson and Dmitry N. Kozlov, Topological obstructions to graph colorings, Electron. Res. Announc. Amer. Math. Soc. 9 (2003), 61–68. MR 2029466, DOI 10.1090/S1079-6762-03-00112-4
- Eric Babson and Dmitry N. Kozlov, Complexes of graph homomorphisms, Israel J. Math. 152 (2006), 285–312. MR 2214465, DOI 10.1007/BF02771988
- Eric Babson and Dmitry N. Kozlov, Proof of the Lovász conjecture, Ann. of Math. (2) 165 (2007), no. 3, 965–1007. MR 2335799, DOI 10.4007/annals.2007.165.965
- E. Batzies and V. Welker, Discrete Morse theory for cellular resolutions, J. Reine Angew. Math. 543 (2002), 147–168. MR 1887881, DOI 10.1515/crll.2002.012
- Ulrich Bauer and Herbert Edelsbrunner, The Morse theory of Čech and Delaunay complexes, Trans. Amer. Math. Soc. 369 (2017), no. 5, 3741–3762. MR 3605986, DOI 10.1090/tran/6991
- Fernando Benavides and Sergio Rajsbaum, Collapsibility of read/write models using discrete Morse theory, J. Appl. Comput. Topol. 1 (2018), no. 3-4, 365–396. MR 3975558, DOI 10.1007/s41468-018-0011-7
- Bruno Benedetti, Smoothing discrete Morse theory, Ann. Sc. Norm. Super. Pisa Cl. Sci. (5) 16 (2016), no. 2, 335–368. MR 3559605
- Bruno Benedetti, Discrete Morse theory for manifolds with boundary, Trans. Amer. Math. Soc. 364 (2012), no. 12, 6631–6670. MR 2958950, DOI 10.1090/S0002-9947-2012-05614-5
- Bruno Benedetti and Frank H. Lutz, Random discrete Morse theory and a new library of triangulations, Exp. Math. 23 (2014), no. 1, 66–94. MR 3177457, DOI 10.1080/10586458.2013.865281
- A. Björner, Topological methods, Handbook of combinatorics, Vol. 1, 2, Elsevier Sci. B. V., Amsterdam, 1995, pp. 1819–1872. MR 1373690
- A. Borel and J. C. Moore, Homology theory for locally compact spaces, Michigan Math. J. 7 (1960), 137–159. MR 131271
- Glen E. Bredon, Sheaf theory, 2nd ed., Graduate Texts in Mathematics, vol. 170, Springer-Verlag, New York, 1997. MR 1481706, DOI 10.1007/978-1-4612-0647-7
- Benjamin A. Burton, Thomas Lewiner, João Paixão, and Jonathan Spreer, Parameterized complexity of discrete Morse theory, Computational geometry (SoCG’13), ACM, New York, 2013, pp. 127–136. MR 3208204, DOI 10.1145/2462356.2462391
- Nicolas Ariel Capitelli and Elias Gabriel Minian, A simplicial complex is uniquely determined by its set of discrete Morse functions, Discrete Comput. Geom. 58 (2017), no. 1, 144–157. MR 3658332, DOI 10.1007/s00454-017-9865-z
- Gunnar Carlsson, Topology and data, Bull. Amer. Math. Soc. (N.S.) 46 (2009), no. 2, 255–308. MR 2476414, DOI 10.1090/S0273-0979-09-01249-X
- Manoj K. Chari, On discrete Morse functions and combinatorial decompositions, Discrete Math. 217 (2000), no. 1-3, 101–113 (English, with English and French summaries). Formal power series and algebraic combinatorics (Vienna, 1997). MR 1766262, DOI 10.1016/S0012-365X(99)00258-7
- Manoj K. Chari and Michael Joswig, Complexes of discrete Morse functions, Discrete Math. 302 (2005), no. 1-3, 39–51. MR 2179635, DOI 10.1016/j.disc.2004.07.027
- Marshall M. Cohen, A course in simple-homotopy theory, Graduate Texts in Mathematics, Vol. 10, Springer-Verlag, New York-Berlin, 1973. MR 362320
- Sonja Lj. Čukić and Dmitry N. Kozlov, The homotopy type of complexes of graph homomorphisms between cycles, Discrete Comput. Geom. 36 (2006), no. 2, 313–329. MR 2252107, DOI 10.1007/s00454-006-1245-z
- Sonja Lj. Čukić and Dmitry N. Kozlov, Higher connectivity of graph coloring complexes, Int. Math. Res. Not. 25 (2005), 1543–1562. MR 2152894, DOI 10.1155/IMRN.2005.1543
- Justin Curry, Robert Ghrist, and Vidit Nanda, Discrete Morse theory for computing cellular sheaf cohomology, Found. Comput. Math. 16 (2016), no. 4, 875–897. MR 3529128, DOI 10.1007/s10208-015-9266-8
- James F. Davis and Paul Kirk, Lecture notes in algebraic topology, Graduate Studies in Mathematics, vol. 35, American Mathematical Society, Providence, RI, 2001. MR 1841974, DOI 10.1090/gsm/035
- Leila De Floriani, Ulderico Fugacci, and Federico Iuricich, Homological shape analysis through discrete Morse theory, Perspectives in shape analysis, Math. Vis., Springer, [Cham], 2016, pp. 187–209. MR 3822076
- Herbert Edelsbrunner and John L. Harer, Computational topology, American Mathematical Society, Providence, RI, 2010. An introduction. MR 2572029, DOI 10.1090/mbk/069
- H. Edelsbrunner, A. Nikitenko, K. Ölsböck, P. Synak, Radius functions on Poisson-Delaunay mosaics and related complexes experimentally, preprint.
- Herbert Edelsbrunner, Anton Nikitenko, and Matthias Reitzner, Expected sizes of Poisson-Delaunay mosaics and their discrete Morse functions, Adv. in Appl. Probab. 49 (2017), no. 3, 745–767. MR 3694316, DOI 10.1017/apr.2017.20
- Daniel Farley and Lucas Sabalka, Discrete Morse theory and graph braid groups, Algebr. Geom. Topol. 5 (2005), 1075–1109. MR 2171804, DOI 10.2140/agt.2005.5.1075
- A. T. Fomenko, D. B. Fuchs, and V. L. Gutenmacher, Homotopic topology, Akadémiai Kiadó (Publishing House of the Hungarian Academy of Sciences), Budapest, 1986. Translated from the Russian by K. Mályusz. MR 873943
- Robin Forman, A user’s guide to discrete Morse theory, Sém. Lothar. Combin. 48 (2002), Art. B48c, 35. MR 1939695
- Robin Forman, Discrete Morse theory and the cohomology ring, Trans. Amer. Math. Soc. 354 (2002), no. 12, 5063–5085. MR 1926850, DOI 10.1090/S0002-9947-02-03041-6
- Robin Forman, Morse theory for cell complexes, Adv. Math. 134 (1998), no. 1, 90–145. MR 1612391, DOI 10.1006/aima.1997.1650
- Ragnar Freij, Equivariant discrete Morse theory, Discrete Math. 309 (2009), no. 12, 3821–3829. MR 2537376, DOI 10.1016/j.disc.2008.10.029
- William Fulton, Algebraic topology, Graduate Texts in Mathematics, vol. 153, Springer-Verlag, New York, 1995. A first course. MR 1343250, DOI 10.1007/978-1-4612-4180-5
- G. Gaiffi, F. Mori, and M. Salvetti, Minimal CW-complexes for complements to line arrangements via discrete Morse theory, Topology of algebraic varieties and singularities, Contemp. Math., vol. 538, Amer. Math. Soc., Providence, RI, 2011, pp. 293–308. MR 2777826, DOI 10.1090/conm/538/10607
- Étienne Gallais, Combinatorial realization of the Thom-Smale complex via discrete Morse theory, Ann. Sc. Norm. Super. Pisa Cl. Sci. (5) 9 (2010), no. 2, 229–252. MR 2731156
- Sergei I. Gelfand and Yuri I. Manin, Methods of homological algebra, 2nd ed., Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2003. MR 1950475, DOI 10.1007/978-3-662-12492-5
- Aldo Gonzalez-Lorenzo, Alexandra Bac, Jean-Luc Mari, and Pedro Real, Allowing cycles in discrete Morse theory, Topology Appl. 228 (2017), 1–35. MR 3679072, DOI 10.1016/j.topol.2017.05.008
- Marvin J. Greenberg and John R. Harper, Algebraic topology, Mathematics Lecture Note Series, vol. 58, Benjamin/Cummings Publishing Co., Inc., Advanced Book Program, Reading, MA, 1981. A first course. MR 643101
- Frank Harary, Graph theory, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London, 1969. MR 256911
- Shaun Harker, Konstantin Mischaikow, Marian Mrozek, and Vidit Nanda, Discrete Morse theoretic algorithms for computing homology of complexes and maps, Found. Comput. Math. 14 (2014), no. 1, 151–184. MR 3160710, DOI 10.1007/s10208-013-9145-0
- Allen Hatcher, Algebraic topology, Cambridge University Press, Cambridge, 2002. MR 1867354
- Maurice Herlihy, Dmitry Kozlov, and Sergio Rajsbaum, Distributed computing through combinatorial topology, Elsevier/Morgan Kaufmann, Waltham, MA, 2014. MR 3292637
- P. J. Hilton and U. Stammbach, A course in homological algebra, 2nd ed., Graduate Texts in Mathematics, vol. 4, Springer-Verlag, New York, 1997. MR 1438546, DOI 10.1007/978-1-4419-8566-8
- Michael Jöllenbeck and Volkmar Welker, Minimal resolutions via algebraic discrete Morse theory, Mem. Amer. Math. Soc. 197 (2009), no. 923, vi+74. MR 2488864, DOI 10.1090/memo/0923
- Tomasz Kaczynski, Konstantin Mischaikow, and Marian Mrozek, Computational homology, Applied Mathematical Sciences, vol. 157, Springer-Verlag, New York, 2004. MR 2028588, DOI 10.1007/b97315
- Henry King, Kevin Knudson, and Neža Mramor Kosta, Birth and death in discrete Morse theory, J. Symbolic Comput. 78 (2017), 41–60. MR 3535328, DOI 10.1016/j.jsc.2016.03.007
- Kevin P. Knudson, Morse theory, World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2015. Smooth and discrete. MR 3379451, DOI 10.1142/9360
- Dmitry N. Kozlov, Complexes of directed trees, J. Combin. Theory Ser. A 88 (1999), no. 1, 112–122. MR 1713484, DOI 10.1006/jcta.1999.2984
- Dmitry N. Kozlov, Collapsibility of $\Delta (\Pi _n)/\scr S_n$ and some related CW complexes, Proc. Amer. Math. Soc. 128 (2000), no. 8, 2253–2259. MR 1662257, DOI 10.1090/S0002-9939-99-05301-0
- D.N. Kozlov, Trends in Topological Combinatorics, Habilitationsschrift, Bern University, 2002.
- Dmitry N. Kozlov, Discrete Morse theory for free chain complexes, C. R. Math. Acad. Sci. Paris 340 (2005), no. 12, 867–872 (English, with English and French summaries). MR 2151775, DOI 10.1016/j.crma.2005.04.036
- Dmitry N. Kozlov, A simple proof for folds on both sides in complexes of graph homomorphisms, Proc. Amer. Math. Soc. 134 (2006), no. 5, 1265–1270. MR 2199168, DOI 10.1090/S0002-9939-05-08105-0
- Dmitry N. Kozlov, Chromatic numbers, morphism complexes, and Stiefel-Whitney characteristic classes, Geometric combinatorics, IAS/Park City Math. Ser., vol. 13, Amer. Math. Soc., Providence, RI, 2007, pp. 249–315. MR 2383129, DOI 10.1090/pcms/013/06
- Dmitry Kozlov, Combinatorial algebraic topology, Algorithms and Computation in Mathematics, vol. 21, Springer, Berlin, 2008. MR 2361455, DOI 10.1007/978-3-540-71962-5
- Dmitry N. Kozlov, Discrete Morse theory and Hopf bundles, Pacific J. Math. 249 (2011), no. 2, 371–376. MR 2782674, DOI 10.2140/pjm.2011.249.371
- Dmitry N. Kozlov, Chromatic subdivision of a simplicial complex, Homology Homotopy Appl. 14 (2012), no. 2, 197–209. MR 3007093, DOI 10.4310/HHA.2012.v14.n2.a12
- Johannes Köbler, Uwe Schöning, and Jacobo Torán, The graph isomorphism problem: its structural complexity, Progress in Theoretical Computer Science, Birkhäuser Boston, Inc., Boston, MA, 1993. MR 1232421, DOI 10.1007/978-1-4612-0333-9
- MichałKukieła, The main theorem of discrete Morse theory for Morse matchings with finitely many rays, Topology Appl. 160 (2013), no. 9, 1074–1082. MR 3049255, DOI 10.1016/j.topol.2013.04.025
- F. Larrión, M. A. Pizaña, and R. Villarroel-Flores, Discrete Morse theory and the homotopy type of clique graphs, Ann. Comb. 17 (2013), no. 4, 743–754. MR 3129782, DOI 10.1007/s00026-013-0204-7
- L. Lovász, Kneser’s conjecture, chromatic number, and homotopy, J. Combin. Theory Ser. A 25 (1978), no. 3, 319–324. MR 514625, DOI 10.1016/0097-3165(78)90022-5
- László Lovász and Michael D. Plummer, Matching theory, AMS Chelsea Publishing, Providence, RI, 2009. Corrected reprint of the 1986 original [MR0859549]. MR 2536865, DOI 10.1090/chel/367
- Albert T. Lundell and Stephen Weingram, The topology of CW complexes, The University Series in Higher Mathematics, Van Nostrand Reinhold Co., New York, 1969. MR 3822092, DOI 10.1007/978-1-4684-6254-8
- Saunders Mac Lane, Categories for the working mathematician, 2nd ed., Graduate Texts in Mathematics, vol. 5, Springer-Verlag, New York, 1998. MR 1712872
- Saunders MacLane, Homology, 1st ed., Die Grundlehren der mathematischen Wissenschaften, Band 114, Springer-Verlag, Berlin-New York, 1967. MR 349792
- Clément Maria and Hannah Schreiber, Discrete Morse theory for computing zigzag persistence, Algorithms and data structures, Lecture Notes in Comput. Sci., vol. 11646, Springer, Cham, 2019, pp. 538–552. MR 3992985, DOI 10.1007/978-3-030-24766-9_{3}9
- J. Peter May, Simplicial objects in algebraic topology, Chicago Lectures in Mathematics, University of Chicago Press, Chicago, IL, 1992. Reprint of the 1967 original. MR 1206474
- J. P. May, A concise course in algebraic topology, Chicago Lectures in Mathematics, University of Chicago Press, Chicago, IL, 1999. MR 1702278
- John McCleary, A user’s guide to spectral sequences, 2nd ed., Cambridge Studies in Advanced Mathematics, vol. 58, Cambridge University Press, Cambridge, 2001. MR 1793722
- Oleg Melnikov, Regina Tyshkevich, Vladimir Yemelichev, and Vladimir Sarvanov, Lectures on graph theory, Bibliographisches Institut, Mannheim, 1994. Translated from the 1990 Russian original by N. Korneenko with the collaboration of the authors. MR 1388513
- J. Milnor, Morse theory, Annals of Mathematics Studies, No. 51, Princeton University Press, Princeton, NJ, 1963. Based on lecture notes by M. Spivak and R. Wells. MR 163331
- John W. Milnor and James D. Stasheff, Characteristic classes, Annals of Mathematics Studies, No. 76, Princeton University Press, Princeton, NJ; University of Tokyo Press, Tokyo, 1974. MR 440554
- Konstantin Mischaikow and Vidit Nanda, Morse theory for filtrations and efficient computation of persistent homology, Discrete Comput. Geom. 50 (2013), no. 2, 330–353. MR 3090522, DOI 10.1007/s00454-013-9529-6
- Francesca Mori and Mario Salvetti, (Discrete) Morse theory on configuration spaces, Math. Res. Lett. 18 (2011), no. 1, 39–57. MR 2770581, DOI 10.4310/MRL.2011.v18.n1.a4
- James R. Munkres, Elements of algebraic topology, Addison-Wesley Publishing Company, Menlo Park, CA, 1984. MR 755006
- Vidit Nanda, Discrete Morse theory and localization, J. Pure Appl. Algebra 223 (2019), no. 2, 459–488. MR 3850551, DOI 10.1016/j.jpaa.2018.04.001
- Vidit Nanda, Dai Tamaki, and Kohei Tanaka, Discrete Morse theory and classifying spaces, Adv. Math. 340 (2018), 723–790. MR 3886179, DOI 10.1016/j.aim.2018.10.016
- P. S. Novikov, Ob algoritmičeskoĭ nerazrešimosti problemy toždestva slov v teorii grupp, Izdat. Akad. Nauk SSSR, Moscow, 1955 (Russian). Trudy Mat. Inst. Steklov. no. 44. MR 75197
- M. Scott Osborne, Basic homological algebra, Graduate Texts in Mathematics, vol. 196, Springer-Verlag, New York, 2000. MR 1757274, DOI 10.1007/978-1-4612-1278-2
- Viktoriya Ozornova, Discrete Morse theory and a reformulation of the $K(\pi ,1)$-conjecture, Comm. Algebra 45 (2017), no. 4, 1760–1784. MR 3576693, DOI 10.1080/00927872.2016.1226852
- Jan Reininghaus, David Günther, Ingrid Hotz, Steffen Prohaska, and Hans-Christian Hege, TADD: a computational framework for data analysis using discrete Morse theory, Mathematical software—ICMS 2010, Lecture Notes in Comput. Sci., vol. 6327, Springer, Berlin, 2010, pp. 198–208. MR 3663192
- Konstanze Rietsch and Lauren Williams, Discrete Morse theory for totally non-negative flag varieties, Adv. Math. 223 (2010), no. 6, 1855–1884. MR 2601003, DOI 10.1016/j.aim.2009.10.011
- Joseph J. Rotman, An introduction to homological algebra, 2nd ed., Universitext, Springer, New York, 2009. MR 2455920, DOI 10.1007/b98977
- Bruce E. Sagan and Robert Willenbring, Discrete Morse theory and the consecutive pattern poset, J. Algebraic Combin. 36 (2012), no. 4, 501–514. MR 2984154, DOI 10.1007/s10801-012-0347-3
- Nicholas A. Scoville, Discrete Morse theory, Student Mathematical Library, vol. 90, American Mathematical Society, Providence, RI, 2019. MR 3970274, DOI 10.1090/stml/090
- John Shareshian, Discrete Morse theory for complexes of $2$-connected graphs, Topology 40 (2001), no. 4, 681–701. MR 1851558, DOI 10.1016/S0040-9383(99)00076-2
- Emil Sköldberg, Morse theory from an algebraic viewpoint, Trans. Amer. Math. Soc. 358 (2006), no. 1, 115–129. MR 2171225, DOI 10.1090/S0002-9947-05-04079-1
- Edwin H. Spanier, Algebraic topology, Springer-Verlag, New York, [1995?]. Corrected reprint of the 1966 original. MR 1325242
- Robert M. Switzer, Algebraic topology—homotopy and homology, Classics in Mathematics, Springer-Verlag, Berlin, 2002. Reprint of the 1975 original [Springer, New York; MR0385836 (52 #6695)]. MR 1886843
- Vladimir Turaev, Introduction to combinatorial torsions, Lectures in Mathematics ETH Zürich, Birkhäuser Verlag, Basel, 2001. Notes taken by Felix Schlenk. MR 1809561, DOI 10.1007/978-3-0348-8321-4
- James W. Vick, Homology theory, 2nd ed., Graduate Texts in Mathematics, vol. 145, Springer-Verlag, New York, 1994. An introduction to algebraic topology. MR 1254439, DOI 10.1007/978-1-4612-0881-5
- Charles A. Weibel, An introduction to homological algebra, Cambridge Studies in Advanced Mathematics, vol. 38, Cambridge University Press, Cambridge, 1994. MR 1269324, DOI 10.1017/CBO9781139644136
- Volkmar Welker, Discrete Morse theory and free resolutions, Algebraic combinatorics, Universitext, Springer, Berlin, 2007, pp. 81–172. MR 2321838
- J. H. C. Whitehead, Simple homotopy types, Amer. J. Math. 72 (1950), 1–57. MR 35437, DOI 10.2307/2372133
- A. Zhukova, Discrete Morse theory for the barycentric subdivison, Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI) 462 (2017), no. Teoriya Predstavleniĭ, Dinamicheskie Sistemy, Kombinatornye Metody. XXVIII, 52–64; English transl., J. Math. Sci. (N.Y.) 232 (2018), no. 2, 129–137. MR 3743406, DOI 10.1007/s10958-018-3863-4
- A. M. Zhukova and G. Yu. Panina, Discrete Morse theory for moduli spaces of flexible polygons, or a solitaire game on the circle, Mat. Sb. 208 (2017), no. 9, 100–115 (Russian, with Russian summary); English transl., Sb. Math. 208 (2017), no. 9, 1353-1367. MR 3691717, DOI 10.4213/sm8677
- Afra J. Zomorodian, Topology for computing, Cambridge Monographs on Applied and Computational Mathematics, vol. 16, Cambridge University Press, Cambridge, 2009. Reprint of the 2005 original [MR2111929]. MR 2549932