On the Topology of Cut Complexes of Graphs

Abstract

For a positive integer k and a finite graph G, we define the $k$-cut complex Δk(G) to be the pure simplicial complex in which the complement of each face contains a set of k vertices inducing a disconnected subgraph of G. This generalises a simplicial complex considered by John Eagon and Victor Reiner (1998), who use Δ2(G) to reformulate and extend a famous theorem of Ralf Fröberg (1990) relating certain Stanley-Reisner ideals to chordal graphs. In particular their combined results imply that Δ2(G) is shellable if and only if G> is a chordal graph.

We investigate Δk(G) with this inspiration, using techniques from algebraic and combinatorial topology. We describe the effect of various graph operations on the cut complex, consider its shellability, and determine the homotopy type and Betti numbers of Δk(G) for various families of graphs. When the homotopy type is a wedge of spheres, we also determine the group representation on the rational homology, notably in the case of complete multipartite graphs.