% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} \usepackage{color, tikz} % Please remove all other commands that change parameters such as % margins or pagesizes. % only use standard LaTeX packages % only include packages that you actually need % we recommend these ams packages \usepackage{amsthm,amsmath,amssymb} % we recommend the graphicx package for importing figures \usepackage{graphicx} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins % declare theorem-like environments \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{prop}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \newtheorem{construction}[theorem]{Construction} \newtheorem{algorithm}[theorem]{Algorithm} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} % set special commands \newcommand{\conv}[1]{\mathrm{conv}\{#1\}} \newcommand{\RR}{\mathbb{R}} \newcommand{\ZZ}{\mathbb{Z}} \newcommand{\QQ}{\mathbb{Q}} \newcommand{\CC}{\mathbb{C}} \newcommand{\rank}{\mathrm{rank }} \newcommand{\Ind}{\mathrm{Ind}} % create TO DO and NOTE boxes, plus comment out feature %\newcommand{\todo}[1]{\par \noindent % \framebox{\begin{minipage}[c]{0.95 \textwidth} TO DO: % #1 \end{minipage}}\par} %\newcommand{\note}[1]{\par \noindent % \framebox{\begin{minipage}[c]{0.95 \textwidth} NOTE: % #1 \end{minipage}}\par} \newcommand\commentout[1]{} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title{\bf Matching and Independence Complexes Related to Small Grids} % input author, affilliation, address and support information as follows; % the address should include the country, and does not have to include % the street address \author{Benjamin Braun\thanks{Partially supported by grant H98230-16-1-0045 from the U.S. National Security Agency.}\\ \small Department of Mathematics\\[-0.8ex] \small University of Kentucky\\[-0.8ex] \small Lexington, KY 40506 U.S.A.\\ \small\tt benjamin.braun@uky.edu\\ \and Wesley K. Hough \\ \small Department of Mathematics\\[-0.8ex] \small University of Wisconsin - Whitewater\\[-0.8ex] \small Whitewater, WI 53190 U.S.A.\\ \small\tt houghw@uww.edu } % \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \date{\dateline{??}{??}\\ \small Mathematics Subject Classifications: 05C69, 05E45} \begin{document} \maketitle \begin{abstract} The topology of the matching complex for the $2\times n$ grid graph is mysterious. We describe a discrete Morse matching for a family of independence complexes $\Ind(\Delta_n^m)$ that include these matching complexes. Using this matching, we determine the dimensions of the chain spaces for the resulting Morse complexes and derive bounds on the location of non-trivial homology groups for certain $\Ind(\Delta_n^m)$. Furthermore, we determine the Euler characteristic of $\Ind(\Delta_n^m)$ and prove that several homology groups of $\Ind(\Delta_n^m)$ are non-zero. % keywords are optional \bigskip\noindent \textbf{Keywords:} Grid Graphs; Independence Complexes; Recursions; Homology \end{abstract} %Begin body of document %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Introduction}\label{sec:intro} Consider a simple graph $G = (V(G),E(G))$. A \textit{matching} on $G$ is a subgraph $H = (V(G),S)$ with $S \subseteq E(G)$ and maximum vertex degree 1. We make no distinction between a matching and its edge set $S$. The \textit{matching complex of $G$}, denoted $M(G)$, is the simplicial complex with vertex set $E(G)$ and faces given by the matchings on $G$. We find it useful to reframe matchings in the language of independent sets as follows. An \textit{independent set} in a graph $G$ is a set $T \subseteq V(G)$ such that no two elements of $T$ are adjacent in $G$. The \textit{independence complex of $G$}, denoted $\Ind(G)$, is the abstract simplicial complex with vertex set $V(G)$ and faces given by the independent sets in $G$. Recall that the \textit{line graph} of $G$, denoted $L(G)$, has vertex set $E(G)$ with two vertices of $L(G)$ adjacent if they are adjacent edges in $G$. A key observation is that $M(G) = \Ind(L(G))$ for a finite simple graph $G$. Recall that the \textit{simplicial join} of two abstract simplicial complexes $\Delta$ and $\Gamma$ is the abstract simplicial complex $\Delta \ast \Gamma = \{\sigma \cup \tau \ | \ \sigma \in \Delta, \tau \in \Gamma\}$. It is straightforward from this definition to verify that $\Ind(A \biguplus B) \cong \Ind(A) \ast \Ind(B)$ and $M(A \biguplus B) \cong M(A) \ast M(B)$ for graphs $A$ and $B$, where $\biguplus$ denotes the disjoint union. For the path on $n$ vertices (denoted $Pa_n$) and the cycle on $n$ vertices (denoted $C_n$), the homotopy type of the matching and independence complexes are known \cite{KozlovIndCycles}; see also \cite[Section~11.4]{JonssonBook}. However, matching and independence complexes quickly become quite complicated, e.g. \cite{AdamaszekSpecial, BarmakStar, Bouc, BraunIndComplexKneser, WachsDongLaplacian, EarlEtAl, JonssonMoreTorsion, ShareshianWachsTopHomology, VrecicaZivaljevicCycleFree, WachsTopologyMatching}. Jonsson \cite{JonssonBook} provides a thorough survey regarding these and other simplicial complexes arising from graphs, including special emphasis on the matching complex for complete graphs and complete bipartite graphs. We focus our attention in this paper on $G(2,n)$, the $2 \times n$ grid graph with $V = \{1,2\} \times [n]$ and where two vertices $(x_0,y_0)$ and $(x_1,y_1)$ are adjacent when their Euclidean distance is exactly 1. \begin{definition} We define $\Gamma_n := G(2,n+2)$ and $D_n := L(\Gamma_n)$. The indexing shift is chosen so that $n$ is the number of interior rungs on the ladder of $\Gamma_n$ as well as the number of interior vertices of degree $4$ in $D_n$. For example, $\Gamma_3$ and $D_3$ are isomorphic to the graphs below, respectively. \end{definition} \begin{figure}[h] \label{fig:Gamma3D3} \centering \begin{tikzpicture}[scale=1.25] \draw [fill] (0,0) circle [radius=0.066]; \draw [fill] (1,0) circle [radius=0.066]; \draw [fill] (2,0) circle [radius=0.066]; \draw [fill] (3,0) circle [radius=0.066]; \draw [fill] (4,0) circle [radius=0.066]; \draw [fill] (0,1) circle [radius=0.066]; \draw [fill] (1,1) circle [radius=0.066]; \draw [fill] (2,1) circle [radius=0.066]; \draw [fill] (3,1) circle [radius=0.066]; \draw [fill] (4,1) circle [radius=0.066]; \draw [ultra thick] (0,0)--(1,0)--(2,0)--(3,0)--(4,0); \draw [ultra thick] (0,1)--(1,1)--(2,1)--(3,1)--(4,1); \draw [ultra thick] (0,0)--(0,1); \draw [ultra thick] (1,0)--(1,1); \draw [ultra thick] (2,0)--(2,1); \draw [ultra thick] (3,0)--(3,1); \draw [ultra thick] (4,0)--(4,1); \end{tikzpicture} \hspace{0.5in} \begin{tikzpicture}[scale=1.25] \draw [fill] (-0.5,0.5) circle [radius=0.066]; \draw [fill] (0.5,0.5) circle [radius=0.066]; \draw [fill] (1.5,0.5) circle [radius=0.066]; \draw [fill] (2.5,0.5) circle [radius=0.066]; \draw [fill] (3.5,0.5) circle [radius=0.066]; \draw [fill] (0,0) circle [radius=0.066]; \draw [fill] (0,1) circle [radius=0.066]; \draw [fill] (1,0) circle [radius=0.066]; \draw [fill] (1,1) circle [radius=0.066]; \draw [fill] (2,0) circle [radius=0.066]; \draw [fill] (2,1) circle [radius=0.066]; \draw [fill] (3,0) circle [radius=0.066]; \draw [fill] (3,1) circle [radius=0.066]; \draw [ultra thick] (-0.5,0.5)--(0,0)--(0.5,0.5)--(1,0)--(1.5,0.5)--(2,0)--(2.5,0.5)--(3,0)--(3.5,0.5); \draw [ultra thick] (-0.5,0.5)--(0,1)--(0.5,0.5)--(1,1)--(1.5,0.5)--(2,1)--(2.5,0.5)--(3,1)--(3.5,0.5); \draw [ultra thick] (0,0)--(1,0)--(2,0)--(3,0); \draw [ultra thick] (0,1)--(1,1)--(2,1)--(3,1); \end{tikzpicture} \caption{$\Gamma_3$ and $D_3$} \end{figure} In an unpublished manuscript \cite{JonssonMatchingGrids}, Jonsson establishes basic results regarding the matching complexes for $\Gamma_n$ and more general grid graphs. For example, Jonsson shows that the homotopical depth of $M(\Gamma_n)$ is $\lceil 2n/3\rceil$, which implies that this skeleton of the complex is a wedge of spheres. However, Jonsson states \cite[page~3]{JonssonMatchingGrids} that ``it is probably very hard to determine the homotopy type of'' matching complexes of grid graphs. In \cite{LinussonGridGraphs}, Bousquet-M\'{e}lou, Linusson, and Nevo introduced \textit{matching trees} as a way to apply discrete Morse theory to study independence complexes of simple graphs. In this paper, we will use matching trees to produce a Morse matching on the face poset of $M(\Gamma_n) = \Ind(D_n)$. Our matching algorithm has a recursive structure that allows us to enumerate the number and dimension of cells in a cellular complex homotopy equivalent to $\Ind(D_n)$. We then use this recursion to determine topological properties of $\Ind(D_n)$. Our techniques actually apply to independence complexes of a larger class of graphs that include the $D_n$ graphs. Before introducing these more general graphs, we need to define a family of useful related graphs. \begin{definition} For $m \geq 1$ and $n \geq 1$, let $\widehat{Y}^m_n$ be two vertices connected by $m$ disjoint paths each having $n+1$ edges. We ignore the degenerate cases $m=0$ and $n=0$. For example, $\widehat{Y}^3_4$ is isomorphic to the graph below. Also, observe that $\widehat{Y}^1_n \cong Pa_{n+2}$ and $\widehat{Y}^2_n \cong C_{2n+2}$. \end{definition} \begin{figure}[h] \label{fig:Yhatgraph} \centering \begin{tikzpicture} \draw [fill] (-1,1) circle [radius=0.1]; \draw [fill] (4,1) circle [radius=0.1]; \draw [fill] (0,0) circle [radius=0.1]; \draw [fill] (1,0) circle [radius=0.1]; \draw [fill] (2,0) circle [radius=0.1]; \draw [fill] (3,0) circle [radius=0.1]; \draw [fill] (0,1) circle [radius=0.1]; \draw [fill] (1,1) circle [radius=0.1]; \draw [fill] (2,1) circle [radius=0.1]; \draw [fill] (3,1) circle [radius=0.1]; \draw [fill] (0,2) circle [radius=0.1]; \draw [fill] (1,2) circle [radius=0.1]; \draw [fill] (2,2) circle [radius=0.1]; \draw [fill] (3,2) circle [radius=0.1]; \draw [ultra thick] (-1,1)--(0,0)--(1,0)--(2,0)--(3,0)--(4,1); \draw [ultra thick] (-1,1)--(0,1)--(1,1)--(2,1)--(3,1)--(4,1); \draw [ultra thick] (-1,1)--(0,2)--(1,2)--(2,2)--(3,2)--(4,1); \end{tikzpicture} \caption{$\widehat{Y}^3_4$} \end{figure} We will impose a specific labeling on these $\widehat{Y}^m_n$ graphs for use throughout this paper: the leftmost vertex is $a$, the rightmost vertex is $b$, and the $k$-th vertex away from $a$ on the $j$-th path is $(j,k)$. \begin{definition} Let $\Delta^m_n$ denote the (labeled) graph $\widehat{Y}^m_{n+1}$ with $n$ additional vertices labeled $\{1, \dots, n\}$ and edges $\{k,(j,k)\}$ and $\{k,(j,k+1)\}$ for each $j \in [m]$ and each $k \in [n]$. As an example, $\Delta^4_3$ is depicted in the figure below. The indexing convention is chosen so that $n$ is the number of interior vertices of degree $2m$. Therefore, we further define $\Delta^m_0 := \widehat{Y}^m_1$ and $\Delta^m_{-1} := K_1$ where $K_1$ denotes an isolated vertex with no loops. \end{definition} It is straightforward to verify that $\Delta^2_n = D_n$, and hence $\Delta_n^m$ is a family generalizing $D_n$. \begin{figure}[h] \label{fig:Delta43labeled} \centering \begin{tikzpicture} \draw [fill] (-1,1.5) circle [radius=0.075] node[left] {\footnotesize $a$}; \draw [fill] (1,1.5) circle [radius=0.075] node[yshift=0.3cm] {\footnotesize $1$}; \draw [fill] (3,1.5) circle [radius=0.075] node[yshift=0.3cm] {\footnotesize $2$}; \draw [fill] (5,1.5) circle [radius=0.075] node[yshift=0.3cm] {\footnotesize $3$}; \draw [fill] (7,1.5) circle [radius=0.075] node[right] {\footnotesize $b$}; \draw [fill] (0,0) circle [radius=0.075] node[below] {\footnotesize $(4,1)$}; \draw [fill] (2,0) circle [radius=0.075] node[below] {\footnotesize $(4,2)$}; \draw [fill] (4,0) circle [radius=0.075] node[below] {\footnotesize $(4,3)$}; \draw [fill] (6,0) circle [radius=0.075] node[below] {\footnotesize $(4,4)$}; \draw [fill] (0,1) circle [radius=0.075] node[below] {\footnotesize $(3,1)$}; \draw [fill] (2,1) circle [radius=0.075] node[below] {\footnotesize $(3,2)$}; \draw [fill] (4,1) circle [radius=0.075] node[below] {\footnotesize $(3,3)$}; \draw [fill] (6,1) circle [radius=0.075] node[below] {\footnotesize $(3,4)$}; \draw [fill] (0,2) circle [radius=0.075] node[above] {\footnotesize $(2,1)$}; \draw [fill] (2,2) circle [radius=0.075] node[above] {\footnotesize $(2,2)$}; \draw [fill] (4,2) circle [radius=0.075] node[above] {\footnotesize $(2,3)$}; \draw [fill] (6,2) circle [radius=0.075] node[above] {\footnotesize $(2,4)$}; \draw [fill] (0,3) circle [radius=0.075] node[above] {\footnotesize $(1,1)$}; \draw [fill] (2,3) circle [radius=0.075] node[above] {\footnotesize $(1,2)$}; \draw [fill] (4,3) circle [radius=0.075] node[above] {\footnotesize $(1,3)$}; \draw [fill] (6,3) circle [radius=0.075] node[above] {\footnotesize $(1,4)$}; \draw [ultra thick] (-1,1.5)--(0,0)--(2,0)--(4,0)--(6,0)--(7,1.5); \draw [ultra thick] (-1,1.5)--(0,1)--(2,1)--(4,1)--(6,1)--(7,1.5); \draw [ultra thick] (-1,1.5)--(0,2)--(2,2)--(4,2)--(6,2)--(7,1.5); \draw [ultra thick] (-1,1.5)--(0,3)--(2,3)--(4,3)--(6,3)--(7,1.5); \draw [ultra thick] (0,0)--(1,1.5)--(2,0)--(3,1.5)--(4,0)--(5,1.5)--(6,0); \draw [ultra thick] (0,1)--(1,1.5)--(2,1)--(3,1.5)--(4,1)--(5,1.5)--(6,1); \draw [ultra thick] (0,2)--(1,1.5)--(2,2)--(3,1.5)--(4,2)--(5,1.5)--(6,2); \draw [ultra thick] (0,3)--(1,1.5)--(2,3)--(3,1.5)--(4,3)--(5,1.5)--(6,3); \end{tikzpicture} \caption{Labeled $\Delta^4_3$} \end{figure} The article is structured as follows. In Section~\ref{sec:background}, we review discrete Morse theory and matching trees for independence complexes. In Section~\ref{sec:comb}, we describe a matching tree procedure for $\Ind(\Delta_n^m)$ which we call the Comb Algorithm. This matching tree produces a cellular complex $X^m_n$ that is homotopy equivalent to $\Ind(\Delta^m_n)$. In Section~\ref{sec:results}, we use the Comb Algorithm to establish enumerative properties regarding dimensions of the chain spaces of $X^m_n$. Finally, in Section~\ref{sec:hom}, we apply these enumerative results to derive some homological properties of $\Ind(\Delta^m_n)$. We conclude with two questions for further research. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Discrete Morse Theory} \label{sec:background} In this section, we introduce tools from discrete Morse theory. Discrete Morse theory was introduced by R.~Forman in \cite{FormanMorseTheory} and has since become a standard tool in topological combinatorics. Similar ideas were developed around the same time by Brown~\cite{Brown1992} and Chari~\cite{Chari2000}. The main idea of simplicial discrete Morse theory is to pair cells in a simplicial complex in a manner that allows them to be cancelled via elementary collapses, which reduces the complex under consideration to a homotopy-equivalent cellular complex, typically having fewer cells. Further details regarding the following definitions and theorems can be found in~\cite{JonssonBook} and~\cite{KozlovBook}. \begin{definition} \label{Morsedef} A \textit{partial matching} on a poset $P$ is a subset $\mu \subseteq P \times P$ such that \begin{itemize} \item $(a,b) \in \mu$ implies $b$ covers $a$, and \item each $a \in P$ belongs to at most one element in $\mu$. \end{itemize} When $(a,b) \in \mu$, we write $a = d(b)$ and $b = u(a)$. A partial matching on $P$ is \textit{acyclic} if there does not exist a cycle of the form $$b_1 > d(b_1) < b_2 > d(b_2) < \cdots < b_n > d(b_n) < b_1$$ with $n\geq 2$ and all $b_i\in P$ being distinct. Given an acyclic partial matching $\mu$ on $P$, we say that the unmatched elements of $P$ are \textit{critical}. \end{definition} The following theorem asserts that an acyclic partial matching on the face poset of a polyhedral cell complex is exactly the pairing needed to produce the homotopy equivalence promised by discrete Morse theory. \begin{theorem} \label{mainmorse} {\rm (Main Theorem of Discrete Morse Theory, \cite[Proposition 1]{Brown1992}, \cite[Proposition 3.3]{Chari2000} )}. Let $\Delta$ be a polyhedral cell complex, and let $\mu$ be an acyclic partial matching on the face poset of $\Delta$. If $c_i$ denotes the number of critical $i$-dimensional cells of $\Delta$, then the space $\Delta$ is homotopy equivalent to a cell complex $\Delta_c$ with $c_i$ cells of dimension $i$ for each $i\geq 0$, plus a single $0$-dimensional cell in the case where the empty set is paired in the matching. \end{theorem} We now define how to create a matching tree on a simple graph $G=(V,E)$. For $A,B \subseteq V$ such that $A \cap B = \emptyset$, let $$ \Sigma(A,B) := \left\{ I \in \mbox{Ind}(G) : A \subseteq I \phantom{.} \mathrm{and} \phantom{.} B \cap I = \emptyset \right\}.$$ For a vertex $p\in V(G)$, let $N(p)$ denote the neighbors of $p$ in $G$. A \emph{matching tree} $\tau(G)$ for $G$ is a directed tree constructed according to the following algorithm. \begin{algorithm}[Matching Tree Algorithm, MTA] Begin by letting $\tau(G)$ be a single node labeled $\Sigma(\emptyset,\emptyset)$. \textbf{WHILE} $\tau(G)$ has a leaf node $\Sigma(A,B)$ with out-degree 0 and $|\Sigma(A,B)| \geq 2$, \textbf{DO ONE OF THE FOLLOWING:} \begin{enumerate} \item If there exists a vertex $p \in V \setminus (A \cup B)$ such that $N(p) \subseteq (A \cup B)$, create a directed edge from $\Sigma(A,B)$ to a new node labeled $\emptyset_p$. Refer to $p$ as a \emph{free vertex} of $\tau(G)$. \medskip \item If there exist vertices $p \in V \setminus (A \cup B)$ and $v \in N(p)$ such that $N(p) \setminus (A \cup B) = \{v\}$, create a directed edge from $\Sigma(A,B)$ to a new node labeled $\Sigma(A \cup \{v\}, B \cup N(v))$. Refer to $v$ as a \emph{matching vertex} of $\tau(G)$ with respect to $p$. \medskip \item Choose a vertex $v \in V \setminus (A \cup B)$ and created two directed edges from $\Sigma(A,B)$ to new nodes labeled $\Sigma(A, B \cup \{v\})$ and $\Sigma(A \cup \{v\}, B \cup N(v))$. Refer to $v$ as a \emph{splitting vertex} of $\tau(G)$. \end{enumerate} The node $\Sigma(\emptyset,\emptyset)$ is called the \emph{root} of the matching tree, while any non-root node of out-degree $1$ in $\tau(G)$ is called a \emph{matching site} of $\tau(G)$ and any non-root node of out-degree $2$ is called a \emph{splitting site} of $\tau(G)$. \end{algorithm} Steps 2 and 3 of the above algorithm ensure that for any $\Sigma(A,B)$ in $\tau(G)$, $a \in A$ implies $N(a) \in B$. Hence, if $p \notin A \cup B$, neither $p$ nor any of its neighbors are in $A$. For a vertex $p$ satisfying the hypotheses of Step 1, we know that all neighbors of $p$ are in $B$ since $N(p) \subseteq (A \cup B)$. Consequently, given $\sigma \in \Sigma(A,B)$, we also have $\sigma \cup \{p\} \in \Sigma(A,B)$, which means we may pair $\sigma$ and $\sigma \cup \{p\}$ in the face poset of $\Ind(G)$. Similarly, for vertices $p$ and $v$ satisfying the hypotheses of Step 2, all of $p$'s neighbors (except for $v$) are in $B$. Note that performing Step 3 with this choice of $v$ implies that the branch with $\Sigma(A, B\cup\{v\})$ has $p$ as a free vertex, so we can then perform Step 1 on that branch. This two-step sequence is an equivalent operation to performing Step 2 itself. Also, note that the empty set is always matched at the last node of the form $\Sigma(\emptyset, B)$. A key observation from \cite{LinussonGridGraphs} is that a matching tree on $G$ yields an acyclic partial matching on the face poset of $\Ind(G)$ as follows. \begin{theorem}[\cite{LinussonGridGraphs}, Section~2] A matching tree $\tau(G)$ for $G$ yields an acyclic partial matching on the face poset of $\Ind(G)$ whose critical cells are given by the non-empty sets $\Sigma(A,B)$ labeling non-root leaves of $\tau(G)$. In particular, for such a set $\Sigma(A,B)$, the set $A$ is a critical cell in $\Ind(G)$. \end{theorem} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{The Comb Matching Algorithm}\label{sec:comb} In this section, we define a specific matching tree for the $\Ind(\Delta^m_n)$ complexes. First, it is appropriate to determine the homotopy type of $\Ind(Y^m_n)$ and $\Ind(\widehat{Y}^m_n)$, where $Y^m_n$ (defined below) is a graph related to $\widehat{Y}^m_n$. \begin{definition} For $m \geq 1$ and $n \geq 1$, let $Y^m_n$ denote the extended star graph with a central vertex of degree $m$ and paths of $n$ edges emanating outward. We refer to each of these paths as a \textit{tendril}. We ignore the degenerate cases $m=0$ and $n=0$ as we did with $\widehat{Y}^m_n$. \end{definition} As an example, $Y^3_4$ is isomorphic to the graph below. Observe that removing one of the vertices of degree $m$ and all of its edges from $\widehat{Y}^m_n$ produces $Y^m_n$. Also, observe that $Y^1_n \cong Pa_{n+1}$ and $Y^2_n \cong Pa_{2n+1}$. \begin{figure}[h] \label{fig:Ygraph} \centering \begin{tikzpicture} \draw [fill] (-1,1) circle [radius=0.1]; \draw [fill] (0,0) circle [radius=0.1]; \draw [fill] (1,0) circle [radius=0.1]; \draw [fill] (2,0) circle [radius=0.1]; \draw [fill] (3,0) circle [radius=0.1]; \draw [fill] (0,1) circle [radius=0.1]; \draw [fill] (1,1) circle [radius=0.1]; \draw [fill] (2,1) circle [radius=0.1]; \draw [fill] (3,1) circle [radius=0.1]; \draw [fill] (0,2) circle [radius=0.1]; \draw [fill] (1,2) circle [radius=0.1]; \draw [fill] (2,2) circle [radius=0.1]; \draw [fill] (3,2) circle [radius=0.1]; \draw [ultra thick] (-1,1)--(0,0)--(1,0)--(2,0)--(3,0); \draw [ultra thick] (-1,1)--(0,1)--(1,1)--(2,1)--(3,1); \draw [ultra thick] (-1,1)--(0,2)--(1,2)--(2,2)--(3,2); \end{tikzpicture} \caption{$Y^3_4$} \end{figure} Since $Y^m_n$ is a tree for $m \geq 1$ and $n \geq 0$, we know by work of Ehrenborg and Hetyei \cite{EhrenborgHetyei} that $\Ind(Y^m_n)$ is either contractible or homotopy equivalent to a single sphere. \begin{lemma} \label{starlem} For $m \geq 1$ and $n \geq 0$, \[ \Ind(Y^m_n) \simeq \left\{ \begin{array}{ll} \ast &\mbox{if } n=3k \\ S^{mk} &\mbox{if } n=3k+1 \\ S^{m(k+1)-1} &\mbox{if } n=3k+2 \\ \end{array} \right. \, . \] \end{lemma} \begin{proof} \textbf{\underline{Case 1}:} $n = 3k$. We use induction on $m$. If $m = 1$, then $Y^1_n \cong Pa_{3k+1}$; hence, $\Ind(Y^1_n)$ is contractible by \cite[Prop~11.16]{KozlovBook}. Suppose the induction hypothesis holds for $\ell < m$. Select a tendril of $Y^m_n$ and label the vertices $1$ through $n$ starting at the leaf. We consider a matching tree on $\Ind(Y^m_n)$. Perform Step~2 of the MTA with $p=1$ and $v=2$. Repeat with $p=4$ and $v=5$ and so on, modulo $3$. Since $n=3k$, we will eventually perform Step~2 with $p = n-2$ and $v = n-1$. The remaining subgraph of $Y^m_n$ from which we may select vertices is isomorphic to $Y^{m-1}_n$. Since $\Ind(Y^{m-1}_n)$ is contractible by assumption, $\Ind(Y^m_n)$ is contractible as well. \textbf{\underline{Case 2}:} $n=3k+1$ or $n=3k+2$. Let $a$ be the vertex of degree $m$ in $Y^m_n$. We again consider a matching tree on $\Ind(Y^m_n)$. We apply Step~3 of the MTA with $v = a$. At the $\Sigma(\{a\}, N(a))$ and $\Sigma(\emptyset, \{a\})$ nodes, the remaining subgraphs of $Y^m_n$ from which we may select vertices are isomorphic to an $m$-fold disjoint union of $Pa_{n-1}$'s and an $m$-fold disjoint union of $Pa_{n}$'s respectively. When $n=3k+1$, the union of $Pa_n$'s is contractible by \cite[Prop~11.16]{KozlovBook}, and each subcomplex $\Ind(Pa_{n-1})$ contributes $\left\lfloor \frac{n-2}{3} \right\rfloor + 1 = k$ vertices toward a single critical cell. In total, the vertex $a$ and the vertices from each $\Ind(Pa_{n-1})$ factor combine to form a single critical cell of dimension $mk$. When $n=3k+2$, the union of the $Pa_{n-1}$'s is contractible by \cite[Prop~11.16]{KozlovBook}, and each subcomplex $\Ind(Pa_n)$ contributes $\left\lfloor \frac{n-1}{3} \right\rfloor + 1 = k+1$ vertices toward a single critical cell. In total, the vertices from each $\Ind(Pa_n)$ factor combine to form a single critical cell of dimension $m(k+1)-1$. This gives the result. \end{proof} \begin{remark} An alternative method of proof relies on the fact that, when $N(v) \subseteq N(w)$, $\Ind(G)$ collapses onto $\Ind(G \backslash w)$ per \cite[Lemma~3.2]{EngstromIndependence} and \cite[Prop~3.1]{AdamaszekSplittings}. On each tendril of an arbitrary $Y^m_n$, set $v$ equal to the leaf, set $w$ equal to the vertex two vertices in from the leaf, and then use this result to obtain that $\Ind(Y^m_n)$ is homotopy-equivalent to the independence complex of the disjoint union of $Y^m_{n-3}$ and $m$ copies of $K_2$. Hence, $\Ind(Y^m_n)~\simeq~\mathrm{susp}^m(\Ind(Y^m_{n-3}))$. It is straightforward to determine $\Ind(Y^m_0)$, $\Ind(Y^m_1)$, and $\Ind(Y^m_2)$ by hand, and then we obtain the result by induction. \end{remark} \begin{lemma} \label{paralem} For $m \geq 2$ and $n \geq 1$, \[ \Ind(\widehat{Y}^m_n) \simeq \left\{ \begin{array}{ll} S^{mk} &\mbox{if } n=3k \\ S^{mk} &\mbox{if } n=3k+1 \\ S^{mk+1} \vee S^{m(k+1)-1} &\mbox{if } n=3k+2 \\ \end{array} \right. \, . \] \end{lemma} \begin{proof} In $\widehat{Y}^m_n$, label the two vertices of degree $m$ as $a$ and $b$ respectively. We consider a matching tree on $\Ind(\widehat{Y}^m_n)$. First, we apply Step 3 of the MTA with $v=b$. At the $\Sigma(\{b\}, N(b))$ and $\Sigma(\emptyset, \{b\})$ nodes, the remaining subgraphs of $\widehat{Y}^m_n$ from which we may select vertices are isomorphic to $Y^m_{n-1}$ and $Y^m_n$ respectively. For $n = 3k$ and $n=3k+1$, the result is immediate from applying Lemma~\ref{starlem} as one of the branches will produce contractible information. For the $n=3k+2$ case with $m \geq 3$, Lemma~\ref{starlem} only shows that two cells of the appropriate dimension exist, but they may not necessarily form a wedge. This is sufficient for the remainder of the article, but we prove that the two cells do, in fact, form a wedge for sake of completeness. Given the matching tree defined above for $\Ind(\widehat{Y}^m_n)$, let $\tau$ denote the cell of dimension $mk+1$, and let $\sigma$ denote the cell of dimension $m(k+1)-1$. In the style of \cite[Theorem~2.2]{KozlovHopf}, we argue that the feasibility domain of $\sigma$ (see \cite[Def~2.1]{KozlovHopf}) is such that $\tau$ and $\sigma$ must form a wedge. Suppose there exists a generalized alternating path from $\sigma$ to $\tau$ as per \cite[Def~2.1]{KozlovHopf}. Our choice of matching tree implies $b \in \tau$ while $b \notin \sigma$. Let $x_i$ be the last element in the alternating path with $b \notin x_i$, so $b \in x_{i+1}$. If $x_i$ is covered by $x_{i+1}$, then $x_i$ and $x_{i+1}$ are matched in the matching tree and so $b$ was designated as a free vertex during some application of Step~1 of the MTA. This is not possible as $b$ is included in $A \cup B$ in all tree nodes except for the root. If $x_i > x_{i+1}$, then $x_{i+1} \subseteq x_i$ as sets. This contradicts that $b \notin x_i$ and $b \in x_{i+1}$. Consequently, no such generalized alternating path can exist between $\sigma$ and $\tau$. The feasibility region of $\sigma$ does not contain $\tau$, and so $\sigma$ and $\tau$ form a wedge per \cite[Theorem~2.2]{KozlovHopf}. \end{proof} We now develop a matching tree for $\Ind(\Delta^m_n)$. \begin{algorithm}[Comb Algorithm, CA] Fix $m \geq 2$, $n \geq 1$ and use the labeling of the vertices of $\Delta_n^m$ from Section~\ref{sec:intro}. \begin{itemize} \item[Step 1:] Perform Step 3 of the MTA for $v = 1$, which produces two leaves $\Sigma(\{1\},N(1))$ and $\Sigma(\emptyset,\{1\})$ respectively. \item[Step 2:] For each $k \in \{2, \dots, n\}$, inductively perform Step 3 of the MTA for $v = k$ on the leaf $\Sigma(\emptyset,\{1, 2, \dots, k-1\})$, successively producing leaves $\Sigma(\{k\}, N(k) \cup \{1, 2, \dots, k-1\})$ and $\Sigma(\emptyset,\{1, 2, \dots, k\})$. \item[Step 3:] At the $\Sigma(\{1\},N(1))$ leaf, we may perform Step 1 of the MTA with $p = a$. \item[Step 4:] For each $k \in \{2, \dots, n-1\}$, consider the leaf \[ \Sigma(\{k\}, N(k) \cup \{1, 2, \dots, k-1\}) \, . \] Now, the remaining subgraph of $\Delta^m_n$ from which we may select vertices is isomorphic to the graph $Y^m_{k-1} \biguplus \Delta^m_{n-(k+1)}$. Since $\Ind(Y^m_{k-1})$ is known, we can determine the number and dimension of critical cells below this node by inductively applying this algorithm to $\Delta^m_{n-(k+1)}$. \item[Step 5:] At the $\Sigma(\{n\}, N(n) \cup \{1, 2, \dots, n-1\})$ leaf, we may perform Step 1 of the MTA with $p = b$. \item[Step 6:] At the $\Sigma(\emptyset,\{1, 2, \dots, n\})$ leaf, the remaining subgraph of $\Delta^m_n$ from which we may query vertices is isomorphic to $\widehat{Y}^m_{n+1}$. Since $\Ind(\widehat{Y}^m_{n+1})$ is known, we can determine the number and dimension of critical cells arising below this node. \end{itemize} \end{algorithm} We call this process for generating a matching tree for $\Ind(\Delta_n^m)$ the ``Comb Algorithm'' because of the visual shape of the resulting matching tree. Steps~1 and~2 produce the backbone of the ``comb,'' while Steps~3 through~6 produce the teeth. For example, applying Steps~1 and~2 of the comb algorithm to $\Ind(\Delta_4^m)$ leads to the (partial) matching tree in Figure \ref{fig:comb}. \begin{figure}[h] \label{fig:comb} \centering \begin{tikzpicture}[scale=1.75] \draw [thick] (-2,5)--(-1,4)--(0,3)--(1,2)--(2,1); \draw [thick] (-3,4)--(-2,5); \draw [thick] (-2,3)--(-1,4); \draw [thick] (-1,2)--(0,3); \draw [thick] (0,1)--(1,2); \node[rectangle, fill=white] at (-2,5) {\footnotesize $\Sigma(\emptyset,\emptyset)$}; \node[rectangle, fill=white] at (-1,4) {\footnotesize $\Sigma(\emptyset,\{1\})$}; \node[rectangle, fill=white] at (0,3) {\footnotesize $\Sigma(\emptyset,\{1,2\})$}; \node[rectangle, fill=white] at (1,2) {\footnotesize $\Sigma(\emptyset,\{1,2,3\})$}; \node[rectangle, fill=white] at (2,1) {\footnotesize $\Sigma(\emptyset,\{1,2,3,4\})$}; \node[rectangle, fill=white] at (-3,4) {\footnotesize $\Sigma(\{1\},N(1))$}; \node[rectangle, fill=white] at (-2,3) {\footnotesize $\Sigma(\{2\},N(2)\cup\{1\})$}; \node[rectangle, fill=white] at (-1,2) {\footnotesize $\Sigma(\{3\},N(3)\cup\{1,2\})$}; \node[rectangle, fill=white] at (0,1) {\footnotesize $\Sigma(\{4\},N(4)\cup\{1,2,3\})$}; \end{tikzpicture} \caption{Example of the Comb Algorithm} \end{figure} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Chain Spaces of $X_n^m$}\label{sec:results} \begin{definition} Denote by $X^m_n$ the cellular complex arising from the Comb Algorithm applied to $\Ind(\Delta^m_n)$ for $m \geq 2$ and $n \geq 1$. Since we cannot apply the Comb Algorithm to $\Ind(\Delta^m_0)$, we define $X^m_0 := S^0$ in agreement with the fact that $\Delta^m_0 \cong \widehat{Y}^m_1$. Now, for fixed $m \geq 2$ and arbitrary $d \geq 1$, let $C^d_n$ be the number of $d$-dimensional cells in $X^m_n$. \end{definition} Since the Comb Algorithm will always pair the empty set with a $0$-cell, we insist that $C^{-1}_n = 0$. Also, we set $C^0_n$ to be one less than the number of $0$-dimensional cells in $X^m_n$ to avoiding including the extra $0$-cell generated by the empty set pairing. Furthermore, the overall context implies that $C^d_n = 0$ if $d < 0$ or $n < 0$. \begin{prop} \label{cellseed} Suppose $0 \leq n \leq 3$. Then, $C^d_n = 0$ for all $d \geq 0$ except the following: \end{prop} %\begin{table}[h] \label{tab:cellseed} %\centering %\begin{tabular}{|c|cccccc|} \hline %& $C^0_0$ & $C^1_1$ & $C^{m-1}_1$ & $C^m_2$ & $C^2_3$ & $C^m_3$ \\ \hline %$m = 2$ & 1 & 2 & 2 & 1 & 2 & 2 \\ \hline %$m \geq 3$ & 1 & 1 & 1 & 1 & 1 & 1 \\ \hline %\end{tabular} %\caption{Initial conditions of the Comb Algorithm recursion} %\end{table} \begin{table}[ht] \label{tab:cellseed} \centering \begin{minipage}{2.5in} \centering When $m=2$ \\ \begin{tabular}{|c|cccc|} \hline & $n = 0$ & 1 & 2 & 3 \\ \hline $d = 0$ & 1 & - & - & - \\ \hline 1 & - & 2 & - & - \\ \hline 2 & - & - & 1 & 2 \\ \hline \end{tabular} \end{minipage} \begin{minipage}{2.5in} \centering When $m \geq 3$ \\ \begin{tabular}{|c|cccc|} \hline & $n = 0$ & 1 & 2 & 3 \\ \hline $d = 0$ & 1 & - & - & - \\ \hline 1 & - & 1 & - & - \\ \hline 2 & - & - & - & 1 \\ \hline $m-1$ & - & 1 & - & - \\ \hline $m$ & - & - & 1 & 1 \\ \hline \end{tabular} \end{minipage} \caption{Initial conditions of the Comb Algorithm recursion} \end{table} \begin{proof} Fix $m \geq 2$. We separately consider $\Ind(\Delta^m_n)$ for $n \in \{0,1,2,3\}$. \textbf{\underline{Case 1}:} Suppose $n=0$. Then $\Delta^m_0 \cong \widehat{Y}^m_1$, which implies $\Ind(\Delta^m_0) \simeq S^0$ by Lemma~\ref{paralem}. Consequently, $C^0_0 = 1$ while $C^d_0 = 0$ for all other $d$. \textbf{\underline{Case 2}:} Suppose $n=1$. We apply Step~1 followed by Step~3 of the CA to $\Ind(\Delta^m_1)$. At the $\Sigma(\emptyset,\{1\})$ node, the remaining graph from which we may select vertices is isomorphic to $\widehat{Y}^m_2$. Thus, $\Ind(\Delta^m_1) \simeq \Ind(\widehat{Y}^m_2)$, from which we can apply Lemma~\ref{paralem}. So, $C^1_1 = C^{m-1}_1 = 1$ if $m \geq 3$, and $C^1_1 = 2$ if $m = 2$. In either case, $C^d_1 = 0$ for all other $d$. \textbf{\underline{Case 3}:} Suppose $n=2$. First, apply the Comb Algorithm to $\Ind(\Delta^m_2)$. We note that Step~5 subsumes Step~4 in this particular instance. Now, Steps~3 and~5 imply that no critical cells are picked out below the nodes $\Sigma(\{1\}, N(1))$ and $\Sigma(\{2\}, N(2) \cup \{1\})$. Consequently, Step~6 implies that $\Ind(\Delta^m_2) \simeq \Ind(\widehat{Y}^m_3) \simeq S^m$ via Lemma~\ref{paralem}. Thus, $C^m_2 = 1$ while $C^d_2 = 0$ for all other $d$. \textbf{\underline{Case 4}:} Suppose $n=3$. First, apply the Comb Algorithm to $\Ind(\Delta^m_3)$. Now, Steps~3 and~5 imply that no critical cells are generated below $\Sigma(\{1\}, N(1))$ and $\Sigma(\{3\},N(3)\cup\{1,2\})$. Per Step~4 at the $\Sigma(\{2\}, N(2) \cup \{1\})$ leaf, the remaining subgraph of $\Delta^m_3$ from which we may select vertices is isomorphic to $Y^m_{1} \biguplus \Delta^m_{0}$. We already know that $\Ind(Y^m_{1})$ and $\Ind(\Delta^m_{0})$ are both homotopy equivalent to $S^0$, thus each has one critical $0$-cell with a single vertex. Consequently, $\Ind(Y^m_1 \biguplus \Delta^m_0)$ must have a single critical cell consisting of two vertices, so it is homotopy equivalent to $S^1$. Accounting for the vertex $2$ as well, we see that the Comb Algorithm generates a 2-cell below this node. At the node $\Sigma(\emptyset, \{1,2,3\})$ generated in Step~6, the remaining subgraph of $\Delta^m_3$ from which we may select vertices is isomorphic to $\widehat{Y}^m_4$. Since $\Ind(\widehat{Y}^m_4) \simeq S^m$, the Comb Algorithm generates an $m$-cell below this node. In total, we have $C^2_3 = C^m_3 = 1$ if $m \geq 3$, otherwise $C^2_3 = 2$. In either case, $C^d_3 = 0$ for all other $d$. \end{proof} \begin{theorem}\label{cellrec} Using Proposition~\ref{cellseed} as initial conditions, we have \begin{align} C^d_n = C^{d-2}_{n-3} + C^{d-(m+1)}_{n-4} + C^{d-m}_{n-3} \, , \label{eqn:rec} \end{align} when $n \geq 4$ for fixed $m \geq 2$. In this formula, a summand is zero if the subscript or superscript is negative. \end{theorem} \begin{proof} Assume $n \geq 4$ and $d \geq 0$. Applying the Comb Algorithm to $\Ind(\Delta^m_n)$ generates factors of the form $\Ind(Y^m_{k-1} \biguplus \Delta^m_{n-(k+1)})$ for $1 \leq k \leq n$, each of which are identically $\Ind(Y^m_{k-1}) \ast \Ind(\Delta^m_{n-(k+1)})$. We let $C^d_n(k)$ be the number of $d$-dimensional cells in $X^m_n$ produced by the Comb Algorithm below the node $\Sigma(\{k\}, N(k) \cup \{1, 2, \dots, k-1\})$, that is, the cells referenced in Step~4 of the Comb Algorithm. We use $C^d_n(\emptyset)$ to denote the number of $d$-dimensional cells arising from Step~6 of the Comb Algorithm. It is clear that $C^d_n = \sum^n_{k=1} C^d_n(k) + C^d_n(\emptyset)$. First, whenever $k-1 \equiv 0 \bmod 3$, $\Ind(Y^m_{k-1})$ is contractible and, consequently, so is $\Ind(Y^m_{k-1}) \ast \Ind(\Delta^m_{n-(k+1)})$. Thus, $C^d_n(k) = 0$ when $k-1 \equiv 0 \bmod 3$, and so we may assume that $k = 3 \ell$ or $k = 3 \ell + 2$ for some non-negative integer $\ell$. Also, note that $\Ind(Y^m_{k-1}) \ast \Ind(\Delta^m_{n-(k+1)})$ is contractible for $k = n$ since $\Ind(\Delta^m_{-1})$ is contractible, i.e. $C^d_n(n) = 0$. These observations agree respectively with Steps 3 and 5 of the Comb Algorithm. Next, we consider $C^d_n(2)$. Such a $d$-cell must correspond to the set of $d+1$ vertices consisting of the vertex $2$, a single vertex contributed from $\Ind(Y^m_1)$, and $d-1$ vertices contributed from $\Ind(\Delta^m_{n-3})$. Therefore, the $d$-cells coming from $\Ind(Y^m_1) \ast \Ind(\Delta^m_{n-3})$ are in bijective correspondence with the $(d-2)$-cells of $\Ind(\Delta^m_{n-3})$. Hence, $C^d_n(2)$ equals $C^{d-2}_{n-3}$. Note that if $d < 2$, then $C^d_n(2) = 0$. Similarly, we consider $C^d_n(3)$. The $d+1$ vertices corresponding to such a $d$-cell consist of the vertex $3$, $m$ vertices contributed from $\Ind(Y^m_2)$, and $d-m$ vertices contributed from $\Ind(\Delta^m_{n-4})$, provided $d-m > 0$. Therefore, the $d$-cells coming from $\Ind(Y^m_2) \ast \Ind(\Delta^m_{n-4})$ are in bijective correspondence with the $(d-(m+1))$-cells of $\Ind(\Delta^m_{n-4})$. Hence, $C^d_n(3) = C^{d-(m+1)}_{n-4}$. Note that if $d < m+1$, then $C^d_n(3) = 0$. Lastly, we simultaneously consider $C^d_n(k)$ for $k \in \{4, 5, \dots, n, \emptyset \}$. As before, we can disregard $k \equiv 1 \bmod 3$ and $k = n$. %The key observation here is that the set of $d$-cells picked out below the node $\Sigma(\emptyset,\{1, 2, 3\})$ is in bijective correspondence with the set of $(d-m)$-cells picked out by the Comb Algorithm when applied to $\Ind(\Delta^m_{n-3})$, i.e. $\displaystyle \sum^n_{k=4} C^d_n(k) + C^d_n(\emptyset) = C^{d-m}_{n-3}$. We handle the case $k \equiv 0 \bmod 3$, while the case $k \equiv 2 \bmod 3$ follows similarly. We first consider the case when $k = 3\ell$ for some positive integer $\ell$, which implies that $\Ind(Y^m_{k-1}) \simeq S^{m\ell - 1}$. A $d$-cell contributed from the factor $\Ind(Y^m_{k-1}) \ast \Ind(\Delta^m_{n-(k+1)})$ consists of (i) the vertex $k$, (ii) $m\ell$ vertices from $\Ind(Y^m_{k-1})$, and (iii) $d - m \ell$ vertices from $\Ind(\Delta^m_{n-(k+1)})$, provided that $d - m\ell > 0$. We observe that a similar factor of $\Ind(Y^m_{(k-1)-3} \biguplus \Delta^m_{n-(k+1)})$ is generated when the Comb Algorithm is applied to $\Ind(\Delta^m_{n-3})$. It is straightforward to show that the difference in dimension of the critical cell in $\Ind(Y^m_{k-1})$ from that of the critical cell in $\Ind(Y^m_{k-4})$ is $m$. This implies that the $d - m\ell$ vertices from $\Ind(\Delta^m_{n-(k+1)})$ that generate a given $d$-cell in the factor $\Ind(Y^m_{k-1}) \ast \Ind(\Delta^m_{n-(k+1)})$ for $\Ind(\Delta^m_n)$ also generate a cell of dimension $d-m$ in the factor $\Ind(Y^m_{k-4} \biguplus \Delta^m_{n-(k+1)})$ for $\Ind(\Delta^m_{n-3})$ and vice versa. Consequently, $C^d_n(k) = C^{d-m}_{n-3}(k-3)$, provided $d \geq m$. A similar argument holds for the case when $k \equiv 2 \bmod 3$. Next, we see that $C^d_n(\emptyset)$ = $C^{d-m}_{n-3}(\emptyset)$ if $d \geq m$. This observation follows because the difference in dimensions of the critical cells in $\Ind(\widehat{Y}^m_{n+1})$ from those of the critical cells in $\Ind(\widehat{Y}^m_{n-2})$ is $m$ while the number of critical cells is constant modulo 3. Hence, we must have $$\sum^n_{k=4}{C^d_n(k)} + C^d_n(\emptyset) = \sum^{n-3}_{k=1}{C^{d-m}_{n-3}(k)} + C^{d-m}_{n-3}(\emptyset) = C^{d-m}_{n-3},$$ which gives $$C^d_n = \sum^n_{k=1} C^d_n(k) + C^d_n(\emptyset) = C^{d-2}_{n-3} + C^{d-(m+1)}_{n-4} + C^{d-m}_{n-3}.$$ \end{proof} Now that we have a recursive formula that gives the number of critical cells generated by the Comb Algorithm, we can manipulate this formula to get a recursive formula for the reduced Euler characteristic of both $\Ind(\Delta^m_n)$ and $X^m_n$. We denote the reduced Euler characteristic by $\chi^m_n$. Note that since $C_n^0$ is one less than the number of $0$-dimensional cells in $X_n^m$, we have $\chi^m_n = \sum_{d \geq 0} (-1)^d C^d_n$. \begin{corollary} Given the initial conditions from Proposition~\ref{cellseed}, when $m \geq 2$ and $n \geq 4$, we have $$\chi^m_n = (1 + (-1)^m) \chi^m_{n-3} + (-1)^{m+1}\chi_{n-4}^m.$$ \end{corollary} \begin{proof} Fix $m$ and $n$ as above. Using formula \eqref{eqn:rec} for $C_n^d$, we obtain \begin{align*} \chi^m_n &= \sum_{d \geq 0} (-1)^d \left( C^{d-2}_{n-3} + C^{d-(m+1)}_{n-4} +C^{d-m}_{n-3} \right) \\ &= \left( \sum_{d \geq 0} (-1)^d C^{d-2}_{n-3} \right) + \left( \sum_{d \geq 0} (-1)^d C^{d-(m+1)}_{n-4} \right) + \left( \sum_{d \geq 0} (-1)^d C^{d-m}_{n-3} \right) \\ &= \left( \sum_{d \geq 0} (-1)^{d-2} C^{d-2}_{n-3} \right) + \left( (-1)^{m+1} \sum_{d \geq 0} (-1)^{d-(m+1)} C^{d-(m+1)}_{n-4} \right) \\ & \hspace{0.25in} + \left( (-1)^m \sum_{d \geq 0}(-1)^{d-m} C^{d-m}_{n-3} \right) \\ &= \left( \sum_{d \geq 0} (-1)^d C^d_{n-3} \right) + \left( (-1)^{m+1} \sum_{d \geq 0} (-1)^d C^d_{n-4} \right) + \left( (-1)^m \sum_{d \geq 0}(-1)^d C^d_{n-3} \right) \\ &= \chi^m_{n-3} + (-1)^{m+1} \chi^m_{n-4} + (-1)^m \chi^m_{n-3} \\ &= (1 + (-1)^m)\chi^m_{n-3} + (-1)^{m+1} \chi^m_{n-4} \end{align*} The fourth equality above is obtained by reindexing and noting that $C^{d-(m+1)}_{n-4}$ = 0 for $d < m$ and $C^{d-m}_{n-3} = 0$ for $d < m-1$. \end{proof} \begin{corollary} When $m$ is even, $\chi^m_n$ satisfies the recursion $a_n = a_{n-3} - a_{n-2} - a_{n-1}$ with initial conditions $a_0 = 1$, $a_1 = -2$, and $a_2 = 1$, and hence has generating function $\frac{1-x}{1+x+x^2-x^3}$. (This sequence is the A078046 entry in the OEIS \cite{OEIS}.) \end{corollary} \begin{proof} Assume that $m \geq 2$ is even. First, observe that $\chi^m_0$ = 1, $\chi^m_1 = -2$, and $\chi^m_2 = 1$ by Proposition~\ref{cellseed}, so both relations have the same initial conditions. We can easily verify that $\chi^m_3 = 2 = 1 - (-2) - 1 = a_0 - a_1 - a_2 = a_3$. Now, for fixed $n$, assume that $\chi^m_{\ell}$ satisfies both relations for $\ell < n$. Since $m$ is even, we have that $\chi^m_n = 2 \cdot \chi^m_{n-3} - \chi^m_{n-4} = \chi^m_{n-3} + (\chi^m_{n-3} - \chi^m_{n-4})$. By assumption, $\chi^m_{n-1} = \chi^m_{n-4} - \chi^m_{n-3} - \chi^m_{n-2}$, which implies that $\chi^m_{n-3} - \chi^m_{n-4} = - \chi^m_{n-2} - \chi^m_{n-1}.$ Therefore, we obtain by substitution that $\chi^m_n = \chi^m_{n-3} + (\chi^m_{n-3} - \chi^m_{n-4}) = \chi^m_{n-3} - \chi^m_{n-2} - \chi^m_{n-1}$. Consequently, $\chi^m_n$ satisfies both relations by induction. \end{proof} \begin{remark} When $m$ is odd, $\chi^m_n = \chi^m_{n-4}$. It is easy to verify that $\chi^m_0 = 1$, $\chi^m_1 = 0$, $\chi^m_2 = -1$, and $\chi^m_3 = 1$ from Proposition~\ref{cellseed}. Therefore, $\chi^m_n \in \{-1,0,1\}$ depending on the value of $n$ modulo $4$. \end{remark} For the special case $m=2$, the dimensions of $C_n^d$ have an interesting enumerative interpretation. In particular, the sequence A201780 in OEIS \cite{OEIS} is the Riordan array of \[ \left( \dfrac{(1-x)^2}{1-2x}, \dfrac{x}{1-2x} \right) \] which can be alternatively defined by \begin{equation} \label{riordan} T(j,k) = 2 \cdot T(j-1,k) + T(j-1,k-1) \end{equation} with initial conditions $T(0,0) = 1$, $T(1,0) = 0$, $T(2,0) = 1$, and $T(j,k) = 0$ if $k<0$ or $j d^{max}_n$, and $C^{d^{max}_n}_n$ is nonzero. \end{theorem} \begin{proof} By Proposition~\ref{cellseed}, the claim holds for the bases cases of $n \in \{0,1,2,3\}$. We proceed by strong induction. For $n \geq 4$, suppose the claim is true for all $0 \leq i < n$. For fixed $j$, we will be considering the maximum dimension of a cell produced below the node $\Sigma(\{j\}, N(j) \cup \{1, 2, \dots, j-1\})$ from the Comb Algorithm applied to $\Ind(\Delta^m_n)$. As before, we may assume $j \in \{2, \dots, n\}$. If $j = n$, the remaining subgraph of $\Delta^m_n$ from which we may query vertices is isomorphic to $\widehat{Y}^m_{n+1}$. If $j < n$, then the remaining subgraph is $Y^m_{j-1} \biguplus \Delta^m_{n-(j+1)}$, which corresponds to a subcomplex of $\Ind(\Delta^m_n)$ of the form $\Ind(Y^m_{j-1}) \ast \Ind(\Delta^m_{n-(j+1)})$. We will again use the notation $\delta_j$ from the proof of Theorem~\ref{mindim}. Again considering $j \in \{2, \dots, n-1\}$, we have $n-(j+1) < n$, and so the induction hypothesis holds for $\Ind(\Delta^m_{n-(j+1)})$. We now count the maximum number of vertices in a critical cell in the matching tree below the node $\Sigma(\{j\},N(j)\cup\{1, 2, \dots, j-1\})$. We have the vertex $j$ itself, $\delta_j + 1$ vertices from $\Ind(Y^m_{j-1})$, and $d^{max}_{n-(j+1)} + 1$ vertices from $X^m_{n-(j+1)}$. This total number of vertices corresponds to a cell of dimension $\delta_j~+~d^{max}_{n-(j+1)}~+~2$ below the node $\Sigma(\{j\}, N(j) \cup \{1,2,\dots,j-1\})$. As before, in the special case $j=n$, we expect the subcomplex corresponding to $\Ind(\widehat{Y}^m_{n+1})$ to contribute one or two cells of the appropriate dimension per Lemma \ref{paralem}. Next, we explicitly calculate $d_n^{max}$ for the two cases of $m$. \vspace{1em} \hspace{-0.275in} \textbf{\underline{Case 1}:} Suppose that $m = 2$. The proposed $d^{max}_n$ is $\left\lfloor \frac{3n+2}{4} \right\rfloor$. \textbf{Subcase 1a:} If $j = 3\ell$, then we have \vspace{-1em} \begin{align*} \delta_j + d^{max}_{n-(j+1)} + 2 &= (2\ell-1) + \left\lfloor \frac{3(n-(3\ell+1))+2}{4} \right\rfloor + 2 \\ &= \left\lfloor \frac{3n-\ell+3}{4} \right\rfloor \quad \leq \quad d^{max}_n \\ \end{align*} \vspace{-2em} since $\ell \geq 1$ as a consequence of $j \geq 2$. \textbf{Subcase 1b:} If $j=3\ell+2$, then we have \vspace{-1em} \begin{align*} \delta_j + d^{max}_{n-(j+1)} + 2 &= 2\ell + \left\lfloor \frac{3(n-(3\ell+3)+2}{4} \right\rfloor + 2 \\ &= \left\lfloor \frac{3n-\ell+1}{4} \right\rfloor \quad \leq \quad d^{max}_n. \\ \end{align*} \vspace{-2em} We now consider the contribution of the subcomplex corresponding to $\Ind(\widehat{Y}^m_{n+1})$. When $n=3k$, $d^{max}_{n} = \left\lfloor \frac{9k+2}{4} \right\rfloor \geq 2k$ while the $\widehat{Y}^m_{n+1}$ contribution has dimension $2k$. When $n=3k+1$, $d^{max}_{n} = \left\lfloor \frac{9k+5}{4} \right\rfloor \geq 2k+1$ while the $\widehat{Y}^m_{n+1}$ contributions have dimension $2k+1$. When $n=3k+2$, $d^{max}_{n} = \left\lfloor \frac{9k+8}{4} \right\rfloor \geq 2k+2$ while the $\widehat{Y}^m_{n+1}$ contribution has dimension $2k+2$. So, all things considered, no cells of $X^m_n$ exceed the proposed maximum dimension. Furthermore, when $j=3$, the $\Ind(Y^m_2) \ast \Ind(\Delta^m_{n-4})$ factor produces at least one cell of dimension exactly $d^{max}_n$, which implies that $C^{d^{max}_n}_n$ is non-zero. \vspace{1em} \hspace{-0.275in} \textbf{\underline{Case 2}:} Suppose that $m \geq 3$. The proposed $d^{max}_n$ is $n + 1 + (m-3)\left\lfloor \frac{n+2}{3} \right\rfloor$. \textbf{Subcase 2a:} If $j = 3\ell$, then we have $\delta_j + d^{max}_{n-(j+1)} + 2$ is equal to the following \vspace{-1em} \begin{align*} &(m\ell-1) + \left( n-(3\ell+1) + 1 + (m-3) \left\lfloor \frac{n-(3\ell+1)+2}{3} \right\rfloor \right) + 2 \\ &= n + 1 + (m-3) \left( \left\lfloor \frac{n-3\ell+1}{3} \right\rfloor + \ell \right) \\ &= n + 1 + (m-3) \left\lfloor \frac{n+1}{3} \right\rfloor \quad \leq \quad d^{max}_n. \\ .\end{align*} \vspace{-2em} \textbf{Subcase 2b:} If $j=3\ell+2$, then we have $\delta_j + d^{max}_{n-(j+1)} + 2$ is equal to the following \vspace{-1em} \begin{align*} & (m\ell) + \left( n-(3\ell+3) + 1 + (m-3) \left\lfloor \frac{n-(3\ell+3)+2}{3} \right\rfloor \right) + 2 \\ &= n + (m-3) \left( \left\lfloor \frac{n-3\ell-1}{3} \right\rfloor + \ell \right) \\ &= n + (m-3) \left\lfloor \frac{n-1}{3} \right\rfloor \quad \leq \quad d^{max}_n. \\ \end{align*} \vspace{-2em} We now consider the contribution of the subcomplex corresponding to $\Ind(\widehat{Y}^m_{n+1})$. When $n=3k$, $d^{max}_{n} = 3k + 1 + (m-3)\left\lfloor \frac{3k+2}{3} \right\rfloor = mk+1$ while the $\widehat{Y}^m_{n+1}$ contribution has dimension $mk$. When $n=3k+1$, $d^{max}_{n} = (3k+1) + 1 + (m-3)\left\lfloor \frac{(3k+1)+2}{3} \right\rfloor= m(k+1)-1$ while the $\widehat{Y}^m_{n+1}$ contributions have dimension $mk+1$ and $m(k+1)-1$ respectively. When $n=3k+2$, $d^{max}_{n} = (3k+2) + 1 + (m-3)\left\lfloor \frac{(3k+2)+2}{3} \right\rfloor = mk+m$ while the $\widehat{Y}^m_{n+1}$ contribution has dimension $mk+m$. So, all things considered, no cells of $X^m_n$ exceed the proposed maximum dimension. Moreover, when $n=3k+1$ or $n=3k+2$, the contributions from the $\widehat{Y}^m_{n+1}$ factor imply that $C^{d^{max}_n}_n$ is non-zero. When $n=3k$ and $j=3$, we have that the factor $\Ind(Y^m_2) \ast \Ind(\Delta^m_{n-4})$ produces at least one cell of dimension exactly $d^{max}_n$, which again implies that $C^{d^{max}_n}_n$ is non-zero. \end{proof} Using Theorems \ref{cellseed} and \ref{cellrec}, we can create data tables containing dimensions of the integral cellular chain spaces of $X^m_n$ for reasonable values of $n$ and $m$. For $m \geq 4$, it is interesting that gaps appear in the dimensions of the chain spaces for low values of $d$ relative to $n$. For example, the Comb Algorithm eliminates all cells of dimension $\left\lfloor \frac{2n+2}{3} \right\rfloor + 1$ through $\left\lfloor \frac{2n+2}{3} \right\rfloor + (m-3)$ when $n=3k$ or $n=3k+1$. Furthermore, we can explicitly determine the lowest non-vanishing homology for $n=3k$ and $n=3k+1$ when $m \geq 4$; see Jonsson \cite[Lemma~2.3 and Proposition~2.7]{JonssonMatchingGrids} for analogous results when $m=2$. \begin{theorem} Suppose that $m \geq 4$, and let $\nu_n = \left\lfloor \frac{2n+2}{3} \right\rfloor$. If $n = 3k$ or $n=3k+1$, then $\nu_n = d^{min}_n$ from Theorem \ref{mindim}, and $C^{\nu_n}_n = 1$ while $C^{\nu_n+1}_n = 0$. This implies that $H_{\nu_n}(X^m_n; \mathbb{Z}) \cong \mathbb{Z}$. If $n = 3k+2$, then $C^{\nu_n}_n = 0$, which implies that $H_{\nu_n}(X^m_n; \mathbb{Z})$ is trivial. \end{theorem} \begin{proof} We consider three cases, one for each value of $n \bmod 3$. \textbf{\underline{Case 1}:} Suppose $n = 3k$. We know that $C^{\ell}_n = 0$ for $\ell < \nu_n$ from our cellular dimension range. We argue by induction on $k$ that $C^{\nu_n}_n = 1$ while $C^{\nu_n+1}_n = 0$, which proves the claim for $n=3k$. Begin by recalling that $C^0_0 = 1$ and $C^1_0 = 0$, which provides a base case. Now, assume that $C^{\nu_{3\ell}}_{3\ell} = 1$ while $C^{\nu_{3\ell}+1}_{3\ell} = 0$ for $0 \leq \ell < k$. We know that $$C^{\nu_n}_n = C^{\nu_{3k}-2}_{3k-3} + C^{\nu_{3k}-m-1}_{3k-4} + C^{\nu_{3k}-m}_{3k-3}$$ by our cellular recursion. Observe that $\nu_{3k}-2 = 2k-2 = \nu_{3k-3}$, so $C^{\nu_{3k}-2}_{3k-3} = 1$ by the induction hypothesis. Since $\nu_{3k}-m-1 < \nu_{3k}-2 = \nu_{3k-4}$, it follows that $C^{\nu_{3k}-m-1}_{3k-4} = 0$. Similarly, $\nu_{3k}-m < \nu_{3k}-2 = \nu_{3k-3}$, so $C^{\nu_{3k}-m}_{3k-3} = 0$. Hence, $C^{\nu_n}_n = 1$. Our cellular recursion also gives $$C^{\nu_n+1}_n = C^{\nu_{3k}-1}_{3k-3} + C^{\nu_{3k}-m}_{3k-4} + C^{\nu_{3k}-m+1}_{3k-3}.$$ Observe that $\nu_{3k}-1 = 2k-1 = \nu_{3k-3} + 1$, so $C^{\nu_{3k}-1}_{3k-3} = 0$ by the induction hypothesis. Now, we note that $\nu_{3k}-m < \nu_{3k}-2 = \nu_{3k-4}$ still, which implies $C^{\nu_{3k}-m}_{3k-4} = 0$. Similarly, $\nu_{3k}-m + 1 < \nu_{3k}-2 = \nu_{3k-3}$, so $C^{\nu_{3k}-m+1}_{3k-3} = 0$. Hence, $C^{\nu_n+1}_n = 0$. By induction, we conclude that $C^{\nu_{3k}}_{3k} = 1$ while $C^{\nu_{3k}+1}_{3k} = 0$ for all $k$, from which the result follows. \textbf{\underline{Case 2}:} Suppose $n = 3k+1$; this argument is similar to that of the previous case. We argue by induction on $k$ that $C^{\nu_n}_n = 1$ while $C^{\nu_n+1}_n = 0$. We obtain our base case by recalling that $C^1_1 = 1$ and $C^2_1 = 0$ for $m \geq 4$. Next, we know that $$C^{\nu_n}_n = C^{\nu_{3k+1}-2}_{3k-2} + C^{\nu_{3k+1}-m-1}_{3k-3} + C^{\nu_{3k}-m}_{3k-3}$$ by our cellular recursion. Observe that $\nu_{3k+1}-2 = 2k-1 = \nu_{3k-2} = \nu_{3(k-1)+1}$, so $C^{\nu_{3k+1}-2}_{3k-2} = 1$ by the induction hypothesis. Now, $\nu_{3k+1}-m-1 = 2k-m < 2k-2$, which is precisely $\nu_{3k-3}$, implying that $C^{\nu_{3k+1}-m-1}_{3k-3} = 0$. Similarly, we see that $\nu_{3k+1}-m$ equal $2k-m + 1 < 2k-1 = \nu_{3k-2}$, so $C^{\nu_{3k+1}-m}_{3k-2} = 0$. Hence, $C^{\nu_n}_n = 1$. We also know that $$C^{\nu_n+1}_n = C^{\nu_{3k+1}-1}_{3k-2} + C^{\nu_{3k+1}-m}_{3k-3} + C^{\nu_{3k+1}-m+1}_{3k-2}$$ by our cellular recursion. Observe that $\nu_{3k+1}-1 = \nu_{3k+1} - 2 + 1 = \nu_{3k-2} + 1$, so $C^{\nu_{3k+1}-1}_{3k-2} = 0$ by the induction hypothesis. Now, $\nu_{3k+1}-m = 2k - m + 1 < 2k-2$, which is again $\nu_{3k-3}$. Therefore, $C^{\nu_{3k+1}-m}_{3k-3} = 0$. Similarly, $\nu_{3k+1}-m + 1 < 2k - 1 = \nu_{3k-2}$, so $C^{\nu_{3k+1}-m+1}_{3k-2} = 0$. Hence, $C^{\nu_n+1}_n = 0$. By induction, we conclude that $C^{\nu_{3k+1}}_{3k+1} = 1$ while $C^{\nu_{3k+1}+1}_{3k+1} = 0$ for all $k$, from which the result follows. \textbf{\underline{Case 3}:} Suppose $n = 3k+2$. Recall from Theorem~\ref{mindim} that for $n=3k+2$ and $m \geq 3$, the minimum dimension of critical cells produced by the Comb Algorithm is $2\left\lfloor \frac{n-1}{3} \right\rfloor + m$. It is easy to check that $\left\lfloor \frac{2n+2}{3} \right\rfloor = 2k+2 < 2k+m = 2\left\lfloor \frac{n-1}{3} \right\rfloor + m$. Therefore, $C^{\nu_n}_n = 0$ when $n=3k+2$, i.e. $H_{\nu_n}(X^m_n; \mathbb{Z})$ is trivial. \end{proof} For other homology groups, the Comb Algorithm provides less comprehensive results. For example, when $m=2$, that is, when $X^m_n$ is homotopy equivalent to the matching complex on the $2 \times (n+2)$ grid graph, a direct analysis of the chain space dimensions on a data table yields the following. \begin{observation} $X^2_n$ has non-trivial free integral homology in dimension $\left\lfloor \frac{9n+9}{13} \right\rfloor$ for $0 \leq n \leq 99$, except possibly for $n \in \{48,61,74,84,87,90,94,97\}$. This arises because the rank of the chain space of $X^2_n$ in dimension $\left\lfloor \frac{9n+9}{13} \right\rfloor$ exceeds the sum of the ranks of the chain spaces in dimensions $\left\lfloor \frac{9n+9}{13} \right\rfloor - 1$ and $\left\lfloor \frac{9n+9}{13} \right\rfloor + 1$ for these values of $n$. Consequently, even if we were to try to further match away the critical cells in dimension $\left\lfloor \frac{9n+9}{13} \right\rfloor$, there are not enough cells in the adjacent dimensions to completely pair them all away. As an interesting side note, when $m=2$, the values of $d^{min}_n$ and $d^{max}_n$ imply that $X^2_n$ is a wedge of spheres for $n \in \{0,1,2,3,4,5,7,8,11\}$. \end{observation} As $n$ grows larger, the data suggest that the rank of the $\left\lfloor \frac{9n+9}{13} \right\rfloor$-dimensional chain space ceases to ``typically'' exceed the sum of the ranks of the neighboring chain spaces. This suggests that the behavior of $\Ind(\Delta_n^m)$ for ``small'' values of $n$, including many values of $n$ for which by-hand computations appear prohibitive, is not indicative of the general behavior of these complexes. In conclusion, the topology of $\Ind(\Delta_n^m)$ remains generally mysterious. It would be of interest to investigate the following two questions. \begin{enumerate} \item Does torsion occur in the homology of $\Ind(\Delta_n^m)$? If so, for which $p$ does $\mathbb{Z}/p\mathbb{Z}$ appear as a summand? \item There is a natural action of the symmetric group $\mathfrak{S}_m$ on $\Ind(\Delta_n^m)$. What is the $\mathfrak{S}_m$-module structure of $H_\ast(\Ind(\Delta_n^m);\mathbb{C})$? \end{enumerate} %\begin{claim} %$T(j,k) = C_{2(j-2)+k}^{3(j-2)+k}$ %\end{claim} % %\begin{proof} %Define functions \qquad $D(x,y) = 2(x-2)+y$ \qquad and \qquad $N(x,y) = 3(x-2)+y$. %Observe that $$D(j,k) = 2(j-2)+k, \qquad D(j-1,k) = 2(j-3)+k, \quad \mbox{and} \quad D(j-1,k-1) = 2(j-3)+k-1.$$ %Similarly, $$N(j,k) = 3(j-2)+k, \qquad N(j-1,k) = 3(j-3)+k, \quad \mbox{and} \quad N(j-1,k-1) = 3(j-3)+k-1.$$ %Applying \fbox{our} recursion to the entry $C_{D(j,k)}^{N(j,k)} = C_{2(j-2)+k}^{3(j-2)+k}$ gives %$$C_{2(j-2)+k}^{3(j-2)+k} = 2 \cdot C_{2(j-2)+k-2}^{3(j-2)+k-3} + C_{2(j-2)+k-3}^{3(j-2)+k-4} = 2 \cdot C_{2(j-3)+k}^{3(j-3)+k} + C_{2(j-3)+k-1}^{3(j-3)+k-1} = 2 \cdot C_{D(j-1,k)}^{N(j-1,k)} + C_{D(j-1,k-1)}^{N(j-1,k-1)}$$ %\bigskip %Thus, the recursion applied to $C_{2(j-2)+k}^{3(j-2)+k}$ matches that of $T(j,k)$. See the previous proof to verify that the initial conditions of the $C_d^n$ correspond appropriately to entries in the Riordan array. %\end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection*{Acknowledgements} Thanks to the anonymous referee for their thoughtful suggestions. \bibliographystyle{plain} \begin{thebibliography}{10} \bibitem{OEIS} The On-Line Encyclopedia of Integer Sequences, published electronically at https://oeis.org. \bibitem{AdamaszekSplittings} Micha{\l} Adamaszek. \newblock Splittings of independence complexes and the powers of cycles. \newblock {\em J. Combin. Theory}, 119(5):1031--1047, 2012. \bibitem{AdamaszekSpecial} Micha{\l} Adamaszek. \newblock Special cycles in independence complexes and superfrustration in some lattices. \newblock {\em Topology Appl.}, 160(7):943--950, 2013. \bibitem{BarmakStar} Jonathan~Ariel Barmak. \newblock Star clusters in independence complexes of graphs. \newblock {\em Adv. Math.}, 241:33--57, 2013. \bibitem{Bouc} S.~Bouc. \newblock Homologie de certains ensembles de {$2$}-sous-groupes des groupes sym\'etriques. \newblock {\em J. Algebra}, 150(1):158--186, 1992. \bibitem{LinussonGridGraphs} Mireille Bousquet-M{\'e}lou, Svante Linusson, and Eran Nevo. \newblock On the independence complex of square grids. \newblock {\em J. Algebraic Combin.}, 27(4):423--450, 2008. \bibitem{BraunIndComplexKneser} Benjamin Braun. \newblock Independence complexes of stable {K}neser graphs. \newblock {\em Electron. J. Combin.}, 18(1):P118, (electronic), 2011. \bibitem{Brown1992} Kenneth~S. Brown. \newblock {\em The Geometry of Rewriting Systems: A Proof of the Anick-Groves-Squier Theorem}, pages 137--163. \newblock Springer New York, New York, NY, 1992. \bibitem{Chari2000} Manoj~K. Chari. \newblock On discrete morse functions and combinatorial decompositions. \newblock {\em Discrete Mathematics}, 217(1):101 -- 113, 2000. \bibitem{WachsDongLaplacian} Xun Dong and Michelle~L. Wachs. \newblock Combinatorial {L}aplacian of the matching complex. \newblock {\em Electron. J. Combin.}, 9(1):Research Paper 17, 11 pp. (electronic), 2002. \bibitem{EarlEtAl} Jonathan Earl, Kevin~N. Vander~Meulen, and Adam Van~Tuyl. \newblock Independence {C}omplexes of {W}ell-{C}overed {C}irculant {G}raphs. \newblock {\em Exp. Math.}, 25(4):441--451, 2016. \bibitem{EhrenborgHetyei} Richard Ehrenborg and G{\'a}bor Hetyei. \newblock The topology of the independence complex. \newblock {\em European J. Combin.}, 27(6):906--923, 2006. \bibitem{EngstromIndependence} Alexander Engstr{\"o}m. \newblock Complexes of directed trees and independence complexes. \newblock {\em Discrete Math.}, 309(10):3299--3309, 2009. \bibitem{FormanMorseTheory} Robin Forman. \newblock Morse theory for cell complexes. \newblock {\em Adv. Math.}, 134(1):90--145, 1998. \bibitem{JonssonMatchingGrids} Jakob Jonsson. \newblock Matching complexes on grids. \newblock unpublished manuscript available at http://www.math.kth.se/$\sim$jakobj/doc/thesis/grid.pdf. \bibitem{JonssonBook} Jakob Jonsson. \newblock {\em Simplicial complexes of graphs}, volume 1928 of {\em Lecture Notes in Mathematics}. \newblock Springer-Verlag, Berlin, 2008. \bibitem{JonssonMoreTorsion} Jakob Jonsson. \newblock More torsion in the homology of the matching complex. \newblock {\em Experiment. Math.}, 19(3):363--383, 2010. \bibitem{KozlovBook} Dmitry Kozlov. \newblock {\em Combinatorial algebraic topology}, volume~21 of {\em Algorithms and Computation in Mathematics}. \newblock Springer, Berlin, 2008. \bibitem{KozlovIndCycles} Dmitry~N. Kozlov. \newblock Complexes of directed trees. \newblock {\em J. Combin. Theory Ser. A}, 88(1):112--122, 1999. \bibitem{KozlovHopf} Dmitry~N. Kozlov. \newblock Discrete {M}orse theory and {H}opf bundles. \newblock {\em Pacific J. Math.}, 249(2):371--376, 2011. \bibitem{ShareshianWachsTopHomology} John Shareshian and Michelle~L. Wachs. \newblock Top homology of hypergraph matching complexes, {$p$}-cycle complexes and {Q}uillen complexes of symmetric groups. \newblock {\em J. Algebra}, 322(7):2253--2271, 2009. \bibitem{VrecicaZivaljevicCycleFree} Sini{\v{s}}a~T. Vre{\'c}ica and Rade~T. {\v{Z}}ivaljevi{\'c}. \newblock Cycle-free chessboard complexes and symmetric homology of algebras. \newblock {\em European J. Combin.}, 30(2):542--554, 2009. \bibitem{WachsTopologyMatching} Michelle~L. Wachs. \newblock Topology of matching, chessboard, and general bounded degree graph complexes. \newblock {\em Algebra Universalis}, 49(4):345--385, 2003. \newblock Dedicated to the memory of Gian-Carlo Rota. \end{thebibliography} \end{document}