Topology of Cut Complexes of Graphs

arXiv2304.13675MaRDI QIDQ6509835FDOQ6509835

Authors: Margaret M. Bayer, Mark Denker, Marija Jelić Milutinović, Rowan Rowlands, Sheila Sundaram, Lei Xue 

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"oberg (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}imes{K}_2$, using techniques from algebraic topology, discrete Morse theory and equivariant poset topology.

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Combinatorial aspects of simplicial complexes (05E45) Group actions on combinatorial structures (05E18) Relations of low-dimensional topology with graph theory (57M15) Discrete Morse theory and related ideas in manifold topology (57Q70)

This page was built for publication: Topology of Cut Complexes of Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6509835)