72 III ComplexesExercisesThe credit assignment reflects a subjective assessment of difficulty. A typicalquestion can be answered using knowledge of the material combined with somethought and analysis.1. Deciding isomorphism (three credits). What is the computational com-plexity of recognizing isomorphic abstract simplicial complexes?2. Order complex (two credits). A flag in a simplicial complex K in Rdisa nested sequence of proper faces, σ0< σ1< . . . < σk. The collection offlags form an abstract simplicial complex A sometimes referred to as theorder complex of K. Prove that A has a geometric realization in Rd.3. Barycentric subdivision (one credit). Let K consist of a d-simplex σand its faces.(i) How many d-simplexes belong to the barycentric subdivision, SdK?(ii) What is the d-dimensional volume of the individual d-simplices inSdK?4. Covering a tree (one credit). Let P be a finite collection of closed pathsthat cover a tree, that is, each node and each edge of the tree belongs toat least one path.(i) Prove that the nerve of P is contractible.(ii) Is the nerve still contractible if we allow subtrees in the collection?What about sub-forests?5. Nerve of stars (one credit). Let K be a simplicial complex.(i) Prove that K is a geometric realization of the nerve of the collectionof vertex stars in K.(ii) Prove that SdK is a geometric realization of the nerve of the collectionof stars in K.6. Helly for boxes (two credits). The box defined by two points a =(a1, a2, . . . , ad) and b = (b1, b2, . . . , bd) in Rdconsists of all points x whosecoordinates satisfy ai≤ xi≤ bifor all i. Let F be a finite collection ofboxes in Rd. Prove that if every pair of boxes has a non-empty intersectionthen the entire collection has a non-empty intersection.7. Alpha complexes (two credits). Let S ⊆ Rdbe a finite set of pointsin general position. Recall thatˇCech(r) and Alpha(r) are theˇCechExercises 73and alpha complexes for radius r ≥ 0. Is it true that Alpha(r) =ˇCech(r) ∩ Delaunay? If yes, prove the following two subcomplex relations.If no, give examples to show which subcomplex relations are not valid.(i) Alpha(r) ⊆ˇCech(r) ∩ Delaunay.(ii)ˇCech(r) ∩ Delaunay ⊆ Alpha(r).8. Collapsibility (three credits). Call a simplicial complex collapsible if thereis a sequence of collapses that reduce the complex to a single vertex. Theexistence of such a sequence implies that the underlying space of the com-plex is contractible. Describe a finite 2-dimensional simplicial complexthat is not collapsible although its underlying space is
View Full Document
Unlocking...