Combinatorial algebraic topology / Dmitry Kozlov.

Format:

Book

Author/Creator:

Kozlov, D. N. (Dmitriĭ Nikolaevich)

Contributor:

Class of 1932 Fund.

Series:

Algorithms and computation in mathematics ; v. 21.

Algorithms and computation in mathematics, 1431-1550 ; v. 21

Language:

English

Subjects (All):

Algebra, Homological.

Categories (Mathematics).

Algebraic topology.

Combinatorial topology.

Physical Description:

xix, 389 pages : illustrations ; 24 cm.

Place of Publication:

Berlin ; New York : Springer, [2008]

Summary:

Combinatorial algebraic topology is a fascinating and dynamic field at the crossroads of algebraic topology and discrete mathematics. This volume is the first comprehensive treatment of the subject in book form. The first part of the book constitutes a swift walk through the main tools of algebraic topology, including Stiefel-Whitney characteristic classes, which are needed for the later parts. Readers - graduate students and working mathematicians alike - will probably find particularly useful the second part, which contains an in-depth discussion of the major research techniques of combinatorial algebraic topology. Our presentation of standard topics is quite different from that of existing texts. In addition, several new themes, such as spectral sequences, are included. Although applications are sprinkled throughout the second part, they are principal focus of the third part, which is entirely devoted to developing the topological structure theory for graph homomorphisms. The main benefit for the reader will be the prospect of fairly quickly getting to the forefront of modern research in this active field.

Contents:

1 Overture 1

Part I Concepts of Algebraic Topology

2 Cell Complexes 7

2.1 Abstract Simplicial Complexes 7

2.1.1 Definition of Abstract Simplicial Complexes and Maps Between Them 7

2.1.2 Deletion, Link, Star, and Wedge 10

2.1.3 Simplicial Join 12

2.1.4 Face Posets 12

2.1.5 Barycentric and Stellar Subdivisions 13

2.1.6 Pulling and Pushing Simplicial Structures 15

2.2 Polyhedral Complexes 16

2.2.1 Geometry of Abstract Simplicial Complexes 16

2.2.2 Geometric Meaning of the Combinatorial Constructions 19

2.2.3 Geometric Simplicial Complexes 23

2.2.4 Complexes Whose Cells Belong to a Specified Set of Polyhedra 25

2.3 Trisps 28

2.3.1 Construction Using the Gluing Data 28

2.3.2 Constructions Involving Trisps 30

2.4 CW Complexes 33

2.4.1 Gluing Along a Map 33

2.4.2 Constructive and Intrinsic Definitions 34

2.4.3 Properties and Examples 35

3 Homology Groups 37

3.1 Betti Numbers of Finite Abstract Simplicial Complexes 37

3.2 Simplicial Homology Groups 39

3.2.1 Homology Groups of Trisps with Coefficients in Z[subscript 2] 39

3.2.2 Orientations 41

3.2.3 Homology Groups of Trisps with Integer Coefficients 41

3.3 Invariants Connected to Homology Groups 44

3.3.1 Betti Numbers and Torsion Coefficients 44

3.3.2 Euler Characteristic and the Euler-Poincare Formula 45

3.4 Variations 46

3.4.1 Augmentation and Reduced Homology Groups 46

3.4.2 Homology Groups with Other Coefficients 47

3.4.3 Simplicial Cohomology Groups 47

3.4.4 Singular Homology 49

3.5 Chain Complexes 51

3.5.1 Definition and Homology of Chain Complexes 51

3.5.2 Maps Between Chain Complexes and Induced Maps on Homology 52

3.5.3 Chain Homotopy 53

3.5.4 Simplicial Homology and Cohomology in the Context of Chain Complexes 54

3.5.5 Homomorphisms on Homology Induced by Trisp Maps 54

3.6 Cellular Homology 56

3.6.1 An Application of Homology with Integer Coefficients: Winding Number 56

3.6.2 The Definition of Cellular Homology 57

3.6.3 Cellular Maps and Properties of Cellular Homology 58

4 Concepts of Category Theory 59

4.1 The Notion of a Category 59

4.1.1 Definition of a Category, Isomorphisms 59

4.1.2 Examples of Categories 60

4.2 Some Structure Theory of Categories 63

4.2.1 Initial and Terminal Objects 63

4.2.2 Products and Coproducts 64

4.3 Functors 68

4.3.1 The Category Cat 68

4.3.2 Homology and Cohomology Viewed as Functors 70

4.3.3 Group Actions as Functors 70

