STUDENT MATHEMATICAL LIBRARY Volume 90 Discrete Morse Theory Nicholas A. Scoville STUDENT MATHEMATICAL LIBRARY Volume 90 Discrete Morse Theory Nicholas A. Scoville Editorial Board SatyanL. Devadoss John Stillwell (Chair) Rosa Orellana Serge Tabachnikov 2010 Mathematics Subject Classification. Primary 55U05, 58E05, 57Q05, 57Q10. For additional informationand updates on this book, visit www.ams.org/bookpages/stml-90 Library of Congress Cataloging-in-Publication Data Cataloging-in-PublicationDatahasbeenappliedforbytheAMS. Seehttp://www.loc.gov/publish/cip/. Copying and reprinting. Individual readers of this publication, and nonprofit libraries acting for them, are permitted to make fair use of the material, such as to copyselectpagesforuseinteachingorresearch. Permissionisgrantedtoquotebrief passagesfromthispublicationinreviews,providedthecustomaryacknowledgmentof thesourceisgiven. Republication,systematiccopying,ormultiplereproductionofanymaterialinthis publicationispermittedonlyunderlicensefromtheAmericanMathematicalSociety. Requests for permission to reuse portions of AMS publication content are handled by the Copyright Clearance Center. For more information, please visit www.ams.org/ publications/pubpermissions. Send requests for translation rights and licensed reprints to reprint-permission @ams.org. (cid:2)c 2019bytheAmericanMathematicalSociety. Allrightsreserved. PrintedintheUnitedStatesofAmerica. (cid:2)∞ Thepaperusedinthisbookisacid-freeandfallswithintheguidelines establishedtoensurepermanenceanddurability. VisittheAMShomepageathttps://www.ams.org/ 10987654321 242322212019 J.M.J. Contents Preface ix Chapter0. WhatisdiscreteMorsetheory? 1 §0.1. Whatisdiscretetopology? 2 §0.2. WhatisMorsetheory? 9 §0.3. SimplifyingwithdiscreteMorsetheory 13 Chapter1. Simplicialcomplexes 15 §1.1. Basicsofsimplicialcomplexes 15 §1.2. Simplehomotopy 31 Chapter2. DiscreteMorsetheory 41 §2.1. DiscreteMorsefunctions 44 §2.2. Gradientvectorfields 56 §2.3. RandomdiscreteMorsetheory 73 Chapter3. Simplicialhomology 81 §3.1. Linearalgebra 82 §3.2. Bettinumbers 86 §3.3. Invarianceundercollapses 95 Chapter4. MaintheoremsofdiscreteMorsetheory 101 v vi Contents §4.1. DiscreteMorseinequalities 101 §4.2. Thecollapsetheorem 111 Chapter5. DiscreteMorsetheoryandpersistenthomology 117 §5.1. PersistencewithdiscreteMorsefunctions 117 §5.2. PersistenthomologyofdiscreteMorsefunctions 134 Chapter6. Booleanfunctionsandevasiveness 149 §6.1. ABooleanfunctiongame 149 §6.2. SimplicialcomplexesareBooleanfunctions 152 §6.3. Quantifyingevasiveness 155 §6.4. DiscreteMorsetheoryandevasiveness 158 Chapter7. TheMorsecomplex 169 §7.1. Twodefinitions 169 §7.2. Rootedforests 177 §7.3. ThepureMorsecomplex 179 Chapter8. Morsehomology 187 §8.1. Gradientvectorfieldsrevisited 188 §8.2. Theflowcomplex 195 §8.3. Equalityofhomology 196 §8.4. Explicitformulaforhomology 199 §8.5. ComputationofBettinumbers 205 Chapter9. ComputationswithdiscreteMorsetheory 209 §9.1. DiscreteMorsefunctionsfrompointdata 209 §9.2. Iteratedcriticalcomplexes 220 Chapter10. StrongdiscreteMorsetheory 233 §10.1. Stronghomotopy 233 §10.2. StrongdiscreteMorsetheory 242 §10.3. SimplicialLusternik-Schnirelmanncategory 249 Bibliography 257 Contents vii Notationandsymbolindex 265 Index 267 Preface ThisbookservesasbothanintroductiontodiscreteMorsetheoryand a general introduction to concepts in topology. I have tried to present thematerialinawayaccessibletoundergraduateswithnomorethan acourseinmathematicalproofwriting. Althoughsomebookssuchas [102,132] include a single chapter on discrete Morse theory, and one [99] treats both smooth and discrete Morse theory together, no book- lengthtreatmentisdedicatedsolelytodiscreteMorsetheory. Discrete Morsetheorydeservesbetter: Itservesasatoolinapplicationsasvaried as combinatorics [16,41,106,108], probability [57], and biology [136]. Morethanthat,itisfascinatingandbeautifulinitsownright. Discrete Morse theory is a discrete analogue of the “smooth” Morse theory de- veloped in Marston Morse’s 1925 paper [124], but it is most popularly knownviaJohnMilnor[116]. FieldsmedalistStephenSmalewentso far as to call smooth Morse theory “the single greatest contribution of American mathematics” [144]. This beauty and utility carries over to thediscretesetting,asmanyoftheresults,suchastheMorseinequali- ties,havediscreteanalogues. DiscreteMorsetheorynotonlyistopolog- icalbutalsoinvolvesideasfromcombinatoricsandlinearalgebra. Yetit iseasytounderstand,requiringnomorethanfamiliaritywithbasicset theoryandmathematicalprooftechniques. Thuswefindseveralonline introductionstodiscreteMorsetheorywrittenbyundergraduates. For ix