A Caltech Library Service

Complexes of not i-connected graphs

Babson, Eric and Björner, Anders and Linusson, Svante and Shareshian, John and Welker, Volkmar (1999) Complexes of not i-connected graphs. Topology, 38 (2). pp. 271-299. ISSN 0040-9383. doi:10.1016/S0040-9383(98)00009-3.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


Complexes of (not) connected graphs, hypergraphs and their homology appear in the construction of knot invariants given by Vassiliev [38, 39, 41]. 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 a question 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.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© 1998 Elsevier. Received 20 May 1997, Revised 20 January 1998, Available online 15 April 1999. We are grateful to Victor Vassiliev for inspiring discussions and hints [40], which sparked our interest and initiated this research. All computer calculations presented in this paper were performed using a Mathematica package designed by Vic Reiner and a C-Program by Frank Heckenbach. We also thank Vic Reiner for some valuable comments. Partially supported by the Mathematical Sciences Research Institute, Berkeley, California. Supported by a National Science Foundation postdoctoral fellowship. Partially supported by the Göran Gustafsson Foundation for Research in Natural Sciences and Medicine. Supported by Swedish Natural Sciences Research Council (NFR) postdoctoral fellowship. Supported by Deutsche Forschungsgemeinschaft (DFG).
Funding AgencyGrant Number
Mathematical Sciences Research Institute (MSRI)UNSPECIFIED
NSF Postdoctoral FellowshipUNSPECIFIED
Göran Gustafsson Foundation for Research in Natural Sciences and MedicineUNSPECIFIED
Swedish Natural Sciences Research CouncilUNSPECIFIED
Deutsche Forschungsgemeinschaft (DFG)UNSPECIFIED
Issue or Number:2
Record Number:CaltechAUTHORS:20170409-073137684
Persistent URL:
Official Citation:Eric Babson, Anders Björner, Svante Linusson, John Shareshian, Volkmar Welker, COMPLEXES OF NOT i-CONNECTED GRAPHS, Topology, Volume 38, Issue 2, 1999, Pages 271-299, ISSN 0040-9383, (
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:76436
Deposited By: 1Science Import
Deposited On:03 Apr 2018 20:55
Last Modified:15 Nov 2021 16:59

Repository Staff Only: item control page