4.4 Limit Constructions 71

4.4.1 Definition of Colimit of a Functor 71

4.4.2 Colimits and Infinite Unions 72

4.4.3 Quotients of Group Actions as Colimits 73

4.4.4 Limits 74

4.5 Comma Categories 74

4.5.1 Objects Below and Above Other Objects 74

4.5.2 The General Construction and Further Examples 75

5 Exact Sequences 77

5.1 Some Structure Theory of Long and Short Exact Sequences 77

5.1.1 Construction of the Connecting Homomorphism 77

5.1.2 Exact Sequences 79

5.1.3 Deriving Long Exact Sequences from Short Ones 81

5.2 The Long Exact Sequence of a Pair and Some Applications 82

5.2.1 Relative Homology and the Associated Long Exact Sequence 82

5.2.2 Applications 84

5.3 Mayer-Vietoris Long Exact Sequence 85

6 Homotopy 89

6.1 Homotopy of Maps 89

6.2 Homotopy Type of Topological Spaces 90

6.3 Mapping Cone and Mapping Cylinder 91

6.4 Deformation Retracts and Collapses 93

6.5 Simple Homotopy Type 95

6.6 Homotopy Groups 96

6.7 Connectivity and Hurewicz Theorems 97

7 Cofibrations 101

7.1 Cofibrations and the Homotopy Extension Property 101

7.2 NDR-Pairs 103

7.3 Important Facts Involving Cofibrations 105

7.4 The Relative Homotopy Equivalence 107

8 Principal [Gamma]-Bundles and Stiefel-Whitney Characteristic Classes 111

8.1 Locally Trivial Bundles 111

8.1.1 Bundle Terminology 111

8.1.2 Types of Bundles 112

8.1.3 Bundle Maps 113

8.2 Elements of the Principal Bundle Theory 114

8.2.1 Principal Bundles and Spaces with a Free Group Action 114

8.2.2 The Classifying Space of a Group 116

8.2.3 Special Cohomology Elements 119

8.2.4 Z[subscript 2]-Spaces and the Definition of Stiefel-Whitney Classes 120

8.3 Properties of Stiefel-Whitney Classes 122

8.3.1 Borsuk-Ulam Theorem, Index, and Coindex 122

8.3.2 Stiefel-Whitney Height 123

8.3.3 Higher Connectivity and Stiefel-Whitney Classes 123

8.3.4 Combinatorial Construction of Stiefel-Whitney Classes 124

Part II Methods of Combinatorial Algebraic Topology

9 Combinatorial Complexes Melange 129

9.1 Abstract Simplicial Complexes 129

9.1.1 Simplicial Flag Complexes 129

9.1.2 Order Complexes 130

9.1.3 Complexes of Combinatorial Properties 133

9.1.4 The Neighborhood and Lovasz Complexes 133

9.1.5 Complexes Arising from Matroids 134

9.1.6 Geometric Complexes in Metric Spaces 134

9.1.7 Combinatorial Presentation by Minimal Nonsimplices 136

9.2 Prodsimplicial Complexes 138

9.2.1 Prodsimplicial Flag Complexes 138

9.2.2 Complex of Complete Bipartite Subgraphs 138

9.2.3 Hom Complexes 140

9.2.4 General Complexes of Morphisms 141

9.2.5 Discrete Configuration Spaces of Generalized Simplicial Complexes 144

9.2.6 The Complex of Phylogenetic Trees 144

9.3 Regular Trisps 145

9.4 Chain Complexes 147

10 Acyclic Categories 151

10.1.1 The Notion of Acyclic Category 151

10.1.2 Linear Extensions of Acyclic Categories 152

10.1.3 Induced Subcategories of Cat 153

10.2 The Regular Trisp of Composable Morphism Chains in an Acyclic Category 153

10.2.1 Definition and First Examples 153

10.2.2 Functoriality 155

10.3 Constructions 156

10.3.1 Disjoint Union as a Coproduct 156

10.3.2 Stacks of Acyclic Categories and Joins of Regular Trisps 156

10.3.3 Links, Stars, and Deletions 158

10.3.4 Lattices and Acyclic Categories 159

10.3.5 Barycentric Subdivision and [Delta]-Functor 160

10.4 Intervals in Acyclic Categories 161

10.4.1 Definition and First Properties 161

10.4.2 Acyclic Category of Intervals and Its Structural Functor 164

10.4.3 Topology of the Category of Intervals 167

