Complexes of not i-connected graphs

DOI10.1016/S0040-9383(98)00009-3zbMATH Open0936.57002arXivmath/9705219MaRDI QIDQ1292680FDOQ1292680

Authors: John Shareshian, Eric Babson, Anders Bjoerner, Svante Linusson, Volkmar Welker 

Publication date: 2 September 1999

Published in: Topology (Search for Journal in Brave)

Abstract: Complexes of (not) connected graphs, hypergraphs and their homology appear in the construction of knot invariants given by V. Vassiliev. In this paper we study the complexes of not $i$-connected $k$-hypergraphs on $n$ vertices. We show that the complex of not $2$-connected graphs has the homotopy type of a wedge of $(n-2)!$ spheres of dimension $2n-5$. This answers one of the questions raised by Vassiliev in connection with knot invariants. For this case the $S_n$-action on the homology of the complex is also determined. For complexes of not $2$-connected $k$-hypergraphs we provide a formula for the generating function of the Euler characteristic, and we introduce certain lattices of graphs that encode their topology. We also present partial results for some other cases. In particular, we show that the complex of not $(n-2)$-connected graphs is Alexander dual to the complex of partial matchings of the complete graph. For not $(n-3)$-connected graphs we provide a formula for the generating function of the Euler characteristic.

Full work available at URL: https://arxiv.org/abs/math/9705219

Recommendations

• Complexes of connected graphs
• Complexes of graphs with bounded independence number
• Complexes of graphs with bounded independence number
• Complexes of graph homomorphisms
• Links in the complex of separable graphs
• On the connectivity of infinite graphs and 2-complexes
• Simplicial complexes of graphs
• Complexes oft-Colorable Graphs
• Homologies of complexes of doubly connected graphs
• On connectivity of the facet graphs of simplicial complexes

zbMATH Keywords

Euler characteristics

Mathematics Subject Classification ID

Connectivity (05C40) Classification of homotopy type (55P15) Relations of low-dimensional topology with graph theory (57M15)

Cited In (35)

• Rational homology of spaces of complex monic polynomials with multiple roots
• On the topology of simplicial complexes related to 3-connected and Hamiltonian graphs
• On efficient sparse integer matrix Smith normal form computations
• Equivariant discrete Morse theory
• Topology of bounded-degree graph complexes.
• Some results related to the evasiveness conjecture.
• Discrete Morse theory and classifying spaces
• On the 3-torsion part of the homology of the chessboard complex
• Cycle-free chessboard complexes and symmetric homology of algebras
• On optimizing discrete Morse functions
• The integral tree representation of the symmetric group
• Complexes of graphs with bounded matching size
• Homotopy of non-modular partitions and the Whitehouse module
• Matching complexes, bounded degree graph complexes, and weight spaces of \(\mathrm{GL}_n\)-complexes
• Torsion in the matching complex and chessboard complex
• Complexes of discrete Morse functions
• Exact sequences for the homology of the matching complex
• Links in the complex of separable graphs
• Complexes of directed trees
• On the homotopy type of complexes of graphs with bounded domination number
• Minimal resolutions and the homology of matching and chessboard complexes
• Connected Plane Sets which Contain no Nondegenerate Connected Simple Graph
• Discrete Morse functions from lexicographic orders
• Cohomology of spaces of complex knots
• Complexes of graph homomorphisms
• The pre-WDVV ring of physics and its topology
• Discrete morse theory and the cohomology ring
• Homotopy type of skeleta of the flag complex over a finite vector space and generalized Galois numbers
• Complexes of connected graphs
• Combinatorial and topological aspects of path posets, and multipath cohomology
• n-connectedness in pure 2-complexes
• On the topology of two partition posets with forbidden block sizes
• Morse theory from an algebraic viewpoint
• Five-torsion in the homology of the matching complex on 14 vertices
• Title not available (Why is that?)

This page was built for publication: Complexes of not \(i\)-connected graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1292680)