%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2023}
\articlenumber{8}
%Revised 2023 March 5
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

\newtheorem{thm}{Theorem}
\newtheorem{lem}{Lemma}

%%%%%%%%%%adding these...
\newtheorem{conj}{Conjecture}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{obs}[thm]{Observation}
\newtheorem{prop}[thm]{Proposition}
\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}
\newtheorem{remark}[thm]{Remark}
\newtheorem{ex}[thm]{Example}
\newtheorem{rk}[thm]{Remark}
\newtheorem{qn}[conj]{Question}

%%%%%%%%%%%%%%%%MACROS from Results.tex %%%%%%%%%%%%%%%%%%

\usepackage{subcaption}
\usepackage{tikz}
%\usepackage{comment}
\usetikzlibrary{patterns}
%Mark's tikz commands from "ShortPresentationSlides" --Sheila2021Dec10
\tikzset{
  norm/.style     = {shape=circle, draw},
  blue/.style     = {shape=circle, draw, fill=blue!25},
  high/.style     = {shape=circle, draw, color=red},
  bluehigh/.style = {shape=circle, draw, color=red, fill=blue!25},
  red/.style      = {shape=circle, draw, fill=red!25},
  both/.style     = {shape=circle, draw, fill=violet!35},
  root/.style     = {node, bottom color=red!30},
  env/.style      = {treenode, font=\ttfamily\normalsize},
  dummy/.style    = {circle}
}
\tikzstyle{standard}=[circle, draw=black, fill=white, very thick, minimum size=7mm]
\tikzstyle{standard2}=[circle, draw=black, fill=white, very thick]
\tikzstyle{blue2}=[circle, draw=black, fill=blue!25, very thick]
\tikzstyle{small}=[circle, draw=black, fill=black, very thick, minimum size=4mm]
\tikzstyle{special}=[circle, draw=red!60, fill=red!5, very thick, minimum size=5mm]
%


% Code to hide proofs (comment out the next four lines if you want the proofs to be included):
% \usepackage{environ}
% \NewEnviron{killcontents}{}
% \let\proof\killcontents
% \let\endproof\endkillcontents

\DeclareMathOperator{\F}{\mathcal{F}}
\DeclareMathOperator{\susp}{susp}
\newcommand{\bigast}{\mathop{\scalebox{1.5}{\raisebox{-0.2ex}{$\ast$}}}}
\DeclareMathOperator{\lk}{lk}
\DeclareMathOperator{\st}{st}
\DeclareMathOperator{\del}{del}
\DeclareMathOperator{\bbS}{\mathbb{S}} %Sheila for spheres
\DeclareMathOperator{\sgn}{\mathrm{sgn}} %Sheila for sign repn
\DeclareMathOperator{\bbR}{\mathbb{R}}
\DeclareMathOperator{\bbP}{\mathbb{P}}
\DeclareMathOperator{\bbZ}{\mathbb{Z}}

%\linenumbers
 
%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%
%%%MACROS FOR TINY TREES IN GRID GRAPH SECTION%%%%%%%
\newcommand{\heha}{\tikz[baseline=.1ex, scale=.5]{
    \draw[fill=black] (0,1) circle (3pt);
    \draw[fill=black] (1,1) circle (3pt);
    \draw[fill=black] (1,0) circle (3pt);
    \draw[fill=black] (2,0) circle (3pt);
    \draw (0,1) -- (1,1);
    \draw (1,1) -- (1,0); 
    \draw (1,0) -- (2,0);
    } }

\newcommand{\hehb}{\tikz[baseline=.1ex, scale=.5]{
    \draw[fill=black] (0,1) circle (3pt);
    \draw[fill=black] (1,1) circle (3pt);
    \draw[fill=black] (1,0) circle (3pt);
    \draw[fill=black] (2,1) circle (3pt);
    \draw (0,1) -- (1,1);
    \draw (1,1) -- (1,0); 
    \draw (1,1) -- (2,1);
    } }

\newcommand{\hehc}{\tikz[baseline=.1ex, scale=.5]{
    \draw[fill=black] (0,0) circle (3pt);
    \draw[fill=black] (1,0) circle (3pt);
    \draw[fill=black] (1,1) circle (3pt);
    \draw[fill=black] (2,1) circle (3pt);
    \draw (0,0) -- (1,0);
    \draw (1,0) -- (1,1); 
    \draw (1,1) -- (2,1);
    } }

\newcommand{\hehd}{ \tikz[baseline=.1ex, scale=.5]{
    \draw[fill=black] (0,0) circle (3pt);
    \draw[fill=black] (1,1) circle (3pt);
    \draw[fill=black] (1,0) circle (3pt);
    \draw[fill=black] (2,0) circle (3pt);
    \draw (0,0) -- (1,0);
    \draw (1,1) -- (1,0); 
    \draw (1,0) -- (2,0);
    }}

\newcommand{\hevDOWN}{\tikz[baseline=.1ex, scale=.5]{
    \draw[fill=black] (0,1) circle (3pt);
    \draw[fill=black] (1,1) circle (3pt);
    \draw[fill=black] (2,1) circle (3pt);
    \draw[fill=black] (2,0) circle (3pt);
    \draw (0,1) -- (1,1);
    \draw (1,1) -- (2,1); 
    \draw (2,1) -- (2,0);
    } }

\newcommand{\vDOWNeh}{\tikz[baseline=.1ex, scale=.5]{
    \draw[fill=black] (0,0) circle (3pt);
    \draw[fill=black] (0,1) circle (3pt);
    \draw[fill=black] (1,1) circle (3pt);
    \draw[fill=black] (2,1) circle (3pt);
    \draw (0,0) -- (0,1) -- (1,1) -- (2,1);
    } }

\newcommand{\hevUP}{\tikz[baseline=.1ex, scale=.5]{
    \draw[fill=black] (0,0) circle (3pt);
    \draw[fill=black] (1,0) circle (3pt);
    \draw[fill=black] (2,0) circle (3pt);
    \draw[fill=black] (2,1) circle (3pt);
    \draw (0,0) -- (1,0) -- (2,0) -- (2,1);
    } }

\newcommand{\vUPeh}{\tikz[baseline=.1ex, scale=.5]{
    \draw[fill=black] (0,1) circle (3pt);
    \draw[fill=black] (0,0) circle (3pt);
    \draw[fill=black] (1,0) circle (3pt);
    \draw[fill=black] (2,0) circle (3pt);
    \draw (0,1) -- (0,0) -- (1,0) -- (2,0);
    } }
    
\newcommand{\veva}{\tikz[baseline=.1ex, scale=.5]{
    \draw[fill=black] (0,-1) circle (3pt);
    \draw[fill=black] (0,0) circle (3pt);
    \draw[fill=black] (0,1) circle (3pt);
    \draw[fill=black] (1,0) circle (3pt);
    \draw (0,-1) -- (0,0) -- (0,1) ; 
    \draw (0,0) -- (1,0);
    } }

\newcommand{\vevb}{\tikz[baseline=.1ex, scale=.5]{
    \draw[fill=black] (0,-1) circle (3pt);
    \draw[fill=black] (0,0) circle (3pt);
    \draw[fill=black] (0,1) circle (3pt);
    \draw[fill=black] (-1,0) circle (3pt);
    \draw (0,-1) -- (0,0) -- (0,1) ; 
    \draw (0,0) -- (-1,0);
    } }