10.5 Homeomorphisms Associated with the Direct Product Construction 168

10.5.1 Simplicial Subdivision of the Direct Product 168

10.5.2 Further Subdivisions 171

10.6 The Mobius Function 173

10.6.1 Mobius Function for Posets 173

10.6.2 Mobius Function for Acyclic Categories 174

11 Discrete Morse Theory 179

11.1 Discrete Morse Theory for Posets 179

11.1.1 Acyclic Matchings in Hasse Diagrams of Posets 179

11.1.2 Poset Maps with Small Fibers 182

11.1.3 Universal Object Associated to an Acyclic Matching 183

11.1.4 Poset Fibrations and the Patchwork Theorem 185

11.2 Discrete Morse Theory for CW Complexes 187

11.2.1 Attaching Cells to Homotopy Equivalent Spaces 187

11.2.2 The Main Theorem of Discrete Morse Theory for CW Complexes 189

11.3 Algebraic Morse Theory 201

11.3.1 Acyclic Matchings on Free Chain Complexes and the Morse Complex 201

11.3.2 The Main Theorem of Algebraic Morse Theory 203

12 Lexicographic Shellability 211

12.1 Shellability 211

12.1.2 Shelling Induced Subcomplexes 214

12.1.3 Shelling Nerves of Acyclic Categories 215

12.2 Lexicographic Shellability 216

12.2.1 Labeling Edges as a Way to Order Chains 216

12.2.2 EL-Labeling 217

12.2.3 General Lexicographic Shellability 219

12.2.4 Lexicographic Shellability and Nerves of Acyclic Categories 223

13 Evasiveness and Closure Operators 225

13.1 Evasiveness 225

13.1.1 Evasiveness of Graph Properties 225

13.1.2 Evasiveness of Abstract Simplicial Complexes 229

13.2 Closure Operators 232

13.2.1 Collapsing Sequences Induced by Closure Operators 232

13.2.2 Applications 234

13.2.3 Monotone Poset Maps 236

13.2.4 The Reduction Theorem and Implications 237

13.3 Further Facts About Nonevasiveness 238

13.3.1 NE-Reduction and Collapses 238

13.3.2 Nonevasiveness of Noncomplemented Lattices 240

13.4 Other Recursively Defined Classes of Complexes 242

14 Colimits and Quotients 245

14.1 Quotients of Nerves of Acyclic Categories 245

14.1.1 Desirable Properties of the Quotient Construction 245

14.1.2 Quotients of Simplicial Actions 245

14.2 Formalization of Group Actions and the Main Question 248

14.2.1 Definition of the Quotient and Formulation of the Main Problem 248

14.2.2 An Explicit Description of the Category C/G 249

14.3 Conditions on Group Actions 250

14.3.1 Outline of the Results and Surjectivity of the Canonical Map 250

14.3.2 Condition for Injectivity of the Canonical Projection 251

14.3.3 Conditions for the Canonical Projection to be an Isomorphism 252

14.3.4 Conditions for the Categories to be Closed Under Taking Quotients 255

15 Homotopy Colimits 259

15.1 Diagrams over Trisps 259

15.1.1 Diagrams and Colimits 259

15.1.2 Arrow Pictures and Their Nerves 260

15.2 Homotopy Colimits 262

15.2.1 Definition and Some Examples 262

15.2.2 Structural Maps Associated to Homotopy Colimits 263

15.3 Deforming Homotopy Colimits 265

15.4 Nerves of Coverings 266

15.4.1 Nerve Diagram 266

15.4.2 Projection Lemma 267

15.4.3 Nerve Lemmas 269

15.5 Gluing Spaces 271

15.5.1 Gluing Lemma 271

15.5.2 Quillen Lemma 272

16 Spectral Sequences 275

16.1 Filtrations 275

16.2 Contriving Spectral Sequences 276

16.2.1 The Objects to be Constructed 276

16.2.2 The Actual Construction 278

16.2.3 Questions of Convergence and Interpretation of the Answer 280

16.3 Maps Between Spectral Sequences 281

16.4 Spectral Sequences and Nerves of Acyclic Categories 283

16.4.1 A Class of Filtrations 283

16.4.2 Mobius Function and Inequalities for Betti Numbers 285

Part III Complexes of Graph Homomorphisms

17 Chromatic Numbers and the Kneser Conjecture 293

17.1 The Chromatic Number of a Graph 293

17.1.1 The Definition and Applications 293

17.1.2 The Complexity of Computing the Chromatic Number 294

