Séminaire Lotharingien de Combinatoire, 89B.8 (2023), 12 pp.
Margaret Bayer, Mark Denker, Marija Jelić
Milutinović, Rowan Rowlands, Sheila Sundaram and Lei Xue
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.
Received: November 15, 2022.
Accepted: February 20, 2023.
Final version: April 1, 2023.
The following versions are available: