Topology of Cut Complexes of Graphs

2023/04/26 by Margaret M. Bayer, Bayer, Margaret, Mark Denker +9 · 3 citations
Computer Science · Mathematics · #05C69 #05E18 #05E45 #57M15 #57Q70 #Advanced Combinatorial Mathematics #Algebraic Topology (math.AT) #Combinatorics (math.CO) #FOS: Mathematics #Homotopy and Cohomology in Algebraic Topology #Topological and Geometric Data Analysis

paper · pdf · doi:10.48550/arxiv.2304.13675

openalex publication_date 2023/04/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We define the k-cut complex of a graph G with vertex set V(G) to be the simplicial complex whose facets are the complements of sets of size k in V(G) inducing disconnected subgraphs of G. This generalizes the Alexander dual of a graph complex studied by Fröberg (1990), and Eagon and Reiner (1998). 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 K_n × K₂, using techniques from algebraic topology, discrete Morse theory and equivariant poset topology.

Cited by

• On Shellability of 3-Cut Complexes of Hexagonal Grid Graphs
• Total 2-cut complexes of powers of cycle graphs and Cartesian products of certain graphs
• The complex of r-co-connected subgraphs, chordality and Fröberg's theorem

Related

• Total Cut Complexes of Graphs
• Topology of Cut Complexes II
• Total 2-cut complexes of powers of cycle graphs and Cartesian products of certain graphs
• Shellability of 3-Cut Complexes of Squared Cycle Graphs
• Realizations and Uniqueness of Cut Complexes of Graphs