Topology of Cut Complexes of Graphs
Margaret M. Bayer, Mark S. Denker, Marija Jelić Milutinović, Rowan Rowlands, Sheila Sundaram, Xue Lei · SIAM Journal on Discrete Mathematics · 2024
Abstract. We define the [Formula: see text]- cut complex of a graph [Formula: see text] with vertex set [Formula: see text] to be the simplicial complex whose facets are the complements of sets of size [Formula: see text] in [Formula: see text] inducing disconnected subgraphs of [Formula: see text]. This generalizes the Alexander dual of a graph complex studied by Fröberg [ Topics in Algebra, Part 2, PWN, Warsaw, 1990, pp. 57–70] and Eagon and Reiner [ J. Pure Appl. Algebra, 130 (1998), pp. 265–275]. We describe the effect of various graph operations on the cut complex and study its shellability, homotopy type, and homology for various families of graphs, including trees, cycles, complete multipartite graphs, and the prism [Formula: see text], using techniques from algebraic topology, discrete Morse theory, and equivariant poset topology.