\newcommand{\vevc}{\tikz[baseline=.1ex, scale=.5]{
    \draw[fill=black] (0,0) circle (3pt);
    \draw[fill=black] (0,1) circle (3pt);
    \draw[fill=black] (1,0) circle (3pt);
    \draw[fill=black] (1,-1) circle (3pt);
    \draw (0,1) -- (0,0) -- (1,0) -- (1,-1); 
        } }

\newcommand{\vevd}{\tikz[baseline=.1ex, scale=.5]{
    \draw[fill=black] (0,-1) circle (3pt);
    \draw[fill=black] (0,0) circle (3pt);
    \draw[fill=black] (1,0) circle (3pt);
    \draw[fill=black] (1,1) circle (3pt);
    \draw (0,-1) -- (0,0) -- (1,0) -- (1,1); 
        } }

%\hLEFTevDOWN \hskip1mm  \hRIGHTevDOWN

\newcommand{\hLEFTevDOWN}{\tikz[baseline=.1ex, scale=.5]{
    \draw[fill=black] (-1,1) circle (3pt);
    \draw[fill=black] (0,1) circle (3pt);
    \draw[fill=black] (0,0) circle (3pt);
    \draw[fill=black] (0,-1) circle (3pt);
    \draw (-1,1)--(0,1)--(0,0)--(0,-1); 
        } }

\newcommand{\hRIGHTevDOWN}{\tikz[baseline=.1ex, scale=.5]{
    \draw[fill=black] (1,1) circle (3pt);
    \draw[fill=black] (0,1) circle (3pt);
    \draw[fill=black] (0,0) circle (3pt);
    \draw[fill=black] (0,-1) circle (3pt);
    \draw (1,1)--(0,1)--(0,0)--(0,-1); 
        } }

\newcommand{\hhh}{\tikz[baseline=.1ex, scale=.5]{
    \draw[fill=black] (0,0) circle (3pt);
    \draw[fill=black] (1,0) circle (3pt);
    \draw[fill=black] (2,0) circle (3pt);
    \draw (0,0)--(1,0) -- (2,0); 
        } }    

%%%END MACROS FOR TINY TREES IN GRID GRAPH SECTION%%%%%%%
%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%END MACROS from Results.tex %%%%%%%%%%%%%%%%%%


%% define your title in the usual way
\title[Cut Complexes of Graphs]{On the Topology of Cut Complexes of Graphs}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
%\author[Optional shorter names]{Margaret Bayer\thanks{\href{mailto:bayer@ku.edu}{mark.denker@ku.edu}. Longer names me was partially supported by Grant 2017.11.14.$\partial$\;supp.}\addressmark{}, \and Mark Denker\addressmark{2}}

\author[Bayer, Denker, Jeli\'c Milutinovi\'c, Rowlands, Sundaram, Xue]{Margaret Bayer\addressmark{1},  Mark Denker\addressmark{2}, Marija Jeli\'c Milutinovi\'c\addressmark{3}, \\Rowan Rowlands\addressmark{4}, Sheila Sundaram\thanks{\href{mailto:shsund@comcast.net}{shsund@comcast.net}}\addressmark{5}, \and Lei Xue\addressmark{6}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1,2}Department of Mathematics, University of Kansas, Lawrence, KS, USA \\
\addressmark{3}Department of Mathematics, University of Belgrade, Belgrade, Serbia\\
 \addressmark{4}Department of Mathematics, University of Washington, Seattle, WA, USA\\
\addressmark{5}Pierrepont School, Westport, CT, USA\\
\addressmark{6}Department of Mathematics, University of Michigan, Ann Arbor, MI, USA}

%% <bayer@ku.edu>, Denker, Mark Edward <mark.denker@ku.edu>, marijaj@matf.bg.ac.rs <marijaj@matf.bg.ac.rs>, Rowan Rowlands <rowanr@uw.edu>, Lei Xue <lxue@uw.edu>

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{For a positive integer $k$  and a finite graph $G$,  we define the  \emph{$k$-cut complex} $\Delta_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 
% introduced by Bruns and Herzog (1997).  
considered by John Eagon and Victor Reiner (1998), who use $\Delta_2(G)$ to reformulate and extend a famous theorem of  Ralf Fr\"oberg (1990) relating  certain Stanley-Reisner ideals to  chordal graphs. In particular their combined results imply that $\Delta_2(G)$ is shellable if and only if $G$ is a chordal graph. 

 We investigate $\Delta_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 $\Delta_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.
}

