Discrete Morse Theory Is At Least As Perfect As Morse Theory Bruno Benedetti ∗ Inst. Mathematics,KTH,Stockholm [email protected] January 2012 2 1 0 2 Abstract n a Inboundingthehomologyofamanifold,Forman’sDiscreteMorsetheoryrecoversthefullpre- J cisionofclassicalMorsetheory: GivenaPLtriangulationofamanifoldthatadmitsaMorsefunc- 4 tion with c critical points of index i, we show that some subdivision of the triangulation admits 1 i a boundary-criticaldiscrete Morse function with ci interior critical cells of dimension d−i. This ] dualizesandextendsarecentresultbyGallais. Furtherconsequencesofourworkare: G (1)Everysimplyconnectedsmoothd-manifold(d6=4)admitsalocallyconstructibletriangula- D tion. (ThissolvesaproblembyZˇivaljevic´.) . (2)Uptorefiningthesubdivision,theclassicalnotionofgeometricconnectivitycanbetranslated h t combinatoriallyviathenotionofcollapsedepth. a m [ 1 Introduction 4 v MorseTheory,introducedbyMarstonMorseintheTwenties[43],hasbeenareservoirforbreakthrough 8 results ever since. It analyzes a smooth manifold M without boundary by looking at generic smooth 4 5 functions f : M −→ R. Via Morse theory, one can bound the homology of a manifold: The number 0 of critical points of f of index i is not less than the i-th Betti number of M. When these two numbers . 0 coincide, theMorsefunction iscalled“perfect”. 1 Plenty of manifolds do not admit perfect Morse functions. Yet sometimes non-perfect Morse func- 0 tions may be “sharpened”: Smale’s cancellation theorem provides sufficient conditions for canceling 1 : criticalpointsinpairs[49,50]. Formanyinterestingexamplesofmanifolds,includingspheresandcom- v i plex manifolds, the sharpening process goes on until one eventually reaches a perfect Morse function. X ThisisatthecoreofSmale’sproofofthehigher-dimensional Poincare´ conjecture [50]. r a In the last decade, Forman’s Discrete Morse Theory [19] has provided important contributions to computational geometry and to combinatorial topology. Discrete Morse Theory uses regular cell com- plexes in place of manifolds. It studies a complex C by looking at certain weakly-increasing maps f :(C,⊆)−→(R,≤), where (C,⊆) is the poset of all faces of C, ordered by inclusion. The “critical cells” in the discrete setting are simply the faces ofC at which the function f is strictly increasing. As for smooth Morse theory, the critical cells of f of dimension i are not fewer than the i-th Betti number ofC. Whenequality isattained, f iscalled“perfect”. There is also a discrete analogous of Smale’s cancellation theorem: A sufficient condition for pair- wise canceling critical cells is the existence of a unique “gradient path” (see [20, Section 9] for the ∗TheresearchleadingtotheseresultshasreceivedfundingfromtheGo¨ranGustaffssonFoundation,Stockholm,Sweden, andfromtheEuropeanResearchCouncil,undertheEuropeanUnion’sseventhframeworkprogramme(FP7/2007-2013)/ERC Grantagreementno.247029-SDModels. 1 definition) from theboundary ofonecelltotheother cell. Bothcellsarenolonger critical ifwereverse thegradient path[19]. Imagine a situation in which the two theories — the smooth one and the discrete one — can be appliedatthesametime. Infact,anysmoothmanifoldwillautomaticallyadmitPLtriangulations [14].1 Whichtheoryisgoingtogivethebetterbounds? In a previous work [6] we showed that if the triangulation is fixed, smooth Morse theory typically wins at large. For each k ≥0 and each d ≥3, we constructed a PL triangulation of Sd on which any discrete Morse function must have more than k critical edges [6, Thms. 3.10 & 4.18] [7, Thm. 2.19]. SincethefirstBettinumberofSd iszero,thisdemonstratesthatforafixedtriangulationofSd thebounds given by discrete Morse theory may be arbitrarily bad — independently of the function chosen. In contrast, by the smooth Poincare´ conjecture (proven in all dimension d 6=4), every closed d-manifold homotopy equivalent to Sd admits a (perfect) smooth Morse function with only two critical points, one ofindex0andtheotheroneofindexd. The ‘nasty’ triangulations of Sd are not rare. Typically, the problem is the presence in the (d−2)- skeleton of a complicated (d−2)-knot with relatively few facets. This is a local defect, which intu- itively explains why knotted spheres are at least as numerous as unknotted ones. (This statement can be made precise by counting triangulations asymptotically with respect to the number of facets, cf. [6, Section3.2].) Yetindiscretizinganycontinuoustheory,oneusuallyleavesthedooropenforsuccessiverefinements of the discrete structure chosen. What if we do not fix a triangulation? Or better, what if we initially choose atriangulation, but later allow forsubdivisions? Inthismorenatural setting, itturns out thatwe canrecoverthefullprecisionofsmoothMorsetheoryalreadyatthediscretelevel. Thefirstclaimofthis factiscontained intherecentworkbyGallais[24,Thm.3.1]: Let M be a closed d-dimensional smooth manifold that admits a smooth Morse function withc criticalpointsofindexi. (Inparticular, MadmitsaPLhandledecompositionintoc i i i-handles.) Thenasuitable PLtriangulation M ofMadmitsadiscrete Morsefunction with c criticalcellsofdimensioni. i Theproofin[24]contains aminorgap,whichweexplaininRemark3.9. Here we present a “dual result”, obtained with a slightly simpler (and independent) combinatorial ap- proach: MainTheorem 1(Theorem 4.4). LetM beanyPLtriangulated d-manifold, withorwithout boundary, thatadmitsahandledecomposition intoc PLi-handles. i Then a suitable subdivision of M admits a boundary-critical discrete Morse function with c critical i interiorcellsofdimensiond−i. Both results show that if one can sharpen “smoothly” (via Smale’s cancellation theorem) then, up to subdividing, one can sharpen also “discretely”. Moreover, the conclusion of Main Theorem 4.4 is exactlywhatweneedtoansweraquestion byZˇivaljevic´, whichwewillnowexplain. Locally constructible triangulations of manifolds (or, shortly, LC manifolds) were introduced by Durhuus and Jonsson in 1994 [17], in connection with the discretization of quantum gravity. They are themanifolds obtainable from sometree of d-simplices by repeatedly identifying twoadjacent (d−1)- simplices inthe boundary [7]. (A “treeofd-simplices” isad-ball whose dual graph isatree.) Durhuus and Jonsson showed that all LC manifolds are simply connected. Moreover, they showed with ele- mentary methods that all LC closed 3-manifolds are spheres [17]. (This could also be derived via the 1Kervaireconstructedtopological10-manifoldsthatadmitPLtriangulations,withoutadmittinganysmoothstructure[34]. 2 3-dimensional Poincare´ conjecture, since all LC manifolds are simply connected. However, Durhuus– Jonsson’s combinatorial proofappeared abouttenyearsbeforePerelman’sproofofthePoincare´ conjec- ture.) Even if for d ≤3 all closed LC d-manifolds are spheres, it recently turned out that for d ≥4 other topological types such as products of spheres are possible [5]. Meanwhile, LC closed manifolds have beencharacterizedbytheauthorandZieglerasthemanifoldsadmittingadiscreteMorsefunctionwithout criticalfacesofdimension(d−1)[6,7]. In2009,Zˇivaljevic´ hasconjecturedthattheclassoftopological typesofLCtriangulations consists ofallsimply connected manifolds. Theintuition behind thisconjec- ture is that the topological notion of simply connectedness is ‘captured’ by the combinatorial notion of local constructibility. Via Main Theorem 4.4, we are now able to prove Zˇivaljevic´’s conjecture in all dimensions higherthanfour. MainTheorem2(Theorem5.2). EverysimplyconnectedPLd-manifold(andthuseverysmoothd-ma- nifold)admitsanLCtriangulation, exceptpossibly whend =4. Whend=3,MainTheorem2reliesonPerelman’sproofofthePoincare´ conjecture, cf.[42]. Infact, modulotheelementarycombinatorialproofthatallclosedLC3-manifoldsarespheres,MainTheorem2 isindeedequivalent tothePoincare´ conjecture whend=3. When d > 5, the proof of Main Theorem 2 is obtained by combining our Main Theorem 1 with Smale’sproof ofthe Poincare´ conjecture. Thatsaid, ourproof ofMain Theorem 1isrelatively easy, by induction onthedimension d ofM,andcanbesketched asfollows: (1) Wearegivenahandle decomposition ofM withc PLi-handles, whichtopologically ared-balls. If i thehandlesandtheirintersections are“nicely”triangulated, soistheirunionM (cf.Theorem4.1). (2) Since the intersection of each handle H with the previous handles is a lower-dimensional submani- foldofitsboundary ¶ H,wemayassumebyinduction thatthisintersection hasbeennicelytriangu- latedalready. (3) Thus, we are left with the problem of how to extend the given, nice triangulations of submanifolds of ¶ H into anice subdivision ofthe whole ball H. Weachieve this by adapting aresult ofclassical PLtopology byZeeman,cf.Proposition 3.7. Intuitively,afterMainTheorem2,LCtriangulationsshouldberegardedasthe“nicest”triangulations of simply connected manifolds. More generally, what are the “nicest” triangulations of k-connected manifolds? Toanswerthisquestion, weputtogoodusethenotionofcollapse depth, whichwerecently introduced in [6]. This collapse depth turns out to be a combinatorial analogous of the classical notion of geometrical connectivity, studied among others by Stallings [51] and Wall [52]. Building on their formidablework,wecanprovethefollowing: Main Theorem 3 (Corollary 4.6). Every k-connected smooth or PL d-manifold, if k≤d−4, admits a triangulation withcollapsedepthk+1. Thus, the collapse depth of a triangulation of a given d-manifold equals the geometric connectivity of the manifold, plus one, plus some “combinatorial noise” which depends only on the triangulation chosen. Intuitively, thisnoisecanbeprogressively reducedbytakingsuitablesubdivisions. 2 Preliminaries Here we review the basic definitions from the world of triangulated manifolds and PL topology. We refer the reader to one of the books [13, 25, 31, 47, 54] for a more detailed introduction. Our notation differs from the standard one only in the following aspect: In order to avoid a possible linguistic am- biguity (namely, the fact that if the smooth Poincare´ conjecture is false, some 4-ball might be “PL” as 3 manifoldbut“non-PL”asball),weadoptaslightlystronger definitionof“PLmanifold”. Inallpractical examples, this newdefinition coincides withthe oldone. Infact, wedonotevenknow whether the two definitions arereally different: Aconcrete example onwhichthetwodefinitions woulddisagree, would also disprove the smooth Poincare´ conjecture, which is a long-standing open problem in topology. See Subsection2.3fordetails. 2.1 Manifoldsand handledecompositions Byad-dimensionalTOP-manifoldwemeanatopologicalspaceM,Hausdorffandcompact,inwhichev- erypointhasanopenneighborhoodthatiseitherhomeomorphictoRdorhomeomorphictotheEuclidean half-space {x∈Rd|x ≥0}. The boundary of a TOP-manifold is the set of points with neighborhood d homeomorphic to the Euclidean half-space. By TOP-manifold with boundary (resp. without boundary) wemean that the boundary is non-empty (resp. empty). Closed is synonymous of “without boundary”. Thustheboundaryofany(d+1)-manifoldiseitherempty,oradisjointunionofclosedd-manifolds. All theTOP-manifoldsweconsiderhereareconnectedandorientable. Ad-TOP-ball(resp. ad-TOP-sphere) isaTOP-manifoldhomeomorphic tothed-simplex(resp. totheboundary ofthe(d+1)-simplex). A smooth manifold is a TOP-manifold that admits a smooth structure. Some 4-dimensional TOP- manifolds do not admit any smooth structure [25, p. 105]. In contrast, some TOP-manifolds admit evenmore than one smooth structure: Using Morse theory, Milnor constructed a7-dimensional smooth manifoldthatishomeomorphic,butnotdiffeomorphic,totheboundaryoftheunitballinR8[41]. S2×S2 has even infinitely many different smooth structures [4]. In contrast, any TOP-manifold of dimension differentthanfouradmitsonlyafinitenumberofnon-diffeomorphic smoothstructures. Let I=[0,1] be the unit segment in R. Let M be a d-dimensional TOP-manifold with boundary and let H be a d-dimensional TOP-ball, so that H∩M⊂¶ M. We say that (H,h) is a d-dimensional handle of index p on M, or simply a p-handle, if h:Ip×Id−p −→H is a homeomorphism such that h(¶ Ip×Id−p)=M∩H. Wedenote a p-handle by H(p), carrying the index (and not the dimension!) in thenotation. TheTOP-manifoldN=M∪H(p) isobtainedfromMby“attaching a p-handle”. Werefer toM∩H(p) astheintersection ofthe p-handle H(p). Thenotation N=M∪H(r)∪H(s) means that H(r) isanr-handleonMandH(s) isans-handle onM∪H(r). Ahandledecomposition ofaTOP-manifoldMisanexpression oftheform M = H(0)∪ ... ∪H(r) ∪H(s), 0 m−1 m whereH(0) isa0-handleandallotherhandlesare p-handleswith p>0. (Thissettingcorresponds tothe 0 particularcaseV =0/ andV =¶ Mofthemoregeneralnotionof“handledecompositionforacobordism 0 1 (M,V ,V )” described in [47, 49].) We can assume that the handles are attached in order of increasing 0 1 index[25,p.107]. IfBisaTOP-ball,withslightabuseofnotation weviewBasa0-handleandregard thetautologyB=H(0) asahandledecomposition. Onlyd-ballsadmithandledecompositions withonly onehandle. Thecoreofad-dimensional p-handleHistheimageunderthehomeomorphismh:Ip×Id−p−→ H ofthe p-dimensionalTOP-ballIp× 1,...,1 ⊂Rd. (Wereferto[25,p.100]orto[47,p.74]forniceil- 2 2 lustrations.) Bydefinition,thecoreo(cid:8)fa p-han(cid:9)dleisa p-cell. Byshrinkingeachhandleontoitscore,from a handle decomposition we obtain a CW-complex homotopy equivalent to M [47, p. 83]. In particular, if a TOP-manifold admits a handle decomposition without 1-handles, then the TOP-manifold is simply connected. The converse is not true: Mazur constructed a contractible smooth 4-manifold all of whose handledecompositionscontain1-handles[23,38]. Moregenerally, letkbeanintegerin{1,...,d}. Ad- dimensionalTOP-manifoldM isk-connected ifallthehomotopygroupsp (M),...p (M)arezero;itis 0 k geometrically k-connected ifitadmitsahandledecomposition withone0-handleandnofurtherhandles ofdimension≤k[52]. Sinceeveryhandlecanbeshrunkontoitscore,everygeometrically p-connected 4 TOP-manifoldisalso p-connected. Theconverse isfalse: Mazur’ssmoothmanifold is1-connected, but notgeometrically. Some4-dimensional TOP-manifoldsdonotadmitanyhandledecomposition [25,p.105]. However, every TOP-manifold that admits a smooth structure admits also some smooth Morse function; and any smoothMorsefunction inducesinfactahandledecomposition, cf.Milnor[40]. 2.2 Triangulations,joins and subdivisions The underlying (topological) space |C| of a simplicial complexC is the union of all of its faces. Con- versely, the simplicial complexC is called a triangulation of |C| (and of any topological space homeo- morphic to|C|). IfC and Dare two simplicial complexes with the sameunderlying space,C is called a subdivision ofDifeverycellofC iscontained inacellofD. By a d-manifold we mean a simplicial complex whose underlying space is homeomorphic to a d- dimensional TOP-manifold. For example, by a d-ball or a d-sphere we mean a simplicial complex homeomorphic to aTOP-ball(resp. aTOP-sphere). In other words, allthe manifolds weconsider from now on are actually triangulations of TOP-manifolds. We point out that not all TOP-manifolds can be triangulated: There are counterexamples in each dimension d ≥ 4. In fact, a 4-dimensional TOP- manifold admits a handle decomposition if and only if it admits a smooth structure, if and only if it is triangulable [25,p.105]. Since TOP-balls can be triangulated, it makes sense to study handle decompositions in the trian- gulated category: Each p-handle should be a simplicial complex, and it should intersect the previous handles at a subcomplex of its boundary, homeomorphic to ¶ Ip×Id−p. Every manifold, possibly af- ter a suitable subdivision, admits a handle decomposition in the triangulated sense. We will use latin characters forhandledecompositions inthetriangulated category, writing M′ = H(0)∪ ... ∪H(r) ∪H(s), 0 m−1 m whereM′ iseitherthemanifoldM itself,or(possibly) asuitable subdivision ofM. Giventwodisjointsimplicesa andb ,thejoina ∗b isasimplexwhoseverticesaretheverticesofa plusthe vertices ofb . Byconvention, 0/∗b isb itself. Thejoin oftwosimplicial complexes Aand Bis definedasA∗B:={a ∗b :a ∈A, b ∈B}. Ifs isafaceofasimplicialcomplexC,andsˆ isanarbitrary pointintheinteriorofs ,wedefine C′ = (C−star(s ,C)) ∪ sˆ ∗link(s ,C). ThisC′ isasubdivisionofC. WesaythatC′ isobtainedfromCbystarringthefaces . Astellarsubdivi- sionisasubdivision obtained starringoneormorefaces,insomeorder. Afirstderivedsubdivision ofC isobtainedbystarringallthesimplicesofC,inorderof(weakly)decreasingdimension. Recursively,an r-thderivedsubdivision isthefirstderivedofan(r−1)-stderived. Thebarycentric subdivision isafirst derived subdivision obtained by starring at the barycenters. With abuse of notation, wewill denote any first derived subdivision of C (including the barycentric) by sdC. Stellar subdivisions are particularly nice from acombinatorial perspective: Forexample, ifC isashellable complex, any stellar subdivision ofC isshellable, whileanarbitrary subdivision ofC mightnotbeshellable. 2.3 PLtopology Ifak-simplexD isthejoinoftwodisjointfacess andt ,thendims +dimt =k−1and ¶ D =¶ (s ∗t )=(¶s ∗t )∪(s ∗¶t ). Assuming the pair (s ,t ) is ordered, the expression to the right hand side gives (up to isomorphism) k different waysofexpressing theboundary ofak-simplex. Ifs isak-simplex inside aPLtriangulated 5 d-manifold M, and link(M,s ) = ¶t for some (d−k)-simplex t not in M, the bistellar flip c (s ,t ) consistsofchanging M to M˜ := (M−s ∗¶t ) ∪ (¶s ∗t ). Ad-ballBiscalledPLifoneofthefollowingequivalent [45]conditions holds: (i) B is piecewise-linearly homeomorphic to a d-simplex; this means that there exist subdivisions B′ ofBandD ′ ofthed-simplex, andabijective maph:B′→D ′,suchthathmapsvertices tovertices andsimpliceslinearlytosimplices; (ii) Bisobtainable fromthed-simplexviaafinitesequence ofbistellarflips. Similarly,ad-sphereSiscalledPLifoneofthefollowingequivalent [45]conditions holds: (i) Sispiecewise-linearly homeomorphic totheboundary ofthe(d+1)-simplex; (ii) Sisobtainable fromtheboundary ofthe(d+1)-simplexviaafinitesequence ofbistellarflips. Givenad-sphereS,thefactthatSisPLimpliesthateveryvertexlinkinsideSisaPL(d−1)-sphere. Surprisingly, theconversealsoholds,except(possibly)whend=4. Theconjecturethatthisholdswhen d =4 as well goes under the name of PL Poincare´ conjecture. It is equivalent to the smooth Poincare´ conjecture, whichclaimsthateveryTOP-manifoldwithasmoothstructureandthesamehomotopytype of a 4-sphere is diffeomorphic to S4 [35, Problem 4.89] [13, 39]. It is also equivalent to the conjecture that every 4-sphere is PL.These three equivalent conjectures are typically believed to be false [22], but whenever interesting classes of 4-spheres have been analyzed, they have always turn out to be PL; see Akbulut [1,2]. Thatsaid, ineachdimension d ≥5wealready know that non-PLd-spheres existbythe workofEdwards[18]. A d-manifold is linkwise-PL if the link of any vertex on its boundary (resp. in its interior) is a PL (d−1)-ball(resp.aPL(d−1)-sphere). AllPLballsandspheresarelinkwise-PL.Thethree-dimensional Poincare´ conjecture, recently proven by Perelman [42], implies that for d ≤ 4 all d-manifolds are linkwise-PL. Linkwise-PL d-manifolds are usually called “PL manifolds” in the literature. We will refrainfromthissimplification,sinceitcouldpotentiallycreatesomeembarassmentwhend=4: Infact, all 4-spheres are linkwise-PL (manifolds), but unless the smooth Poincare´ conjecture is true, we would expecttofindsomenon-PL4-sphere someday. Let us define “PL handle decompositions” as handle decompositions inside the PL category. For- mally, the definition isbyinduction on thedimension: All(triangulated) handle decompositions ofad- manifold arePLhandle decompositions, ifd ≤2. Recursively, ahandle decomposition ofad-manifold M (d>2)iscalledaPLhandledecomposition ifandonlyif: • allhandlesarePLballs; • allintersections admitaPLhandledecomposition. For example, every PL d-sphere admits a PL handle decomposition with one PL 0-handle and one PL d-handle, whose intersection is a PL (d−1)-sphere. In the present paper, by PL manifold we will denote a manifold that admits a PL handle decomposition. This notation is consistent: A PL manifold homeomorphic to a sphere is a PL sphere, even if the smooth Poincare´ conjecture turns out to be false. (Thesamecannot besaidoflinkwise-PL manifolds.) Clearly, ifthesmooth Poincare´ conjecture istrue, PLmanifolds andlinkwise-PLmanifoldscoincide. EverysmoothmanifoldadmitsaPLhandledecomposition [14]. Infact,anysmoothMorsefunction on the manifold induces one possible PL handle decomposition, cf. [47, Chapter 6] or [25, Chapter 4]. Neither the (linkwise) PL property nor the smooth structure are preserved under homeomorphisms: for example, two manifolds homeomorphic to S7 need not be diffeomorphic [41]; one could be PLand the other one non-PL [18]. Interestingly, not all PL manifolds are smooth: Kervaire found examples of closedPL10-manifolds thatdonotadmitanysmoothstructure[34]. 6 2.4 DiscreteMorsefunctions, collapses andlocalconstructions The face poset (C,⊂) of a simplicial complexC is the set of all the faces ofC, ordered with respect to inclusion. By(R,≤)wedenote theposet oftherealnumberswiththeusualordering. Adiscrete Morse functionisanorder-preserving map f from(C,⊂)to(R,≤),suchthat: • thepreimage f−1(r)ofanyrealnumberrconsists ofatmosttwoelements; • if f(s )= f(t ),theneithers ⊆t ort ⊆s . AcriticalcellofC isafaceatwhich f isinjective. The function f induces a perfect matching (called Morse matching) on the non-critical cells: Two cells are matched if and only if they have identical image under f. The Morse matching can be repre- sentedbyasystemofarrows: Whenevers ⊂t and f(s )= f(t ),onedrawsanarrowfromthebarycenter ofs tothebarycenteroft . WeconsidertwodiscreteMorsefunctionsequivalentiftheyinducethesame Morse matching. For example, up to replacing a discrete Morse function f with an equivalent one, we can assume that f(s ) is a positive integer for all s . Forman’s original definition of a discrete Morse function is weaker than the one presented here; but one can easily see that each Morse function in the senseofFormanisequivalent toadiscreteMorsefunction inoursense. An elementary collapse is the simultaneous removal from a simplicial complexC of a pair of faces (s ,S ), such that S is the only face of C that properly contains s . If C′ =C−s −S , we say that C collapses onto C′. We also say that the complexC collapses onto the complex D ifC can be reduced to D by a finite sequence of elementary collapses. A collapsible complex is a complex that collapses onto a single vertex. Equivalently, a simplicial complex is collapsible if and only if it admits a discrete Morsefunctionwithonecriticalvertexandnocriticalcellsofhigherdimension. Collapsible complexes are contractible; collapsible PL manifolds are necessarily balls [53]. However, some PL3-balls are not collapsible [8]andsomecollapsible 6-balls(forexample, theconesovernon-PL5-balls) arenotPL. Ad-manifold without boundary is endo-collapsible if itadmits adiscrete Morse function with only two critical faces, which have to be a vertex and a d-simplex. A d-manifold with boundary is endo- collapsible ifitadmitsadiscrete Morsefunction whosecritical cellsareallboundary faces plusexactly oneinterior face, whichhastobed-dimensional. Bothcollapsibility and endo-collapsibility are weaker properties than shellability, a classical notion in combinatorial topology, cf. [6, 9]. Shellable manifolds are either balls or spheres [9]. In contrast, the topology of collapsible manifolds is not completely understood (or better, it is understood only in the PL case [53]). However, endo-collapsible manifolds areeitherballsorspheres[6,Theorem3.12]. A discrete Morse function on a manifold M is boundary-critical if all of the boundary faces of M are critical cells. The collapse depth cdepthM of a d-manifold M is the maximal integer k for which there exists a boundary-critical discrete Morse function on M with one critical d-cell and no critical interior (d−i)-cells, for each i∈{1,...,k−1}. In general 1≤cdepthM ≤dimM. A manifold M is endo-collapsible ifandonlyifcdepthM=dimM. Atree of d-simplices isad-ball whose dual graph isa tree. The locally constructible manifolds are themanifolds obtainable from sometree of d-simplices by repeatedly identifying twoadjacent (d−1)- simplices in the boundary [7]. Equivalently, the locally constructible manifolds are those with collapse depth ≥2[6, 7]. From now on, wewillshorten “locally constructible” into “LC”. Topologically, every LC 3-manifold is homeomorphic to a 3-sphere with a finite number of “cacti” of 3-balls removed [7, Theorem 1.2][17]. All LC d-manifolds are simply connected [6, 17]. Any stellar subdivision of an LC (resp. endo-collapsible) manifold is also LC (resp. endo-collapsible). Also, the stellar subdivision of a collapsible complexisalwayscollapsible. CompareLemma4.3below. In contrast, an arbitrary subdivision might destroy some combinatorial properties. For example, although the3-simplex is shellable, there exists subdivisions ofthe 3-simplex that are neither shellable, nor collapsible, nor endo-collapsible. Also, if S is the double suspension of the Poincare´ homology sphereandD isa5-simplexofS,thed-ballS−D isanon-PLsubdivision ofthe5-simplex. 7 3 The combinatorics of handles HereweshowthatanarbitraryPLtriangulationofanyhandlehasaconvenientsubdivision,thatpreserves someofthecombinatorial properties oftheoriginalboundary. Westartbyrecalling twoclassical resultsfromthelecturenotesbyZeeman[54]: Lemma3.1(Zeeman[54,Lemma13]). IfBisaPL(d−1)-ballintheboundaryofaPLd-ballA,there exists an integer r and a subdivision of A that collapses onto the r-th derived subdivision of B. This subdivision ofAneednotbestellar. Proof. Let D be the d-simplex and G a (d−1)-face of it. By the definition of PL, we can find subdi- visions A′,B′,D ′,G ′ and asimplicial isomorphism h:A′→D ′ whose restriction to B′ yields a simplicial isomorphism betweenB′ andG ′. Let p : D → G be the linear (“vertical”) projection, mapping the vertex opposite to G to the down barycenter ofG . Choosesubdivisions D ′′,G ′′ ofD ′,G ′ suchthatp :D ′′→G ′′ issimplicial. LetA′′,B′′ down be the isomorphic subdivisions of A′,B′. For a sufficiently large integer r, an r-th derived subdivision B′′′ :=sdrB ofBwill subdivide also B′′. LetG ′′′ be the subdivision of G ′′ corresponding to B′′′. Wecan extend G ′′′ to a subdivision D ′′′ of D ′′, such that the projection p :D ′′′ →G ′′′ is simplicial. Finally, down letA′′′ bethesubdivision ofA′′ corresponding toD ′′′. Byconstruction, D ′′′ collapses vertically toG ′′′,in decreasing orderofdimension. Hence,A′′′ collapses ontoB′′′. Proposition3.2(Zeeman). EveryPLballadmitsacollapsible subdivision. Proof. Choosea(d−1)-simplexBintheboundary ofthed-ballA,andapplyLemma3.1: Somesubdi- visionA′ofAwillcollapseontoanr-thderivedsubdivisionsdrBofB. Suchasubdivision iscollapsible, becausesimplicesarecollapsible andstellarsubdivisions preservecollapsibility. Remark3.3. ThepreviousresultswereusedbyZeemantoshowthatthetwonotionsofPL-collapsibility and simplicial collapsibility are equivalent up to subdividing [54, Theorem 4] [31, p. 12]. In fact, if a polyhedronC PL-collapses onto apolyhedron D, then using Lemma3.1 one can prove the existence of aninteger r and ofa subdivisionC′ ofC such thatC′ isasimplicial complex that collapses simplicially ontother-thderivedsubdivision ofD. Recall that shellable manifolds are collapsible and endo-collapsible at the same time [6]. In the Seventies,Proposition 3.2wasstrengthened byBruggesser andManiasfollows: Proposition 3.4 (Bruggesser–Mani). Every d-dimensional PL ball admits a shellable subdivision with shellable boundary. Proof. IfAisad-dimensional PLball,thereexistsanintegerrforwhichther-thderivedsubdivision of thed-simplexisalsoasubdivision ofA. Sincethesimplexanditsboundary areshellable, soarether-th derivedsubdivision ofthesimplexanditsboundary. BothProposition 3.2andProposition 3.4claimthatsomenicesubdivision exists, butdonotspecify how to get it. It is natural to ask whether a collapsible or shellable subdivision can always be reached justbyperforming barycentric subdivisions. Unfortunately, thisisanopenproblem. Conjecture 3.5. For every PL ball B there is an integer r such that the r-th derived subdivision of B is shellable. Theconjecture seemscrucialforthetopological application wehaveinmind,namely, totriangulate anyhandledecomposition ‘onehandleatthetime’. Theplanwehaveinmindistotriangulateeachhan- dleH starting from atriangulation T oftheintersection ofH withtheprevious handles. Topologically, i i i 8 H ad-ball andT isa(d−1)-submanifold ofitsboundary. IfT istriangulated nicely andH isnot, can i i i i we fix the triangulation of H without touching T (or maybe, by subdividing T gently, so that the nice i i i combinatorial properties ofT aremaintained)? Hereistheproblem: i — ByProposition3.4,weknowthatsomesubdivisionmakesH shellable. However,anarbitrarysubdi- i vision canmakeanon-shellable complex shellable, but alsotheotherwayaround. Therefore, inthe process of subdividing H into a shellable complex, the subcomplex T of ¶ H might get subdivided i i i “badly”. — Ifinsteadweuse“standard”subdivisions, likethebarycentricorastellarsubdivision, the“niceness” of T is preserved (cf. Lemma 4.3 below). However, unless Conjecture 3.5 is proven, there is no i guarantee thatwewilleventually succeedinmakingH shellable orendo-collapsible. i Wesolvethedilemmawithahybridapproach. Weshowtheexistenceofsome(non-standard)subdivision ofH that(1)makesH endo-collapsible, and(2)whenrestrictedtotheboundaryofthehandle,coincides i i withaderivedsubdivision. Firstofall,weneedaLemmaonhowtosubdividecylinders,whichsomewhatresemblesLemma3.1. Lemma 3.6. Let C be a PL d-manifold homeomorphic to Sd−1×I. Let C and C be the two top bottom connected components of¶ C. Thereexistintegers r,sandsomesubdivisionC′ ofC suchthat: (i) TheboundaryofC′consistsoftwoconnectedcomponentsC′ andC′ ,whereC′ isther-th bottom top bottom derivedsubdivision ofC andC′ isthes-thderived subdivision of¶ D d. bottom top (ii) C′ simplicially collapses ontoC′ . bottom Proof. LetGbe(¶ D d)×I. Theboundary ofGconsistsoftwoconnected components, G andG , bottom top bothhomeomorphictoSd−1. WechoosesubdivisionsC′ andG′sothatthereisasimplicialisomorphism h fromC′ to G′, which restricts to an isomorphism betweenC′ and G′ (and also to an isomorphism top top between C′ and G′ ). Without loss of generality, we can assume that C′ is the s-th derived bottom bottom top subdivision of¶ D d,forsomes. (Ifnot,wechooseslargeenoughsothatsds¶ D d isasubdivision ofC′ top andwereplaceC′ withsomefinertriangulation whoserestriction tothetopfaceissds¶ D d.) Letusdenote byp thevertical projection from GtoG . Ingeneral p isnot asimplicial down bottom down map, but we can make it simplicial by refining the triangulation, that is, by passing to a suitable subdi- vision G′′of G′. Therefinement can be done without subdividing the top faces ofG′, sowecan assume that G′′ = G′ . Using the isomorphism h, we can pull-back G′′ to a subdivision C′′ of C′. Clearly top top C′′ =C′ =sds¶ D d. top top Finally, for r large enough the r-th derived subdivision ofC subdivides C′′ . This derived bottom bottom subdivision ispushedforwardviahtoasubdivision ofG′′ ,whichcanbeextendedtoatriangulation bottom G′′′ofG,sothattheprojectionp issimplicial. WecanassumeG′′′ =G′′ ,becauseinordertomake down top top theverticalprojectionsimplicialthereisnoneedtosubdividethetopfacesofG′′. Ifwepull-backG′′′ to asubdivisionC′′′ ofC,wehavethat: (i) The boundary ofC′′′ consists of two connected componentsC′′′ andC′′′ , whereC′′′ is the top bottom bottom r-thderivedsubdivision ofC andC′′′ =C′′ =C′ =sds¶ D d. bottom top top top (ii) C′′′ simplicially collapsesontoC′′′ ,becauseG′′′ collapses vertically ontoG′′′ . bottom bottom Proposition3.7. EveryPLd-ballBadmitssomesubdivision B′ withthefollowingtwoproperties: (i) B′ isendo-collapsible, and (ii) ¶ B′ isther-thderivedsubdivision of¶ B,forasuitabler. Proof. Uptoreplacing Bwithitssecondbarycentric subdivision, wecanassumethatsomefacetD ofB isdisjoint from¶ B. ApplyingLemma3.6toC := B−D ,wecanfindasubdivisionC′ ofCsuchthat: (i) The boundary ofC′ consists of two connected components C′ and C′ , where C′ is the bottom top bottom r-thderivedsubdivision of¶ BandC′ isthes-thderivedsubdivision of¶ D d. top 9 (ii) C′ simplicially collapses ontoC′ . bottom LetD′ bethed-ballobtainedbytakingaconeoverC′ =sds¶ D d. ByglueingD′ ontoC′alongC′ , top top we can completeC′ to a triangulation B′ :=C′∪D′ of B. Let S be a facet of D′. Being a cone over an endo-collapsiblesphere,D′isendo-collapsible[6,Theorem4.9],whichmeansthatD′−S collapsesonto C′ . Thelatter collapsing sequence can alsobe viewedasacollapse of B′−S ontoC′. ByLemma3.6, top C′ collapses ontoC′ =sdr¶ B, which is also the boundary of B′. Therefore, B′−S collapses onto bottom ¶ B′,whichmeansthatB′ isendo-collapsible. Remark3.8. Manytriangulationsof3-ballsareneithercollapsiblenorendo-collapsible[6]. These“bad” triangulations usually contain complicated knots assubcomplexes withfewedges. In[7]weintroduced ameasure ofcomplicatedness for knots, which istheminimal number ofgenerators for theknot group, minus one. For example, the connected sum of m trefoil knots is m-complicated [26]. In an arbitrary 3-ball, any m-complicated knot can be realized with only 3edges. Incontrast, in a collapsible or endo- collapsible 3-ball, thereisnom-complicated knotthatuseslessthanmedges[6]. When we perform a subdivision, the complicatedness of the knot stays the same, while the edge numbermightincrease. Intuitively,asufficientlyfinesubdivisionwillmaketheknot-theoretical obstruc- tion disappear. Howewer, there is no universal upper bound on how fine this subdivision should be. In fact, for each positive integert, consider a PL3-sphere S with a 3-edge knotted subcomplex isotopic to the sum of 3·2t trefoils. Since it contains an (3·2t)-complicated knot on 3·2t edges, any t-th derived subdivision ofScannotbeendo-collapsible. Remark3.9. AsimilarstatementtoLemma3.6appears alsointheworkbyGallais[24,Lemma3.9]: Given a d-simplex D d and an arbitrary subdivision X of D , one can construct a triangu- 0 d lation X ofthe full cylinder D d×Isuch that the‘bottom’ ofthe cylinder iscombinatorially equivalent to X , the ‘top’ is combinatorially equivalent to D , and X collapses to the top 0 d andtothebottom. Unfortunately, the proof presented in [24, p. 240] is incorrect in its “Step 3”: It is not true that any simplicial subdivision X of the d-simplex is collapsible. There are explicit counterexamples already 0 when d =3: Forexample, take X =S−D , where S is the non-shellable 3-sphere constructed by Lick- 0 orish [37]. In higher dimensions, the situation gets even more complicated, since the 5-simplex admits subdivisions that are not collapsible and not even PL. In particular, the triangulation X constructed in [24, p. 240], which is acone over the CWcomplex X ∪D ∪(I׶ D ), might not collapse down toits 0 d d bottomX . 0 At present, we do not know whether the claim [24, Lemma 3.9] is still true (with a different con- struction for X , say). However, the main results in [24] can be savaged, (for example) using stellar 0 subdivisions andtheideasexplained inthepresentpaper. 4 Main Results We start by recalling how to compose two discrete Morse functions together [6, Theorem 3.18]. Given a discrete Morse function f on a manifold with boundary M, let cint(f) denote the number of critical i i-facesof f intheinterior ofM. Theorem 4.1 ([6, Theorem 3.18]). Let M =M ∪M be three d-manifolds, d ≥2, such that the M’s 1 2 i have non-empty boundary and M ∩M is a full-dimensional submanifold of ¶ M (i=1,2). Let f and 1 2 i g be boundary-critical discrete Morse functions on M and M , respectively, with cint(f)=cint(g)=1. 1 2 d d 10