17.1.3 The Hadwiger Conjecture 295

17.2 State Graphs and the Variations of the Chromatic Number 298

17.2.1 Complete Graphs as State Graphs 298

17.2.2 Kneser Graphs as State Graphs and Fractional Chromatic Number 298

17.2.3 The Circular Chromatic Number 300

17.3 Kneser Conjecture and Lovasz Test 301

17.3.1 Formulation of the Kneser Conjecture 301

17.3.2 The Properties of the Neighborhood Complex 302

17.3.3 Lovasz Test for Graph Colorings 303

17.3.4 Simplicial and Cubical Complexes Associated to Kneser Graphs 304

17.3.5 The Vertex-Critical Subgraphs of Kneser Graphs 306

17.3.6 Chromatic Numbers of Kneser Hypergraphs 307

18 Structural Theory of Morphism Complexes 309

18.1 The Scope of Morphism Complexes 309

18.1.1 The Morphism Complexes and the Prodsimplicial Flag Construction 309

18.1.2 Universality 311

18.2 Special Families of Hom Complexes 312

18.2.1 Coloring Complexes of a Graph 312

18.2.2 Complexes of Bipartite Subgraphs and Neighborhood Complexes 313

18.3 Functoriality of Hom (-, -) 315

18.3.1 Functoriality on the Right 315

18.3.2 Aut (G) Action on Hom (T, G) 316

18.3.3 Functoriality on the Left 316

18.3.4 Aut (T) Action on Hom (T, G) 318

18.3.5 Commuting Relations 318

18.4 Products, Compositions, and Hom Complexes 320

18.4.1 Coproducts 320

18.4.2 Products 320

18.4.3 Composition of Hom Complexes 322

18.5 Folds 323

18.5.1 Definition and First Properties 323

18.5.2 Proof of the Folding Theorem 324

19 Characteristic Classes and Chromatic Numbers 327

19.1 Stiefel-Whitney Characteristic Classes and Test Graphs 327

19.1.1 Powers of Stiefel-Whitney Classes and Chromatic Numbers of Graphs 327

19.1.2 Stiefel-Whitney Test Graphs 328

19.2 Examples of Stiefel-Whitney Test Graphs 329

19.2.1 Complexes of Complete Multipartite Subgraphs 329

19.2.2 Odd Cycles as Stiefel-Whitney Test Graphs 334

19.3 Homology Tests for Graph Colorings 337

19.3.1 The Symmetrizer Operator and Related Structures 338

19.3.2 The Topological Rationale for the Tests 338

19.3.3 Homology Tests 340

19.3.4 Examples of Homology Tests with Different Test Graphs 341

20 Applications of Spectral Sequences to Hom Complexes 349

20.1 Hom[subscript +] Construction 349

20.1.1 Various Definitions 349

20.1.2 Connection to Independence Complexes 351

20.1.3 The Support Map 352

20.1.4 An Example: Hom[subscript +] (C[subscript m], K[subscript n]) 353

20.2 Setting up the Spectral Sequence 354

20.2.1 Filtration Induced by the Support Map 354

20.2.2 The 0th and the 1st Tableaux 355

20.2.3 The First Differential 355

20.3 Encoding Cohomology Generators by Arc Pictures 356

20.3.1 The Language of Arcs 356

20.3.2 The Corresponding Cohomology Generators 356

20.3.3 The First Reduction 357

20.4 Topology of the Torus Front Complexes 358

20.4.1 Reinterpretation of H (A[subscript t], d[subscript 1]) Using a Family of Cubical Complexes {[Phi subscript m, n, g]} 358

20.4.2 The Torus Front Interpretation 360

20.4.3 Grinding 362

20.4.4 Thin Fronts 364

20.4.5 The Implications for the Cohomology Groups of Hom (C[subscript m], K[subscript n]) 366

20.5 Euler Characteristic Formula 367

20.6 Cohomology with Integer Coefficients 368

20.6.1 Fixing Orientations on Hom and Hom[subscript +] Complexes 368

20.6.2 Signed Versions of Formulas for Generators [Characters not reproducible] 370

20.6.3 Completing the Calculation of the Second Tableau 371

20.6.4 Summary: the Full Description of the Groups H (Hom (C[subscript m], K[subscript n]); Z) 374.

Notes:

Includes bibliographical references (pages [377]-384) and index.

Local Notes:

Acquired for the Penn Libraries with assistance from the Class of 1932 Fund.

ISBN:

9783540719618

354071961X

OCLC:

185096383