Simplicial complexes of graphs (Q2459925): Difference between revisions

The subject of this book is the topology of graph complexes. A graph complex is a family of graphs (on a fixed vertex set) which is closed under deletion of edges. Since the vertex set is fixed, each graph in the family \(\Delta\) may be identified with its edge set and \(\Delta\) may be interpreted as a simplicial complex and realized as a geometric object whose topology can be analyzed. A family of graphs, \(\Delta\), is called a graph property if \(\Delta\) is invariant under the action of the symmetric group on the underlying vertex set. Topological and enumerative properties of monotone graph properties such as matchings, forests, bipartite graphs, non-Hamiltonian graphs, not-k-connected graphs are discussed. The twenty-seven chapters of the book are organized into eight parts. Part I provides an overview over the entire volume and introduces the basic concepts such as abstract graphs and set systems, matroids and simplicial topology. Part II introduces the major tools, disctrete Morse theory [\textit{R. Forman}, A discrete Morse theory for cell complexes. Geometry, topology and physics for Raoul Bott. Lectures of a conference in honor of Raoul Bott's 70th birthday, Harvard University, Cambridge, MA, USA 1993. Cambridge, MA: International Press. Conf. Proc. Lect. Notes Geom. Topol. 4, 112--125 (1995; Zbl 0867.57018)]; and decision trees [Combinatorica 20, No.4, 489--504 (2000 Zbl 1028.05110)]. The third part gives an overview of graph complexes by providing lists and illustrations of particular graph properties and spelling out the main goals and proof techniques. Parts IV to VII, titled Vertex Degree, Cycles and Crossings, Connectivity, Cliques and Stable Sets, contain the results promised in the overview, several of them are new, some previously published. Part VIII contains a list of well formulated open problems, organized by the chapter to which they are related or where they were previously stated. In some cases conjectures are provided. Readers who mastered parts I-VII will tackle these problems to test their mastery. Researchers, who find any of the stated problems intriguing, will be enticed to read the book.