Total cut complexes of graphs
The paper introduces a new class of simplicial complexes called \textbf{total cut complexes}, denoted \(\Delta^t_k(G)\), associated with a graph \(G\). The facets of \(\Delta^t_k(G)\) are defined as the complements of independent sets of size \(k\) in \(G\). This construction is inspired by Fröberg's theorem and extends classical results in algebraic topology and combinatorial commutative algebra.\N\NKey properties of \(\Delta^t_k(G)\) such as \textit{vertex decomposability}, \textit{shellability}, and \textit{homotopy type} are investigated across various families of graphs, including chordal graphs, cycles, bipartite graphs, grid graphs, and the prism graph \(K_n \times K_2\). A major result generalizes the Eagon-Reiner characterization of chordal graphs [\textit{J. A. Eagon} and \textit{V. Reiner}, J. Pure Appl. Algebra 130, No. 3, 265--275 (1998; Zbl 0941.13016)] by showing that \(G\) is chordal if and only if \(\Delta^t_k(G)\) is vertex decomposable for all \(k\).\N\NTechniques used include discrete Morse theory and simplicial homotopy theory, providing both structural and topological insights into these new complexes.\N\N\textbf{Key Concepts and Theorems}\N\begin{enumerate}\N\item \textbf{Total \(k\)-cut complex:}\N\begin{itemize}\N\item The \textbf{total \(k\)-cut complex} \(\Delta^t_k(G)\) is the simplicial complex whose facets are the complements of independent sets of size \(k\) in \(G\).\N\end{itemize}\N\N\item \textbf{Vertex decomposability:}\N\begin{itemize}\N\item A pure simplicial complex is \textbf{vertex decomposable} if it is either a simplex or there exists a vertex \(v\) such that both the \textit{link} and \textit{deletion} of \(v\) are vertex decomposable, and the deletion is pure and of the same dimension.\N\item \textbf{Theorem 1.3.}\\ \(\Delta^t_k(G)\) is vertex decomposable for all \(k\) if and only if \(G\) is chordal.\N\item \textbf{Theorem 4.12.} \\\NIf \(G\) is chordal, then \(\Delta^t_k(G)\) is vertex decomposable for all \(k \geq 2\).\N\end{itemize}\N\N\item \textbf{Homotopy type of \(\Delta^t_k(G)\) }\N\begin{itemize}\N\item \textbf{Theorem 3.6.} \NLet \(v\) be a simplicial vertex of \(G\), and suppose \(\Delta^t_k(G \setminus v)\) is non-void. Then\N\[\N\Delta^t_k(G) \simeq \text{susp}(\Delta^t_k(G \setminus v)).\N\]\N\item \textbf{Theorem 3.11 (a).} \NLet \(G \cup \{v\}\) be the disjoint union of \(G\) and an isolated vertex \(v\). Then:\N\[\N\Delta^t_k(G \cup \{v\}) \simeq \Delta^t_{k-1}(G) / \Delta^t_k(G).\N\]\N\item \textbf{Theorem 4.8.} \NLet \(G_n = K_n \times K_2\) (the prism over \(K_n\)). Then:\N\[\N\Delta^t_2(G_n) \simeq \bigvee^{n-1} S^{2n-4}.\N\]\N\item \textbf{Theorem 4.13.} \NLet \(G\) be a chordal graph with \(n\) vertices and \(c\) connected components. Then:\N\[\N\Delta^t_k(G) \simeq\N\begin{cases}\N\bigvee^{\binom{c-1}{k-1}} S^{n-k-1}, & \text{if } c \geq k, \\\N\text{contractible or void}, & \text{if } c < k.\N\end{cases}\N\]\N\end{itemize}\N\N\item \textbf{Shellability of \(\Delta^t_k(G)\) }\N\begin{itemize}\N\item \textbf{Theorem 4.15.} \NFor the cycle graph \(C_n\) with \(n \geq 2k\),\N\[\N\Delta^t_k(C_n) \simeq S^{n - 2k}.\N\]\NHence, it is not shellable.\N\end{itemize}\N\end{enumerate}
- Combinatorial algebraic topology
- Combinatorics and commutative algebra.
- Complexes of graphs with bounded independence number
- Complexes oft-Colorable Graphs
- Decompositions of Simplicial Complexes Related to Diameters of Convex Polyhedra
- Elementary topology: problem textbook
- Higher independence complexes of graphs and their homotopy types
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 16165 (Why is no real title available?)
- scientific article; zbMATH DE number 2103273 (Why is no real title available?)
- scientific article; zbMATH DE number 854567 (Why is no real title available?)
- scientific article; zbMATH DE number 863503 (Why is no real title available?)
- Introduction to topological manifolds
- Matching complexes of trees and applications of the matching tree algorithm
- Morse theory for cell complexes
- On Lexicographically Shellable Posets
- Poset topology: tools and applications
- Resolutions of Stanley-Reisner rings and Alexander duality
- Semigroup rings and simplicial complexes
- Shellable nonpure complexes and posets. II
- Simplicial complexes of graphs
- Some combinatorial and algebraic properties of Coxeter complexes and Tits buildings
- Topology of cut complexes of graphs
- Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in cooperation with Anders Björner and Günter M. Ziegler
This page was built for publication: Total cut complexes of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7025757)
