Combinatorial Algebraic Topology (Algorithms and Computation in Mathematics)

Cover......Page 1
Algorithms and Computation in Mathematics Volume 21......Page 2
Combinatorial Algebraic Topology......Page 4
9783540719618......Page 5
Preface......Page 8
Contents......Page 12
1 Overture......Page 22
Part I Concepts of Algebraic Topology......Page 26
2.1.1 Definition of Abstract Simplicial Complexes and Maps Between Them......Page 28
2.1.2 Deletion, Link, Star, and Wedge......Page 31
2.1.4 Face Posets......Page 33
2.1.5 Barycentric and Stellar Subdivisions......Page 34
2.1.6 Pulling and Pushing Simplicial Structures......Page 36
2.2.1 Geometry of Abstract Simplicial Complexes......Page 37
2.2.2 Geometric Meaning of the Combinatorial Constructions......Page 40
2.2.3 Geometric Simplicial Complexes......Page 44
2.2.4 Complexes Whose Cells Belong to a Specified Set of Polyhedra......Page 46
2.3.1 Construction Using the Gluing Data......Page 49
2.3.2 Constructions Involving Trisps......Page 51
2.4.1 Gluing Along a Map......Page 54
2.4.2 Constructive and Intrinsic Definitions......Page 55
2.4.3 Properties and Examples......Page 56
3.1 Betti Numbers of Finite Abstract Simplicial Complexes......Page 58
3.2.1 Homology Groups of Trisps with Coefficients in \mathbb{Z}_2......Page 60
3.2.3 Homology Groups of Trisps with Integer Coefficients......Page 62
3.3.1 Betti Numbers and Torsion Coefficients......Page 65
3.3.2 Euler Characteristic and the Euler–Poincar´e Formula......Page 66
3.4.1 Augmentation and Reduced Homology Groups......Page 67
3.4.3 Simplicial Cohomology Groups......Page 68
3.4.4 Singular Homology......Page 70
3.5.1 Definition and Homology of Chain Complexes......Page 72
3.5.2 Maps Between Chain Complexes and Induced Maps on Homology......Page 73
3.5.3 Chain Homotopy......Page 74
3.5.5 Homomorphisms on Homology Induced by Trisp Maps......Page 75
3.6.1 An Application of Homology with Integer Coefficients: Winding Number......Page 77
3.6.2 The Definition of Cellular Homology......Page 78
3.6.3 Cellular Maps and Properties of Cellular Homology......Page 79
4.1.1 Definition of a Category, Isomorphisms......Page 80
4.1.2 Examples of Categories......Page 81
4.2.1 Initial and Terminal Objects......Page 84
4.2.2 Products and Coproducts......Page 85
4.3.1 The Category Cat......Page 89
4.3.3 Group Actions as Functors......Page 91
4.4.1 Definition of Colimit of a Functor......Page 92
4.4.2 Colimits and Infinite Unions......Page 93
4.4.3 Quotients of Group Actions as Colimits......Page 94
4.5.1 Objects Below and Above Other Objects......Page 95
4.5.2 The General Construction and Further Examples......Page 96
5.1.1 Construction of the Connecting Homomorphism......Page 98
5.1.2 Exact Sequences......Page 100
5.1.3 Deriving Long Exact Sequences from Short Ones......Page 102
5.2.1 Relative Homology and the Associated Long Exact Sequence......Page 103
5.2.2 Applications......Page 105
5.3 Mayer–Vietoris Long Exact Sequence......Page 106
6.1 Homotopy of Maps......Page 110
6.2 Homotopy Type of Topological Spaces......Page 111
6.3 Mapping Cone and Mapping Cylinder......Page 112
6.4 Deformation Retracts and Collapses......Page 114
6.5 Simple Homotopy Type......Page 116
6.6 Homotopy Groups......Page 117
6.7 Connectivity and Hurewicz Theorems......Page 118
7.1 Cofibrations and the Homotopy Extension Property......Page 122
7.2 NDR-Pairs......Page 124
7.3 Important Facts Involving Cofibrations......Page 126
7.4 The Relative Homotopy Equivalence......Page 128
8.1.1 Bundle Terminology......Page 132
8.1.2 Types of Bundles......Page 133
8.1.3 Bundle Maps......Page 134
8.2.1 Principal Bundles and Spaces with a Free Group Action......Page 135
8.2.2 The Classifying Space of a Group......Page 137
8.2.3 Special Cohomology Elements......Page 140
8.2.4 \mathbb{Z}_2-Spaces and the Definition of Stiefel–Whitney Classes......Page 141
8.3.1 Borsuk–Ulam Theorem, Index, and Coindex......Page 143
8.3.3 Higher Connectivity and Stiefel–Whitney Classes......Page 144
8.3.4 Combinatorial Construction of Stiefel–Whitney Classes......Page 145
8.4 Suggested Reading......Page 146
Part II Methods of Combinatorial Algebraic Topology......Page 148
9.1.1 Simplicial Flag Complexes......Page 150
9.1.2 Order Complexes......Page 151
9.1.4 The Neighborhood and Lov´asz Complexes......Page 154
9.1.6 Geometric Complexes in Metric Spaces......Page 155
9.1.7 Combinatorial Presentation by Minimal Nonsimplices......Page 157
9.2.2 Complex of Complete Bipartite Subgraphs......Page 159
9.2.3 Hom Complexes......Page 161
9.2.4 General Complexes of Morphisms......Page 162
9.2.6 The Complex of Phylogenetic Trees......Page 165
9.3 Regular Trisps......Page 166
9.4 Chain Complexes......Page 168
9.5 Bibliographic Notes......Page 169
10.1.1 The Notion of Acyclic Category......Page 172
10.1.2 Linear Extensions of Acyclic Categories......Page 173
10.2.1 Definition and First Examples......Page 174
10.2.2 Functoriality......Page 176
10.3.2 Stacks of Acyclic Categories and Joins of Regular Trisps......Page 177
10.3.3 Links, Stars, and Deletions......Page 179
10.3.4 Lattices and Acyclic Categories......Page 180
10.3.5 Barycentric Subdivision and Δ-Functor......Page 181
10.4.1 Definition and First Properties......Page 182
10.4.2 Acyclic Category of Intervals and Its Structural Functor......Page 185
10.4.3 Topology of the Category of Intervals......Page 188
10.5.1 Simplicial Subdivision of the Direct Product......Page 189
10.5.2 Further Subdivisions......Page 192
10.6.1 Möbius Function for Posets......Page 194
10.6.2 Möbius Function for Acyclic Categories......Page 195
10.7 Bibliographic Notes......Page 199
11.1.1 Acyclic Matchings in Hasse Diagrams of Posets......Page 200
11.1.2 Poset Maps with Small Fibers......Page 203
11.1.3 Universal Object Associated to an Acyclic Matching......Page 204
11.1.4 Poset Fibrations and the Patchwork Theorem......Page 206
11.2.1 Attaching Cells to Homotopy Equivalent Spaces......Page 208
11.2.2 The Main Theorem of Discrete Morse Theory for CW Complexes......Page 210
11.2.3 Examples......Page 213
11.3.1 Acyclic Matchings on Free Chain Complexes and the Morse Complex......Page 222
11.3.2 The Main Theorem of Algebraic Morse Theory......Page 224
11.3.3 An Example......Page 226
11.4 Bibliographic Notes......Page 229
12.1.1 The Basics......Page 232
12.1.2 Shelling Induced Subcomplexes......Page 235
12.1.3 Shelling Nerves of Acyclic Categories......Page 236
12.2.1 Labeling Edges as a Way to Order Chains......Page 237
12.2.2 EL-Labeling......Page 238
12.2.3 General Lexicographic Shellability......Page 240
12.2.4 Lexicographic Shellability and Nerves of Acyclic Categories......Page 244
12.3 Bibliographic Notes......Page 245
13.1.1 Evasiveness of Graph Properties......Page 246
13.1.2 Evasiveness of Abstract Simplicial Complexes......Page 250
13.2.1 Collapsing Sequences Induced by Closure Operators......Page 253
13.2.2 Applications......Page 255
13.2.3 Monotone Poset Maps......Page 257
13.2.4 The Reduction Theorem and Implications......Page 258
13.3.1 NE-Reduction and Collapses......Page 259
13.3.2 Nonevasiveness of Noncomplemented Lattices......Page 261
13.4 Other Recursively Defined Classes of Complexes......Page 263
13.5 Bibliographic Notes......Page 264
14.1.2 Quotients of Simplicial Actions......Page 266
14.2.1 Definition of the Quotient and Formulation of the Main Problem......Page 269
14.2.2 An Explicit Description of the Category C/G......Page 270
14.3.1 Outline of the Results and Surjectivity of the Canonical Map......Page 271
14.3.2 Condition for Injectivity of the Canonical Projection......Page 272
14.3.3 Conditions for the Canonical Projection to be an Isomorphism......Page 273
14.3.4 Conditions for the Categories to be Closed Under Taking Quotients......Page 276
14.4 Bibliographic Notes......Page 278
15.1.1 Diagrams and Colimits......Page 280
15.1.2 Arrow Pictures and Their Nerves......Page 281
15.2.1 Definition and Some Examples......Page 283
15.2.2 Structural Maps Associated to Homotopy Colimits......Page 284
15.3 Deforming Homotopy Colimits......Page 286
15.4.1 Nerve Diagram......Page 287
15.4.2 Projection Lemma......Page 288
15.4.3 Nerve Lemmas......Page 290
15.5.1 Gluing Lemma......Page 292
15.5.2 Quillen Lemma......Page 293
15.6 Bibliographic Notes......Page 294
16.1 Filtrations......Page 296
16.2.1 The Objects to be Constructed......Page 297
16.2.2 The Actual Construction......Page 299
16.2.4 An Example......Page 301
16.3 Maps Between Spectral Sequences......Page 302
16.4.1 A Class of Filtrations......Page 304
16.4.2 Möbius Function and Inequalities for Betti Numbers......Page 306
16.5 Bibliographic Notes......Page 309
Part III Complexes of Graph Homomorphisms......Page 312
17.1.1 The Definition and Applications......Page 314
17.1.2 The Complexity of Computing the Chromatic Number......Page 315
17.1.3 The Hadwiger Conjecture......Page 316
17.2.2 Kneser Graphs as State Graphs and Fractional Chromatic Number......Page 319
17.2.3 The Circular Chromatic Number......Page 321
17.3.1 Formulation of the Kneser Conjecture......Page 322
17.3.2 The Properties of the Neighborhood Complex......Page 323
17.3.3 Lovász Test for Graph Colorings......Page 324
17.3.4 Simplicial and Cubical Complexes Associated to Kneser Graphs......Page 325
17.3.5 The Vertex-Critical Subgraphs of Kneser Graphs......Page 327
17.4 Bibliographic Notes......Page 328
18.1.1 The Morphism Complexes and the Prodsimplicial Flag Construction......Page 330
18.1.2 Universality......Page 332
18.2.1 Coloring Complexes of a Graph......Page 333
18.2.2 Complexes of Bipartite Subgraphs and Neighborhood Complexes......Page 334
18.3.1 Functoriality on the Right......Page 336
18.3.3 Functoriality on the Left......Page 337
18.3.5 Commuting Relations......Page 339
18.4.2 Products......Page 341
18.4.3 Composition of Hom Complexes......Page 343
18.5.1 Definition and First Properties......Page 344
18.5.2 Proof of the Folding Theorem......Page 345
18.6 Bibliographic Notes......Page 347
19.1.1 Powers of Stiefel–Whitney Classes and Chromatic Numbers of Graphs......Page 348
19.1.2 Stiefel–Whitney Test Graphs......Page 349
19.2.1 Complexes of Complete Multipartite Subgraphs......Page 350
19.2.2 Odd Cycles as Stiefel–Whitney Test Graphs......Page 355
19.3 Homology Tests for Graph Colorings......Page 358
19.3.2 The Topological Rationale for the Tests......Page 359
19.3.3 Homology Tests......Page 361
19.3.4 Examples of Homology Tests with Different Test Graphs......Page 362
19.4 Bibliographic Notes......Page 367
20.1.1 Various Definitions......Page 370
20.1.2 Connection to Independence Complexes......Page 372
20.1.3 The Support Map......Page 373
20.1.4 An Example: Hom_+(C_m, K_n)......Page 374
20.2.1 Filtration Induced by the Support Map......Page 375
20.2.3 The First Differential......Page 376
20.3.2 The Corresponding Cohomology Generators......Page 377
20.3.3 The First Reduction......Page 378
20.4.1 Reinterpretation of H*(A*_t ,d_1) Using a Family of Cubical Complexes {Φ_{m,n,g}}......Page 379
20.4.2 The Torus Front Interpretation......Page 381
20.4.3 Grinding......Page 383
20.4.4 Thin Fronts......Page 385
20.4.5 The Implications for the Cohomology Groups of Hom (C_m, K_n)......Page 387
20.5 Euler Characteristic Formula......Page 388
20.6.1 Fixing Orientations on Hom and Hom_+ Complexes......Page 389
20.6.2 Signed Versions of Formulas for Generators [σ^S_V ]......Page 391
20.6.3 Completing the Calculation of the Second Tableau......Page 392
20.6.4 Summary: the Full Description of the Groups \widetilde{H}*(Hom (C_m, K_n); \mathbb{Z})......Page 395
20.7 Bibliographic Notes and Conclusion......Page 397
References......Page 398
Index......Page 406