Simplicial complexes of graphs

Jakob Jonsson (auth.)3540758585, 9783540758587

A graph complex is a finite family of graphs closed under deletion of edges. Graph complexes show up naturally in many different areas of mathematics, including commutative algebra, geometry, and knot theory. Identifying each graph with its edge set, one may view a graph complex as a simplicial complex and hence interpret it as a geometric object. This volume examines topological properties of graph complexes, focusing on homotopy type and homology.

Many of the proofs are based on Robin Forman’s discrete version of Morse theory. As a byproduct, this volume also provides a loosely defined toolbox for attacking problems in topological combinatorics via discrete Morse theory. In terms of simplicity and power, arguably the most efficient tool is Forman’s divide and conquer approach via decision trees; it is successfully applied to a large number of graph and digraph complexes.

Table of contents :
Front Matter….Pages i-xiv
Introduction and Overview….Pages 3-17
Abstract Graphs and Set Systems….Pages 19-28
Simplicial Topology….Pages 29-47
Discrete Morse Theory….Pages 51-66
Decision Trees….Pages 67-86
Miscellaneous Results….Pages 87-95
Graph Properties….Pages 99-106
Dihedral Graph Properties….Pages 107-112
Digraph Properties….Pages 113-118
Main Goals and Proof Techniques….Pages 119-124
Matchings….Pages 127-149
Graphs of Bounded Degree….Pages 151-168
Forests and Matroids….Pages 171-188
Bipartite Graphs….Pages 189-204
Directed Variants of Forests and Bipartite Graphs….Pages 205-215
Noncrossing Graphs….Pages 217-231
Non-Hamiltonian Graphs….Pages 233-242
Disconnected Graphs….Pages 245-262
Not 2-connected Graphs….Pages 263-273
Not 3-connected Graphs and Beyond….Pages 275-290
Dihedral Variants of k -connected Graphs….Pages 291-300
Directed Variants of Connected Graphs….Pages 301-308
Not 2-edge-connected Graphs….Pages 309-325
Graphs Avoiding k -matchings….Pages 329-331
t -colorable Graphs….Pages 333-335
Graphs and Hypergraphs with Bounded Covering Number….Pages 337-354
Open Problems….Pages 357-362
Back Matter….Pages 363-382