%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Graph complex, chordal graph,  shellability, homotopy, homology representation}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations; i.e., [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
%\addbibresource{shellable-no-url.bib}
\addbibresource{FPSAC2023CutComplex.bib}
%\addbibresource{sample.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

\section{Introduction}

%\lipsum[3]

In recent years, there has been much interest in the topology of simplicial
complexes associated with graphs.  A comprehensive reference is Jonsson's book  \cite{JonssonBook2008}.


  A \emph{graph complex} is a simplicial complex associated to a finite  graph $G$. In this paper we introduce a new family of  graph complexes  which we call \emph{cut complexes}. We consider only simple graphs.  Our work is motivated by a famous theorem of Ralf Fr\"oberg (1990) connecting commutative algebra and graph theory through topology.  We investigate  our new complexes in the spirit of Fr\"oberg's theorem, relating topological properties of the cut complex  to structural properties of the graph. 

For a field $\mathbb{K}$ and a finite simplicial complex $\Delta$ with vertex set $[n]=\{1,2,\ldots,n\}$, the Stanley-Reisner ideal of $\Delta$ is the ideal $I_\Delta$  of the polynomial ring $\mathbb{K}[x_1,\ldots , x_n]$ generated by  monomials $x_{i_1}\cdots x_{i_k}$, where 
$\{i_1, \ldots , i_k\}$ runs over the inclusion-minimal subsets of $[n]$ which are NOT faces of $\Delta$.  The Stanley-Reisner ring $\mathbb{K}[\Delta]$ is the quotient of the polynomial ring $\mathbb{K}[x_1,\ldots , x_n]$ by the ideal $I_\Delta$. 

For a graph $G$, %the \emph{flag complex} or 
the \emph{clique complex} $\Delta(G)$  is  the simplicial complex whose simplices are subsets of vertices of $G$, in which every pair of vertices  is connected by an edge of $G$.  Fr\"oberg \cite{Froberg1990} characterised ideals generated by monomials which have a \emph{linear resolution}, by first reducing to the case of square-free monomial ideals.    The ideal $I_\Delta$ is generated by quadratic square-free monomials precisely when the simplicial complex $\Delta$ is $\Delta(G)$ for some graph $G$ (see \cite[Proposition~8]{EagonReiner1998}).  Hence Fr\"oberg's theorem can be stated as follows:

\begin{thm}\label{thm:Fr} (Fr\"oberg) [{\cite{Froberg1990}, \cite[p. 274]{EagonReiner1998}}] A Stanley-Reisner ideal $I_\Delta$ generated by quadratic square-free monomials has a linear resolution if and only if $\Delta$ is the clique complex $\Delta(G)$ of a chordal  graph $G$.
\end{thm} 
%
Define the combinatorial \emph{Alexander dual} of a simplicial complex $\Delta$ \cite[p.188]{BrunsHerzog1997} on $n$ vertices to be 
\[\Delta^{\vee}:= \{F\subset [n]: [n]\setminus F\notin \Delta\}.\]  
The $i$th homology of $\Delta$ and the $(n-i-3)$th cohomology of $\Delta^{\vee}$ are isomorphic by Alexander duality in the sphere $\bbS^{n-2}$.

For a graph $G$, write $\Delta_2(G)$ for 
 the  Alexander dual $\Delta(G)^\vee$ of the clique complex $\Delta(G)$.
%
The facets of  $\Delta_2(G)$  are the complements of  independent sets of size 2 in $G$.
%
Eagon and Reiner's \cite[Proposition 8]{EagonReiner1998} reformulation of Fr\"oberg's theorem 
includes the following equivalences.

\begin{thm}\label{thm:Froberg} 
The graph  $G$ is chordal  $\!\iff\!$ $\Delta_2(G)$ is shellable $\!\iff\!$ $\Delta_2(G)$ is vertex decomposable.
\end{thm} 

Inspired by this theorem, we introduce the following generalisation of the simplicial complex $\Delta_2(G)$.  Let $k\ge 1$.  Define 
 a complex whose facets are complements of sets  $F$ of size $k$ in $G$ such that the induced subgraph of $G$ on  the vertex set $F$ is disconnected; we call this the $k$-cut complex of $G$, and denote it by 
$\Delta_k(G)$.  A different generalisation, the total $k$-cut complex $\Delta_k^t(G)$,  is treated in \cite{BDJRSX-TOTAL2022}.  The two notions coincide for $k=2$. 

We examine the topology of the cut complex $\Delta_k(G)$ and consider how it is affected by properties of the graph $G$ (\cref{sec:Constructions}). For example, in analogy with Fr\"oberg's theorem,  \cref{prop:chordal-Delta3-shell} asserts that graph chordality implies  shellability of the 3-cut complex $\Delta_3$.
We show that for many common families of graphs (\cref{sec:Families}),  the homotopy type of $\Delta_k(G)$  is a wedge of spheres in a single dimension.    Often  there is  a simplicial group action  on the cut complex $\Delta_k(G)$, which in turn acts on the rational homology. We  determine this homology representation,  notably in the case of complete multipartite graphs \cite{BDJRSX}.  


\section{Definitions}\label{sec:Definitions}
 
General references for simplicial complexes, shellability and topology are \cite{BjTopMeth1995}, \cite{Hatcher2002} 
and \cite{WachsPosetTop2007}, and \cite{WestGraphTheory1996} for graph theory.  All graphs in this paper are simple (no loops and no multiple edges).

\begin{defn}\label{def:simplicial-complex}  A simplicial complex $\Delta$ on a set $A$ is a collection of subsets of $A$ 
\[ \sigma\in \Delta \text{ and } \tau\subseteq \sigma \Rightarrow \tau \in \Delta. \] 
%
The elements of $\Delta$ are called its \emph{faces} or \emph{simplices}. 
If the collection of subsets is empty, i.e.\ $\Delta$ has no faces,  we call $\Delta$ the void complex.  Otherwise $\Delta$ always contains the empty set as a face. 

The \emph{dimension of a face} $\sigma$, $\dim(\sigma)$, is one less than its cardinality; thus the dimension of the empty face is $(-1)$, and the 0-dimensional faces are the \emph{vertices} of $\Delta$. A \emph{$d$-face} or \emph{$d$-simplex} is a face of dimension $d$.  The maximal faces of $\Delta$ are called its \emph{facets}, and the maximum dimension of a facet is the \emph{dimension} $\dim(\Delta)$ of the nonvoid simplicial complex $\Delta$. We  write $\Delta=\langle\mathcal{F}\rangle$ for the simplicial complex $\Delta$ whose set of facets is $\mathcal{F}$.

In this paper all simplicial complexes will be \emph{finite}, that is, the vertex set is finite.

A (nonvoid) simplicial complex is \emph{pure} if all its facets have the same dimension, which is then the dimension of the complex.

The \emph{join} of two simplicial complexes $\Delta_1$ and $\Delta_2$ with disjoint vertex sets is the complex \begin{center}{$\Delta_1 * \Delta_2= \{\sigma\cup \tau: \sigma\in \Delta_1, \tau\in \Delta_2\}.$}\end{center}
Thus the join $\Delta_1 * \Delta_2$ contains $\Delta_1$ and $ \Delta_2$ as subcomplexes.
%

The \emph{cone} over $\Delta$ and the \emph{suspension} of $\Delta$ are the complexes 
\begin{center}{$\mathrm{cone}(\Delta)=\Delta* \Gamma_1, \ 
\mathrm{susp}(\Delta)=\Delta*\Gamma_2=\Delta*\{u\}\cup\Delta*\{v\},$}\end{center}
where $\Gamma_1$ is the 0-dimensional simplicial complex with one vertex, and $\Gamma_2$ is the 0-dimensional complex with two vertices $u,v$. 
\end{defn}

\begin{defn}[{\cite[Sec. 11.2]{BjTopMeth1995}}]\label{def:shelling}
%[{\cite[Chapter III, Section 2]{RPSCCA1996}}] \label{def:shelling}
An ordering $F_1,F_2,\dots,F_t$ of the facets of a simplicial complex $\Delta$ is a \emph{shelling} if, for every $j$ with $1<j\leq t$, $\left( \bigcup_{i=1}^{j-1}\langle F_i\rangle\right)\cap \langle F_j\rangle$
is a simplicial complex whose facets all have cardinality $|F_j|-1$, where $\langle F_i\rangle$ is the simplex generated by the face $F_i$.
The simplicial complex $\Delta$ is  \emph{shellable}  if it admits a shelling order of its facets. 
%
\end{defn}
%
\begin{rk}\label{rem:empty-complex-0-dim-complex} By convention, the void complex is shellable. The complex whose only face is the empty set 
 is vacuously shellable. 
The  complex with a unique nonempty facet is (also vacuously) shellable, and contractible. 
\end{rk}
%
See Figures~\ref{fig:Ex-Delta2}(b) and~\ref{fig:Ex-Delta4}(b) for examples of shellable and nonshellable complexes.

In combinatorial topology, shellability is an important tool  for determining the homotopy type of simplicial complexes, thanks to the following theorem of Bj\"orner.
%
\begin{thm}[{\cite[(9.19) and Sec. 11]{BjTopMeth1995}}] \label{thm:shell-implies-homotopytype}
A pure shellable simplicial complex of dimension $d$ has the homotopy type of a wedge of spheres, all of dimension $d$ (it may be contractible).
%[{\cite[Theorem~1.3]{Bj-AIM1984}}]
\end{thm}

\begin{defn}\label{def:graph-disc-sep}
Let $G=(V,E)$ be a graph on $|V|=n$ vertices. If $S$ is a subset of the vertex set $V$,  write $G[S]$ to denote the \emph{induced subgraph} of $G$ whose vertex set is $S$. 
\end{defn}


\begin{defn}\label{def:cut-cplx}
Let $G=(V,E)$ be a graph on $|V|=n$ vertices, and let $k\ge 2$. Define the \emph{$k$-cut complex} of the graph $G$  to be the $(n-k-1)$-dimensional simplicial complex 
\[\Delta_k(G):=\langle F\subseteq V, |F|=n-k\mid G[V\setminus F] \text{ is disconnected}\rangle.\] The facets of the cut complex $\Delta_k(G)$ are the vertex subsets of $G$ of size $(n-k)$ whose removal disconnects the graph $G$.   Thus $\sigma$ is a face of the cut complex $\Delta_k(G)$ if and only if its complement $V\setminus \sigma$ contains a subset $S$ of size $k$ such that the induced subgraph $G[S]$ is disconnected.   Note  the inclusion
% added $k\ge 2$ here 2023 March 5
%\begin{equation} \label{eqn:inclusion}
$\Delta_{k+1}(G)\subseteq \Delta_k(G)$ for $ k\ge 2,$ and the fact that the vertices of $\Delta_k(G)$ are a subset of the vertices of the graph $G$. See \cref{fig:Ex-Delta2,fig:Ex-Delta4} .
%\end{equation}
\end{defn}
 %   
    \begin{figure}[htb]
        \centering
        \begin{subfigure}{0.4\textwidth}
        \centering
        \begin{tikzpicture}[scale=0.5]
        %Nodes
\node[standard] (node3) at (0,0) {3};
\node[standard] (node1) at (0,2) {1};
\node[standard] (node4) at (2,0) {4};
\node[standard] (node2) at (2,2) {2};
\node[standard] (node5) at (4,0) {5};

%Lines
\draw (node1) -- (node3);
\draw (node1) -- (node2);
\draw (node1) -- (node4);
\draw (node2) -- (node4);
\draw (node2) -- (node5);
\draw (node3) -- (node4);
\draw (node4) -- (node5);
% \node at (2,-1) {The graph $G$ has 3 separating 3-sets:};
% \node at (2, -1.5) {$\{1,2,4\}, \{1,4,5\}$ and $\{2,3,4\}$};
        \end{tikzpicture}
        \caption{The graph $G$ is disconnected by removing any of the following  3-sets: $\{1,2,4\}, \{1,4,5\}$ and $\{2,3,4\}$}
        \end{subfigure} \qquad
        \begin{subfigure}{0.4\textwidth}
        \centering
        \begin{tikzpicture}[scale=0.5]
\draw[fill=gray!20] (3,0) -- (4,2) -- (2,2) -- cycle;
\draw[fill=gray!20] (1,0) -- (2,2) -- (3,0) -- cycle;
\draw[fill=gray!20] (1,0) -- (2,2) -- (0,2) -- cycle;

\node[standard] (node5) at (0,2) {5};
\node[standard] (node1) at (1,0) {1};
\node[standard] (node4) at (2,2) {4};
\node[standard] (node2) at (3,0) {2};
\node[standard] (node3) at (4,2) {3};
% \node at (2,-1) {The cut complex $\Delta_2 (G)=\langle234,145,124\rangle$};
        \end{tikzpicture}
       \caption{$\Delta_2 (G)=\langle234,145,124\rangle$}
        \end{subfigure}
       \caption{(Shellable) 2-cut complex of graph $G$}\label{fig:Ex-Delta2}
    \end{figure}

\begin{figure}[htb!]
        \centering
        \begin{subfigure}{0.4\textwidth}
        \centering
        \begin{tikzpicture}[scale=0.6]
        %Nodes
\node[standard] (node3) at (0,0) {3};
\node[standard] (node1) at (0,2) {1};
\node[standard] (node4) at (2,0) {4};
\node[standard] (node2) at (2,2) {2};
\node[standard] (node5) at (4,1) {5};
\node[standard] (node6) at (-2,1) {6};
% moved up node5 and node6 to look like a kayak 2023 March 5
%Lines
\draw[very thick, color=red] (node1) -- (node3); % separating set of size 2
\draw (node1) -- (node2);
\draw (node1) -- (node4);  % for kayak
\draw (node2) -- (node3);  % for kayak
\draw[very thick, color=red] (node2) -- (node4);% separating set of size 2
\draw (node2) -- (node5);
\draw (node3) -- (node4);
\draw (node4) -- (node5);
\draw (node1) -- (node6);
\draw (node3) -- (node6);

% \node at (2,-1) {The graph $G$ has 3 separating 3-sets:};
% \node at (2, -1.5) {$\{1,2,4\}, \{1,4,5\}$ and $\{2,3,4\}$};
        \end{tikzpicture}
        \caption{$G$ is disconnected by removing\\ one of the 2-sets $\{1,3\}$, $\{2,4\}$}
        \end{subfigure} \qquad
        \begin{subfigure}{0.4\textwidth}
        \centering
        \begin{tikzpicture}[scale=0.6]
  %Nodes
\node[standard] (node3) at (0,0) {3};
\node[standard] (node1) at (0,2) {1};
\node[standard] (node4) at (2,0) {4};
\node[standard] (node2) at (2,2) {2};

%Lines
\draw (node1) -- (node3);
\draw (node2) -- (node4);
% \node at (2,-1) {The cut complex $\Delta_2 (G)=\langle234,145,124\rangle$};
        \end{tikzpicture}
        \caption{$\Delta_4 (G)=\langle 13, 24\rangle$}
        \end{subfigure}
       \caption{(Nonshellable) 4-cut complex of graph $G$}\label{fig:Ex-Delta4}
    \end{figure}

\begin{ex}\label{ex:Examples-cut-complex}  Let $G$ be a graph on $n$ vertices. We record some easy facts about cut complexes.  %Recall that void complexes are shellable.
\begin{enumerate}
%\item  $\Delta_1(G)$ is always void.

\item $\Delta_k(G)$ is void if $k=1$ or $k>n$. 

\item $\Delta_n(G)$ is 
$\begin{cases} \text{ the void complex, } & \text{if $G$ is connected},\\
            \text{ the $(-1)$-dimensional complex } \{\emptyset\},  
                              & \text{otherwise}. \end{cases}$

\item $\Delta_k(G)$ is void for $n-k\le r-1$ if $G$ is $r$-connected, since at least $r$ vertices must be removed to disconnect the graph.
%changed $k\le r-1$ to $n-k\le r-1$ 2022 nov 7

\item  If $G$ is the complete graph $K_n$, then $\Delta_k(G)$  is void for all $k\ge 1$. 

\item If $G=E_n$ is the edgeless graph on $n$ vertices, then for $2\le k\le n-1$, $\Delta_k(G)$ is the $(n-k-1)$-skeleton of an $(n-1)$-dimensional simplex, hence shellable \cite{BjWachsI1996}.
\end{enumerate}
\end{ex}

In view of Item (1.) above,  we will assume $\mathbf{n\ge k\ge 2}$ for the cut complex $\Delta_k(G)$.


In order to  determine the homotopy type of a simplicial complex $\Delta$, and especially a group representation on the rational homology,  it is often useful to work with the face lattice
$\mathcal{L}(\Delta)$ of $\Delta$. In many cases the automorphism group of the graph $G$ acts simplicially on the cut complex $\Delta_k(G)$.

Clearly the symmetric group $\mathfrak{S}_n$ acts on the cut complex $ \Delta_k(E_n)$ of the edgeless graph $E_n$. 
 The face lattice $\mathcal{L}(\Delta_k(E_n))$ is a rank-selected subposet of the Boolean lattice $B_n$ of subsets of an $n$-element set, consisting of subsets of size at most $n-k$.  Using the fact that this is shellable (see e.g. \cite{WachsPosetTop2007}) in conjunction with  a well-known result of Solomon \cite{SolJAlg1968},   
%\cite{RPSGaP1982}}, 
Observation (5.) above gives us our first nontrivial result for the homotopy type and equivariant homology of a cut complex:

\begin{prop}\label{prop:Deltak-edgeless-graph-homrepS} Let $E_n$ be the edgeless graph on $n$ vertices. If $k\ge n$, the cut complex  $\Delta_k(E_n)$ is void. If $2\le k\le n-1$, the cut complex is shellable and  homotopy equivalent to a wedge of $\binom{n-1}{k-1}$ spheres in dimension $n-k-1$:
\[ \Delta_k(E_n)\simeq\bigvee_{\binom{n-1}{k-1}} \mathbb{S}^{n-k-1}.\]
 The $\mathfrak{S}_n$-representation on the unique nonvanishing homology of $\Delta_k(E_n)$ is 
%$V_{(k, 1^{n-k})},$ 
the irreducible module indexed by the partition $(k, 1^{n-k})$ of $n$.
\end{prop}

\begin{defn}[{\cite{WestGraphTheory1996}}] \label{defn:chordal}
    A graph is \emph{chordal} if it has no induced cycle of size greater than 3.
    \end{defn}
%
\Cref{fig:Ex-Delta2} shows a chordal graph and its shellable 2-cut complex, whereas \cref{fig:Delta2C5} is an example of a nonchordal graph, with  nonshellable 2-cut complex.
%; it is a 2-dimensional complex homotopy equivalent to a circle.
These examples also illustrate Fr\"oberg's \cref{thm:Froberg}.
\begin{figure}[htb]
\centering
\begin{subfigure}{0.4\textwidth}
\centering
\begin{tikzpicture}
%Nodes
\node[standard] (node1) at (0,3) {1};
\node[special] (node1) at (0,3) {1};
\node[standard] (node2) at (1.5,1.7) {2};
\node[special] (node2) at (1.5,1.7) {2};
\node[standard] (node3) at (1,0) {3};
\node[special] (node3) at (1,0) {3};
\node[standard] (node4) at (-1,0) {4};
\node[special] (node4) at (-1,0) {4};
\node[standard] (node5) at (-1.5,1.7) {5};
\node[special] (node5) at (-1.5,1.7) {5};
%
%Lines
\draw (node1) -- (node2);
\draw (node2) -- (node3);
\draw (node3) -- (node4);
\draw (node4) -- (node5);
\draw (node5) -- (node1);
% \node at (0.2, -1) {The cycle $C_5$};
\end{tikzpicture}
\caption{The cycle $C_5$}
\end{subfigure}
%$\Delta_2(C_5)$
%\begin{figure}[htb]
\begin{subfigure}{0.4\textwidth}
\centering
\begin{tikzpicture}
%
\draw[fill=gray!20] (0,0) -- (0.7,1.5) -- (1.4,0) -- (0,0);
\draw[fill=gray!20] (2.1,1.5) -- (0.7,1.5) -- (1.4,0) -- (2.1,1.5);
\draw[fill=gray!20] (2.1,1.5) -- (1.4,0) -- (2.8,0) -- (2.1,1.5);
\draw[fill=gray!20] (3.5,1.5) -- (2.8,0) -- (2.1,1.5) -- (3.5,1.5);
\draw[fill=gray!20] (3.5,1.5) -- (4.2,0) -- (2.8,0) -- (3.5,1.5);
\draw[very thick, color=red,->] (0,0) -- (.55*0.7,.55*1.5);
\draw[very thick, color=red] (.55*0.7,.55*1.5) -- (0.7,1.5);
\draw[very thick, color=red,->] (3.5,1.5) -- (3.5+.55*.7,1.5-.55*1.5);
\draw[very thick, color=red] (3.5+.55*.7,1.5-.55*1.5) -- (4.2,0);
%

\node[standard] (n5) at (0,0) {5};
\node[standard] (n2) at (0.7,1.5) {2};
\node[standard] (n4) at (1.4,0) {4};
\node[standard] (n1) at (2.1,1.5) {1};
\node[standard] (n3) at (2.8,0) {3};
\node[standard] (n5') at (3.5,1.5) {5};
\node[standard] (n2') at (4.2,0) {2};
%
% \node at (2, -1) {$\Delta_2 (C_5)=\langle{245}{,124}{,134} {,135}{,235}\rangle$};
\end{tikzpicture}
\caption{$\Delta_2 (C_5)=\langle{245}{,124}{,134} {,135}{,235}\rangle$}
\end{subfigure}
\caption{The 2-cut complex for $C_5$ is a M\"obius strip}
\label{fig:Delta2C5}
\end{figure}



\section{Constructive Theorems}\label{sec:Constructions}

In this section we consider the effect of  some common graph operations on the cut complex.  We begin with what may be viewed as a universal property of cut complexes.
%
%
\begin{thm} \label{thm:anycomplexiscutcomplex}
Let $\Delta$ be any pure simplicial complex. There exists some $k$ and some chordal graph $G$ such that $\Delta$ is equal to the cut complex $\Delta_k(G)$.
%added chordal 2023 Mar 5
\end{thm}
 The  construction  starts with a clique whose vertices correspond to the vertex set of the complex $\Delta$. For each facet of $\Delta$, add a vertex which is connected to every  vertex of that facet.   If $\Delta$ has $n$ vertices, $t$ facets and dimension $d$, 
the resulting graph $G$ has $(n+t)$ vertices, and   $\Delta_{n+t-(d+1)}(G)=\Delta$. \Cref{fig:Mark-SimplicialComplex-to-CutComplex} illustrates the procedure.

\begin{figure}[htb]
    \centering
    \begin{subfigure}{0.4\textwidth}
    \centering
\begin{tikzpicture}[scale=1]
    \tikzstyle{facet}=[shape=rectangle, fill=white]
    \draw[draw=red!60, fill=blue!5] (0,0) -- (0,2) -- (1.5,1) -- cycle;
    \draw[draw=red!60, fill=blue!5] (0,0) -- (3,0) -- (1.5,1) -- cycle;
    \draw[draw=red!60, fill=blue!5] (0,2) -- (3,2) -- (1.5,1) -- cycle;
    \draw[draw=red!60, fill=blue!5] (3,0) -- (3,2) -- (1.5,1) -- cycle;
    \node (a)[facet] at (.5,1) {$F_1$};
    \node (b)[facet] at (1.5,.3) {$F_2$};
    \node (c)[facet] at (1.5,1.7) {$F_3$};
    \node (d)[facet] at (2.5,1) {$F_4$};
    \node[special] (node1) at (0,0) {1};
    \node[special] (node2) at (0,2) {2};
    \node[special] (node3) at (3,2) {3};
    \node[special] (node4) at (3,0) {4};
    \node[special] (node5) at (1.5,1) {5};
    % \node at (1.5, -1) {A pure simplicial complex $\Delta$};
\end{tikzpicture}
\caption{A pure simplicial complex $\Delta$}
\end{subfigure}
\begin{subfigure}{0.4\textwidth}
\centering
\begin{tikzpicture}[scale=1]
        \node[standard] (n1) at (0,1.5) {1};
        \node[standard] (n2) at (.75,.85) {2};
        \node[standard] (n3) at (.5,0) {3};
        \node[standard] (n4) at (-.5,0) {4};
        \node[standard] (n5) at (-.75,.85) {5};
        \draw (n1) -- (n2);
        \draw (n1) -- (n3);
        \draw (n1) -- (n4);
        \draw (n1) -- (n5);
        \draw (n2) -- (n3);
        \draw (n2) -- (n4);
        \draw (n2) -- (n5);
        \draw (n3) -- (n4);
        \draw (n3) -- (n5);
        \draw (n4) -- (n5);
%   
        \node[standard] (F1) at (0,3) {F1};
        \node[standard] (F2) at (-2,1.4) {F2};
        \node[standard] (F3) at (2,0.2) {F3};
        \node[standard] (F4) at (-1.3,-1.2) {F4};
        \draw[] (F1)--(n1);
        \draw[] (F1)--(n2);
        \draw[] (F1)--(n5);
        
        \draw[] (F2)--(n1);
        \draw[] (F2)--(n4);
        \draw[] (F2)--(n5);
        
        \draw[] (F3)--(n3);
        \draw[] (F3)--(n2);
        \draw[] (F3)--(n5);
        
        \draw[] (F4)--(n3);
        \draw[] (F4)--(n4);
        \draw[] (F4)--(n5);
        \node[blue2] (F1) at (0,3) {F1};
        \node[blue2] (F2) at (-2,1.4) {F2};
       \node[blue2] (F3) at (2,0.2) {F3};
      \node[blue2] (F4) at (-1.3,-1.2) {F4};
        
        \node[special] (n1) at (0,1.5) {1};
        \node[special] (n2) at (.75,.85) {2};
        \node[special] (n3) at (.5,0) {3};
        \node[special] (n4) at (-.5,0) {4};
       \node[special] (n5) at (-.75,.85) {5};
    %   \node at (0, -2) {A graph $G$ such that $\Delta=\Delta_6(G)$};
\end{tikzpicture}
\caption{A graph $G$ such that $\Delta=\Delta_6(G)$}
\end{subfigure}
\caption{The construction  of \cref{thm:anycomplexiscutcomplex}}
\label{fig:Mark-SimplicialComplex-to-CutComplex}
\end{figure}

Let  $G=(V,E)$ be a graph. Recall that we assume $k\ge 2$ for the cut complex $\Delta_k(G)$.
The link 
\cite[Sec. 9.9]{BjTopMeth1995} of a face $\sigma$ of a simplicial complex $\Delta$ is defined to be the simplicial complex 
\[\lk_{\Delta} \sigma= \{\tau \in \Delta \mid \text{$\sigma\cap \tau 
      = \emptyset$, and $\sigma\cup \tau \in \Delta$}\}.  \]
\begin{lem}\label{lemma:links}
    Let   $v\in V$. Then $\Delta_k (G\setminus v) = \lk_{\Delta_k(G)}\{v\}$, if $v$ is a vertex of $\Delta_k(G)$. Otherwise $\Delta_k (G\setminus v)$ is the void complex.
% added caveat for when $v$ is NOT a vertex of the cut complex. 2023 March 5
\end{lem}

By  applying this lemma repeatedly and using the fact that links preserve shellability \cite[Sec. 11.2]{BjTopMeth1995}, we obtain the following important corollary.

\begin{cor}\label{cor:induced subgraphs}
      Let  $W\subseteq V$. If the $k$-cut complex $\Delta_k(G)$ is shellable, so is $\Delta_k(G\setminus W)$.  Equivalently, 
      if $\Delta_k(G)$ is shellable for a graph $G$, then 
      $\Delta_k(H)$ is shellable for every induced subgraph $H$ of $G$. 
\end{cor}

\begin{defn}\label{defn:Disjunion}
If $G_1$, $G_2$ are graphs, their disjoint union is the graph $G_1+G_2$ having vertex set equal to the union of the vertex sets of $G_1$ and $G_2$, and edge set equal to the  union of the edge sets of $G_1$ and $G_2$.
\end{defn}
%
\begin{thm}\label{thm:MargeDisjunion}
 $\Delta_k(G_1+G_2)$ is shellable if and only if $\Delta_k(G_1)$ and $\Delta_k(G_2)$ are shellable.
\end{thm}
For instance, from \cref{ex:Examples-cut-complex}, this theorem  tells us that the $k$-cut complex of the disjoint union of two complete graphs is always shellable.
%
   \begin{defn}
    Given graphs $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ on disjoint vertex sets, their \emph{join} $G_1*G_2$ is their disjoint union with the set of all edges between $V_1$ and $V_2$ included.
    \end{defn}

\begin{thm}\label{thm:Mark-Joins}
 $\Delta_k(G_1*G_2)$ is shellable if and only if between $\Delta_k(G_1)$ and $\Delta_k(G_2)$, one is shellable and the other is the void complex. 
\end{thm}

The homotopy type of  the cut complex of the join of two graphs bears a precise relationship to the homotopy types  of the cut complexes of the individual graphs.  Passing  to the face lattices gives an alternative proof of the homotopy equivalence, and also shows that it is group-equivariant, a fact we will need in \cref{sec:Families}, where we will apply the full force of this theorem to complete bipartite graphs, which are joins of edgeless graphs.   

\begin{thm}\label{thm:susp-of-joins2022Sept12} Let $k\ge 1$,  let $G_i$ be a graph with vertex set $V_i, i=1,2$, where $V_1\cap V_2=\emptyset$.  Assume $\Delta_k(G_i)$ is not void for at least one $i=1,2$.

 If only one cut complex is void, then $\Delta_k(G_1*G_2)$ is contractible.

Now assume both cut complexes $\Delta_k(G_i), i=1,2,$ are nonvoid. Then there is a homotopy equivalence 
\begin{equation}\label{eqn:join-susp-iso} \susp ( \Delta_k(G_1)*\Delta_k(G_2) )\simeq \Delta_k(G_1*G_2). \end{equation}
%
Moreover, there is a group-equivariant poset map from the product  
$\mathcal{L}(\Delta_k(G_1))\times \mathcal{L}(\Delta_k(G_2))$ of face lattices, 
to the face lattice of the simplicial complex $\Delta_k(G_1*G_2)$ 
 which induces a group-equivariant homotopy equivalence of the respective order complexes.
%
This in turn gives a group-equivariant $(H_1\times H_2)$-homotopy equivalence %
%\begin{equation*}\label{eqn:join-susp-iso-group-equiv} 
$\susp ( \Delta_k(G_1)*\Delta_k(G_2) )\simeq_{H_1\times H_2} \Delta_k(G_1*G_2),$
%\end{equation*}
where $H_i$ is a group  acting simplicially on the cut complex $\Delta_k(G_i)$.

Hence we have the following  isomorphism of $(H_1\times H_2)$-modules in rational homology:
\begin{equation*}\tilde{H}_d(\Delta_k(G_1*G_2))\cong \bigoplus_{p+q=d-2} \tilde{H}_{p}(\Delta_k(G_1)) \otimes \tilde{H}_{q}(\Delta_k(G_2)).
  \end{equation*}
\end{thm}

The proof of Equation~\eqref{eqn:join-susp-iso} uses gluing homeomorphisms and homotopy equivalences from algebraic topology \cite[Ex. 0.14]{Hatcher2002}, \cite[Prop. 2.7 ]{BDJRSX-TOTAL2022}.  
To establish the group-equivariant homotopy equivalence of face lattices, we use an equivariant  Quillen fibre lemma \cite{QFibLemma1978}, \cite{WelkerJCTA1995}. The K\"unneth theorem then gives the isomorphism in homology.

\begin{defn}
  Given graphs $G_1$ and $G_2$ on disjoint vertex sets, a \emph{wedge product} of $G_1$ and $G_2$, $G_1\vee G_2$, is formed by taking one vertex from $G_1$ and one vertex from $G_2$, and identifying them.  Note that a wedge product of two graphs is not unique in general.  
    \end{defn}
%
For example, any tree on $n$ vertices can be obtained as a wedge product of a smaller tree on $n-1$ vertices with the complete graph $K_2$.
    
\begin{thm}\label{thm:Mark-Wedge}
Let $k\geq 2$, and let $G_1$, $G_2$ be graphs. Then $\Delta_k(G_1\vee G_2)$ is shellable if and only if $\Delta_k(G_1)$ and $\Delta_k(G_2)$ are shellable.
\end{thm}  

The cycle graph gives a counterexample (see  \cref{thm:DaneCycleShellability}) to the converse of the next result, offered in 
 the spirit of Fr\"oberg's  \cref{thm:Froberg}.
\begin{prop}\label{prop:chordal-Delta3-shell}
If $G$ is chordal, then $\Delta_3(G)$ is shellable.
\end{prop}
An example of  a chordal graph whose 4-cut complex is not shellable appears in \cref{fig:Ex-Delta4}.

\Cref{cor:induced subgraphs} says that if  $\Delta_k(H)$ is \emph{not} shellable for some induced subgraph $H$ of $G$, then $\Delta_k(G)$ is not shellable. 
  It is thus natural to seek a description of the \emph{minimal} graphs whose $k$-cut complex fails to be shellable, for fixed $k$. We will call such a graph a \emph{minimal forbidden subgraph} for $k$-cut complex shellability.
%
\begin{prop}\label{cor:Delta3-min-forbidden-is3-conn}
Every minimal forbidden subgraph for 3-cut complex shellability is at least 3-connected.
\end{prop}

\section{Reduced Euler characteristics and Betti numbers}\label{sec:Euler-char}
%
Our proofs of the preceding results determine the homotopy type, but do not give Betti numbers.
In this section we present a method for determining the Betti numbers of a cut complex, under certain favourable conditions. 
Recall \cite{RPSEC11997} that the reduced Euler characteristic of a simplicial complex $\Delta$ is the M\"obius number $\mu(\mathcal{L}(\Delta))$ of its face lattice $\mathcal{L}(\Delta)$. The idea is to describe the face poset of the cut complex as a subposet of the truncated Boolean lattice, and then use poset topology techniques as in  
 \cite[Lemma 3.16.4]{RPSEC11997}, \cite[Proposition~1.3]{Jer93} to determine the M\"obius number. 

We say a subset $A$ of the vertex set $V(G)$ of a graph $G$ is \emph{connected} (resp. disconnected) if the induced subgraph $G[A]$ is connected (resp. disconnected). 

 Let $G$ be a graph with vertex set $V(G)$ of size $n$. Let $P(n,k)$ be the truncated Boolean lattice $B_n^{\le n-k}$ of subsets of $[n]$ of size at most $(n-k)$. Clearly the face poset of  $\Delta_k(G)$ is a subposet of $P(n,k)$. Let $A^c$ denote the complement of a subset $A$ of $[n]$, and  define $\mathcal{Z}_k(G)$ to be the subset 
%
$\{A^c\in P(n,k): |A|=k, A \text{ induces a connected subgraph of } G\}.$
%
Thus $\mathcal{Z}_k(G)$ is the set of  maximal elements of $P(n,k)$ which are not facets of the cut complex $\Delta_k(G)$.   Also the number of facets of $ \Delta_k(G)$ is $\binom{n}{k}-|\mathcal{Z}_k(G)|$.
\begin{thm}\label{thm:truncBoolean-minus-antichain} We have the following.
\begin{enumerate}
\item The face poset of $\Delta_k(G)$ is a subposet of $P(n,k)\setminus \mathcal{Z}_k(G)$.
\item The following are equivalent:

(i) The face poset of $\Delta_k(G)$ coincides with  $P(n,k)\setminus \mathcal{Z}_k(G)$.

(ii) Let $A^c\in \mathcal{Z}_k(G)$, $X\subset A^c$, $|X|=(n-k-1)$. Then
$X^c$ contains a disconnected set of size $k$.

(iii) Let $A\subset V(G)$ be connected of size $k$. For every $x\notin A$ 
 there is a $y\in A$  such that $(A\setminus\{y\})\cup\{x\}$ is disconnected.
%
\item If any condition in Part (2.) holds, the reduced Euler characteristic $\mu(\Delta_k(G))$ of $\Delta_k(G)$ is given by 
\begin{center}{$(-1)^{n-k-1}\mu(\Delta_k(G))=\binom{n-1}{k-1}- |\mathcal{Z}_k(G)|
=|\{F: F \text{ is a facet of }\Delta_k(G)\}| -\binom{n-1}{k}.$}\end{center}
%
Furthermore, in this case the nonzero homology of $\Delta_k(G)$ is torsion-free and occurs in at most two dimensions, $n-k-1$ and $n-k-2$.
%
\item If any  condition in Part (2.) holds and $\Delta_k(G)$ is shellable, then 
 it is homotopy equivalent to a wedge of $|\mu(\Delta_k(G))|$ spheres in dimension $n-k-1$. It is contractible if $\mu(\Delta_k(G))=0$.
\end{enumerate}
\end{thm}
%
The technical conditions in Part (2.) above, as well as variations, hold for several common families of graphs, including trees, cycles and grid graphs.

\section{Families of Graphs}\label{sec:Families}
We now examine specific classes of graphs.   \cref{thm:truncBoolean-minus-antichain}  can be applied to compute Betti numbers for cut complexes of forests and cycles, which satisfy  
the conditions in Part (2.) of \cref{thm:truncBoolean-minus-antichain}.

\vskip.05in
\noindent 
\textbf{\textit{Trees}}

Recall that for every $k$, the $k$-cut complex of the complete graph $K_2$ is the void complex (\cref{ex:Examples-cut-complex}).  Since trees may be recursively constructed by taking a wedge with $K_2$, and forests are disjoint unions of trees, \cref{thm:MargeDisjunion,thm:Mark-Joins} give:

\begin{prop}\label{cor:Mark-trees}
    If $G$ is a forest, $\Delta_k(G)$ is shellable for all $k\geq 2$.
    \end{prop}

For any (finite) graph $G$, let $\tau_k(G)$ denote the number of subtrees of $G$ with $k$ vertices. We have $\tau_2(\F_n)=n-c,$ where $c$ is the number of connected components of the forest $\F_n$.  If the tree is a path $P_n$, then $\tau_k(P_n)=(n-k+1)$.  
From \cref{thm:truncBoolean-minus-antichain}, we obtain:

\begin{thm}\label{prop:cut-complex-trees} Let $\mathcal{F}_n$ be a forest on $n$ vertices. 
Then the shellable cut complex
 $\Delta_k(\mathcal{F}_n)$ is homotopy equivalent to a wedge of $\left( \binom{n-1}{k-1} -\tau_k(\mathcal{F}_n)\right)$ spheres in dimension $(n-k-1)$ if this number is nonzero, and contractible otherwise.  

 In particular, for a tree $T_n$ on $n$ vertices, $\Delta_k(T_n)$ is contractible if $k=2$, and has the homotopy type of a wedge of 
$\binom{n-1}{k-1}-\tau_k(T_n)$ spheres of dimension $(n-k-1)$ if $k\ge 3$.
\end{thm}

\noindent 
\textbf{\textit{Cycles}}

For the cycle graph $C_n,$  we may assume $n\ge 4$ and $2\le k\le n-2.$    If $n=4,$ the one-dimensional cut complex  $\Delta_2(C_4)$ has two facets $\{1,3\}$ and $\{2,4\},$ and is homotopy equivalent to the 0-sphere $\bbS^0;$  it is thus not shellable. 

Recall from \cref{fig:Delta2C5} that the 2-dimensional cut complex $\Delta_2(C_5)$ is in fact a M\"obius strip, and hence it is homotopy equivalent to the one-sphere $\bbS^1$. 
Using a discrete Morse matching \cite{JonssonBook2008}, it was shown more generally in  \cite{BDJRSX-TOTAL2022} that:
\begin{prop}[{\cite[Theorem~3.9]{BDJRSX-TOTAL2022}}] \label{prop:MarijaDMT-Delta2cycle}
Let $C_n$ be a cycle graph, $n \in \mathbb{N},$ and $n \ge 5.$  
Then the $(n-3)$-dimensional  cut complex $\Delta_2(C_n)$ is homotopy equivalent to the sphere $\bbS^{n-4}.$ 
%Consequently, complex $\Delta_2(C_n)$ is not shellable. 
\end{prop}
We show that for $k\ge 3$, the cut complex of the cycle graph is shellable. The Betti number follows by verifying the conditions in \cref{thm:truncBoolean-minus-antichain}.
%
\begin{thm}\label{thm:DaneCycleShellability}
	For all $ n>k>2 $, the $(n-k-1)$-dimensional cut complex $\Delta_{k}(C_n) $  is shellable. 
It has the homotopy type of a wedge of $\binom{n-1}{k-1}-n$ spheres of dimension $(n-k-1).$  
\end{thm}

\noindent 
\textbf{\textit{Bipartite graphs}}

Let $E_n$ denote the edgeless graph on $n$ vertices. 
The complete bipartite graph $K_{m,n}$ is the join of two edgeless graphs $E_m$ and $E_n$. 
We use the structural result of \cref{thm:susp-of-joins2022Sept12}, completely determining both the homotopy type and homology representation for the cut complexes of all  complete multipartite graphs.  For lack of space we state our results only for the complete bipartite case.

 Let $V_{\lambda}$ denote the irreducible module of the symmetric group $\mathfrak{S}_n$ indexed by the integer partition $\lambda$ of $n$.
The  group $\mathfrak{S}_m\times \mathfrak{S}_n$ 
 (resp. the wreath product $\mathfrak{S}_2[\mathfrak{S}_n]$) 
% of $K_{m,n}$ acts simplicially on $\Delta_k(K_{m,n}), m\ne n,$ (resp. $m=n$), and hence 
induces a representation on the rational homology of $\Delta_k(K_{m,n}), m\ne n,$ (resp. $m=n$). 

From \cref{thm:Mark-Joins}, \cref{thm:susp-of-joins2022Sept12} and \cref{prop:Deltak-edgeless-graph-homrepS}, we have, since $K_{m,n}=E_m*E_n$:
\begin{thm} \label{thm:bipartite}
Let $1\le m\le n$ and $2\le k$.  Then 
$\Delta_k(K_{m,n})$ is shellable if and only if  $m<k$.
Furthermore, if $m<k\le n$, then $\Delta_k(K_{m,n})$ is contractible, and if $k>n$, the cut complex is void and hence shellable. 


If $k\le m \le n$, the $(m+n-k-1)$-dimensional complex $\Delta_k(K_{m,n})$ is homotopy equivalent to a wedge of $\binom{m-1}{k-1}\binom{n-1}{k-1}$ spheres of dimension $m+n-2k$.

The representation of $\mathfrak{S}_m\times \mathfrak{S}_n$ on the rational homology is
the irreducible $V_{(k, 1^{m-k})}\otimes V_{ (k, 1^{n-k})}$ indexed by the pair of integer partitions $((k, 1^{m-k}), (k, 1^{n-k})).$


If $m=n,$  the representation of  
$\mathfrak{S}_2[\mathfrak{S}_n]$ 
%on the rational homology of the cut complex
 is $\Phi_{\mathfrak{S}_2}[V_{(k, 1^{n-k})}],$
where 
%the one-dimensional representation 
$\Phi_{\mathfrak{S}_2}$ equals $\mathrm{sgn}^{n-k-1},$ and $\mathrm{sgn}$ is the sign representation of $\mathfrak{S}_2.$
%
\end{thm}
The last statement uses {\cite[Proposition 2.3]{Jer93}} to compute the homology representation for a product of posets.


The  homotopy type and homology representation  determined  in  \cref{thm:bipartite} bear a striking resemblance to that of a complex studied by  Linusson, Shareshian and Welker  \cite[Theorem 1.4, Conjecture 1.15]{LinShareshWelker2008}, a connection we propose to explore further. 
%
\vskip.2in

\noindent
\textbf{\textit{Grid Graphs}}

The $m$ by $n$ grid graph $G(m,n)$ is the Cartesian product of two paths, $P_m\times P_n$.  Here we describe our most significant results on grid graphs.  The first result is proved by a discrete Morse matching \cite{JonssonBook2008}.

\begin{thm}\cite[Theorem~3.10]{BDJRSX-TOTAL2022}\label{thm:grid-k=2MyMorseMatching2021Sept} For $n, m\ge 2,$ the $(mn-3)$-dimensional cut complex\linebreak[4] $\Delta_2 (G(m,n))$ has  the homotopy type of a wedge of $(m-1)(n-1)$ spheres of dimension $mn-4$.
\end{thm}

Complexes associated to grid graphs appear to be  difficult to analyse.
We obtain shellability of $\Delta_3(G(m,n))$ below  as an unexpected corollary of \cref{cor:Delta3-min-forbidden-is3-conn}. 
 The Betti number is the result of a generalisation of \cref{thm:truncBoolean-minus-antichain}, exploiting the fact that grid graphs are triangle-free.
\begin{thm}\label{prop:BettiNumberDelta3GridGraph} Let $m,n\ge 2$. The 3-cut complex $\Delta_3(G(m,n))$ is shellable and has the homotopy type of a wedge of
%
$\binom{mn-1}{2} -5mn+5(m+n)-3 $
spheres in dimension $m+n-4$.
\end{thm}

 For $k=4,6,$ we use poset topology tools to show that the homology of $\Delta_k(G(m,n))$ is torsion-free and concentrated in the top two dimensions, and give formulas for the reduced Euler characteristic.  

We conjecture that $\Delta_k(G(m,n))$ is shellable for $mn-3\ge k\ge 4$.

\begin{acknowledgements} {We thank the organizers of the 2021 Graduate Research Workshop in Combinatorics, where this work originated, and Natalie Behague, Dane Miyata, and George Nasr for their early contributions to our project. Marija Jeli\'c Milutinovi\'c has been supported by the Project No.\ 7744592 MEGIC ``Integrability and Extremal Problems in Mechanics, Geometry and Combinatorics'' of the Science Fund of Serbia, and by the Faculty of Mathematics University of Belgrade through the grant (No.\ 451-03-68/2022-14/200104) by the Ministry of Education, Science, and Technological Development of the Republic of Serbia. Rowan Rowlands was partially supported by a graduate fellowship from NSF grant DMS-1953815.}
\end{acknowledgements}

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography



\end{document}
