% -------------------------------------------------------------
% NOTE ON THE DETAILED AND SHORT VERSIONS:
% -------------------------------------------------------------
% This paper comes in two versions, a detailed and a short one.
% The short version should be more than sufficient for any
% reasonable use; the detailed one was written purely to
% convince the author of its correctness.
% To switch between the two versions, find the line containing
% "\newenvironment{noncompile}{}{}" in this LaTeX file.
% Look at the two lines right beneath this line.
% To compile the detailed version, they should be as follows:
%   \includecomment{verlong}
%   \excludecomment{vershort}
% To compile the short version, they should be as follows:
%   \excludecomment{verlong}
%   \includecomment{vershort}
% As a rule, the line
%   \excludecomment{noncompile}
% should stay as it is.
% -------------------------------------------------------------
% NOTES ON SOME HACKS USED IN THIS FILE:
% -------------------------------------------------------------
% One of my pet peeves with amsthm is its use of italics in the theorem and
% proposition environments; this makes math and text indistinguishable in said
% enviroments. To avoid this, I redefine the enviroments to use the standard
% font and to use a hanging indent, along with a bold vertical bar to its
% left, to distinguish these environments from surrounding text. (Along with
% the advantage of distinguishing math from text, this also allows nesting
% several such environments inside each other, like a definition inside a
% remark. I'm not sure how good of an idea this is, though. There are also
% downsides related to the hanging indentation, such as footnotes out of it
% being painful to do right.) This is done starting from the line
%   \theoremstyle{definition}
% and until the line
%   {\end{leftbar}\end{exmp}}

\documentclass[numbers=enddot,12pt,final,onecolumn,notitlepage]{scrartcl}%
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[all,cmtip]{xy}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{comment}
\usepackage{color}
\usepackage[breaklinks=True]{hyperref}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{tikz}
\usepackage{needspace}
\usepackage{tabls}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Friday, August 08, 2025 01:53:11}
%TCIDATA{SuppressPackageManagement}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%TCIDATA{Language=American English}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\usetikzlibrary{arrows}
\newcounter{exer}
\theoremstyle{definition}
\newtheorem{theo}{Theorem}[section]
\newenvironment{theorem}[1][]
{\begin{theo}[#1]\begin{leftbar}}
{\end{leftbar}\end{theo}}
\newtheorem{lem}[theo]{Lemma}
\newenvironment{lemma}[1][]
{\begin{lem}[#1]\begin{leftbar}}
{\end{leftbar}\end{lem}}
\newtheorem{prop}[theo]{Proposition}
\newenvironment{proposition}[1][]
{\begin{prop}[#1]\begin{leftbar}}
{\end{leftbar}\end{prop}}
\newtheorem{defi}[theo]{Definition}
\newenvironment{definition}[1][]
{\begin{defi}[#1]\begin{leftbar}}
{\end{leftbar}\end{defi}}
\newtheorem{remk}[theo]{Remark}
\newenvironment{remark}[1][]
{\begin{remk}[#1]\begin{leftbar}}
{\end{leftbar}\end{remk}}
\newtheorem{coro}[theo]{Corollary}
\newenvironment{corollary}[1][]
{\begin{coro}[#1]\begin{leftbar}}
{\end{leftbar}\end{coro}}
\newtheorem{conv}[theo]{Convention}
\newenvironment{convention}[1][]
{\begin{conv}[#1]\begin{leftbar}}
{\end{leftbar}\end{conv}}
\newtheorem{quest}[theo]{Question}
\newenvironment{question}[1][]
{\begin{quest}[#1]\begin{leftbar}}
{\end{leftbar}\end{quest}}
\newtheorem{warn}[theo]{Warning}
\newenvironment{conclusion}[1][]
{\begin{warn}[#1]\begin{leftbar}}
{\end{leftbar}\end{warn}}
\newtheorem{conj}[theo]{Conjecture}
\newenvironment{conjecture}[1][]
{\begin{conj}[#1]\begin{leftbar}}
{\end{leftbar}\end{conj}}
\newtheorem{exam}[theo]{Example}
\newenvironment{example}[1][]
{\begin{exam}[#1]\begin{leftbar}}
{\end{leftbar}\end{exam}}
\newtheorem{exmp}[exer]{Exercise}
\newenvironment{exercise}[1][]
{\begin{exmp}[#1]\begin{leftbar}}
{\end{leftbar}\end{exmp}}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\newenvironment{fineprint}{\begin{small}}{\end{small}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\newenvironment{convention}[1][Convention]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\newenvironment{question}[1][Question]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\let\cupnonlimits\bigcup
\let\capnonlimits\bigcap
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\renewcommand{\bigcup}{\cupnonlimits\limits}
\renewcommand{\bigcap}{\capnonlimits\limits}
\setlength\tablinesep{3pt}
\setlength\arraylinesep{3pt}
\setlength\extrarulesep{3pt}
\setlength\textheight{22.5cm}
\setlength\textwidth{14.8cm}
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\newcommand{\defn}[1]{{\color{darkred}\emph{#1}}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\KK}{\mathbb{K}}
\newcommand{\PPos}{\RR_{>0}}
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\tup}[1]{\left( #1 \right)}
\newcommand{\ive}[1]{\left[ #1 \right]}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\newcommand{\calF}{\mathcal{F}}
\newcommand{\calB}{\mathcal{B}}
\newcommand{\IN}{\ive{N}}
\newcommand{\Eh}{\widehat{E}}
\newcommand{\wh}{\widehat{w}}
\renewcommand{\dh}{\widehat{d}}
\newcommand{\Ch}{\widehat{C}}
\newcommand{\timesu}{\mathbin{\underline{\times}}}
\newcommand{\verts}[1]{\operatorname{V}\left( #1 \right)}
\newcommand{\edges}[1]{\operatorname{E}\left( #1 \right)}
\renewcommand{\leq}{\leqslant}
\renewcommand{\geq}{\geqslant}
\iffalse
\NOEXPAND{\timesu}{\mathbin{\underline{\times}}}
\fi
\newtheoremstyle{plainsl}
{8pt plus 2pt minus 4pt}
{8pt plus 2pt minus 4pt}
{\slshape}
{0pt}
{\bfseries}
{.}
{5pt plus 1pt minus 1pt}
{}
\theoremstyle{plainsl}
\ihead{}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\title{Some simplicial complexes in combinatorics\\{\large [Corrected slides of a talk at UConn Algebra Seminar, 2021-03-11]}}
\author{Darij Grinberg}
\maketitle

\begin{abstract}
\textbf{Abstract.} A number of combinatorial identities are concerned with
certain classes of subsets of a finite set (e.g., matchings of a graph); they
can be viewed as saying (roughly speaking) that equal numbers of these subsets
have even size and odd size. In this talk, I will discuss a few such
identities -- some of them new -- and their topological meaning. As a common
theme, the "parity bias" (or lack thereof) is the Euler characteristic of a
simplicial complex, and thus any expression for it is potentially the tip of a
topological iceberg. Underneath are questions of homology, homotopy or even
discrete Morse theory. Aside from the specific complexes in question, I hope
to provide one more pair of "simplex glasses" through which combinatorial
identities appear in a new light.

Preprint:

\url{https://arxiv.org/abs/2009.11527}

\end{abstract}

\section{Introduction}

\subsection{Alternating sums}

\begin{itemize}
\item Enumerative combinatorics is full of \textit{alternating sums}. Some
examples:%
\begin{align*}
\sum_{k=0}^{n}\left(  -1\right)  ^{k}\dbinom{n}{k}  &  =0\qquad\text{for
integers }n>0;\\
\sum_{k=0}^{m}\left(  -1\right)  ^{k}\dbinom{n}{k}  &  =\left(  -1\right)
^{m}\dbinom{n-1}{m}\qquad\text{for }m\geq0;\\
\sum_{k=0}^{\left\lfloor n/2\right\rfloor }\left(  -1\right)  ^{k}\dbinom
{n-k}{k}  &  =\left(  1\text{ or }0\text{ or }-1\right)  ;\\
\sum_{k=0}^{n}\left(  -1\right)  ^{k}\dbinom{n}{k}\dbinom{ak+b}{c}  &
=0\qquad\text{for }c,n\in\mathbb{N}\text{ with }c<n\text{;}\\
\sum_{i=0}^{m}\left(  -1\right)  ^{i}\operatorname*{sur}\left(  m,i\right)
&  =\left(  -1\right)  ^{m},
\end{align*}
where $\operatorname*{sur}\left(  m,i\right)  =\left(  \text{\# of surjections
from }\left\{  1,2,\ldots,m\right\}  \text{ to }\left\{  1,2,\ldots,i\right\}
\right)  $.

\item These alternating sums are among the most helpful tools in proving
identities. (They often play a similar role as the formula $1+\zeta+\zeta
^{2}+\cdots+\zeta^{n-1}=0$ for $\zeta$ being a nontrivial $n$-th root of unity
plays in the discrete Fourier transform.)

\item An alternating sum identity generally looks like this:%
\[
\sum_{\left(  \text{some finite set}\right)  }\left(  -1\right)  ^{\left(
\text{something}\right)  }\left(  \text{something}\right)  =\left(
\text{something typically simpler}\right)  .
\]


\item In this talk, I shall

\begin{itemize}
\item present some alternating sum identities and their combinatorial proofs
by \textquotedblleft\textbf{toggling}\textquotedblright\ or \textquotedblleft
sign-reversing involutions\textquotedblright;

\item discuss how a few of these identities can be lifted to
\textbf{topological} statements about simplicial complexes,

\item and how these topological statements can be lifted to
\textbf{combinatorial} statements again using discrete Morse theory.
\end{itemize}

\item This is not a theory talk; you'll hear my personal favorites, not the
most general or most important results.

\item There will be various open questions.
\end{itemize}

\section{Toggling}

\subsection{All subsets}

\begin{itemize}
\item We start with the first identity listed above:

\textbf{Theorem.} Let $n$ be a positive integer. Then,%
\[
\sum_{k=0}^{n}\left(  -1\right)  ^{k}\dbinom{n}{k}=0.
\]


\item There are many ways to prove this:

e.g., expand $\left(  1-1\right)  ^{n}$ using the binomial theorem.

\item Here is a \textbf{combinatorial proof}:

Set $\left[  n\right]  =\left\{  1,2,\ldots,n\right\}  $. Then,%
\[
\sum_{k=0}^{n}\left(  -1\right)  ^{k}\dbinom{n}{k}=\sum_{I\subseteq\left[
n\right]  }\left(  -1\right)  ^{\left\vert I\right\vert }.
\]


\textbf{Claim:} In the sum on the RHS, all the addends cancel out.

\textbf{Proof.} For each subset $I$ of $\left[  n\right]  $, we can

\begin{enumerate}
\item insert $1$ into $I$ if $1\notin I$, or

\item remove $1$ from $I$ if $1\in I$.
\end{enumerate}

This gives us a new subset of $\left[  n\right]  $, which we denote by
$I\bigtriangleup\left\{  1\right\}  $.

Easy to see: The map%
\begin{align*}
\left\{  \text{subsets of }\left[  n\right]  \right\}   &  \rightarrow\left\{
\text{subsets of }\left[  n\right]  \right\}  ,\\
I  &  \mapsto I\bigtriangleup\left\{  1\right\}
\end{align*}
is an involution (i.e., applying it twice gives the identity), and it flips
the sign (meaning $\left(  -1\right)  ^{\left\vert I\bigtriangleup\left\{
1\right\}  \right\vert }=-\left(  -1\right)  ^{\left\vert I\right\vert }$ for
any subset $I$ of $\left[  n\right]  $).

Hence, all addends in the sum $\sum_{I\subseteq\left[  n\right]  }\left(
-1\right)  ^{\left\vert I\right\vert }$ cancel out (the $I$-addend cancelling
the $I\bigtriangleup\left\{  1\right\}  $-addend). Thus, the sum is $0$, qed.

\item Our notation $I\bigtriangleup\left\{  1\right\}  $ is a particular case
of the notation%
\begin{align*}
I\bigtriangleup J  &  =\left(  I\cup J\right)  \setminus\left(  I\cap J\right)
\\
&  =\left(  I\setminus J\right)  \cup\left(  J\setminus I\right) \\
&  =\left\{  \text{all elements that belong to \textbf{exactly one} of
}I\text{ and }J\right\}
\end{align*}
for any two sets $I$ and $J$.

\item If $a$ is any element, then the operation of replacing a set $I$ by
$I\bigtriangleup\left\{  a\right\}  $ (that is, inserting $a$ into $I$ if
$a\notin I$, and removing $a$ from $I$ otherwise) is called \textit{toggling}
$a$ in $I$. This is always an involution: $\left(  I\bigtriangleup\left\{
a\right\}  \right)  \bigtriangleup\left\{  a\right\}  =I$ for any $I$ and $a$.

\item \textbf{Remark:} It was actually sufficient for our proof that the map
$I\mapsto I\bigtriangleup\left\{  1\right\}  $ is a bijection, not necessarily
an involution. But all such maps we will encounter are involutions.
\end{itemize}

\subsection{All subsets not too large}

\begin{itemize}
\item Let us try the second identity:

\textbf{Theorem.} Let $n$ be any number (e.g., a real), and let $m$ be a
nonnegative integer. Then,%
\[
\sum_{k=0}^{m}\left(  -1\right)  ^{k}\dbinom{n}{k}=\left(  -1\right)
^{m}\dbinom{n-1}{m}.
\]


\item \textbf{Proof.} First of all, we are proving a polynomial identity in
$n$, so we WLOG assume that $n$ is a positive integer (since two polynomials
over a field are equal if they agree on sufficiently many points).

We have%
\[
\sum_{k=0}^{m}\left(  -1\right)  ^{k}\dbinom{n}{k}=\sum_{\substack{I\subseteq
\left[  n\right]  ;\\\left\vert I\right\vert \leq m}}\left(  -1\right)
^{\left\vert I\right\vert }.
\]


Now, we try the involution from the previous proof:%
\begin{align*}
\left\{  \text{subsets of }\left[  n\right]  \right\}   &  \rightarrow\left\{
\text{subsets of }\left[  n\right]  \right\}  ,\\
I  &  \mapsto I\bigtriangleup\left\{  1\right\}  .
\end{align*}


Unfortunately, applying it to a set $I$ might break the $\left\vert
I\right\vert \leq m$ restriction. But it restricts to an involution%
\begin{align*}
\mathcal{A}  &  \rightarrow\mathcal{A},\\
I  &  \mapsto I\bigtriangleup\left\{  1\right\}  ,
\end{align*}
where
\[
\mathcal{A}=\left\{  \text{subsets }I\text{ of }\left[  n\right]  \text{ with
}\left\vert I\setminus\left\{  1\right\}  \right\vert <m\right\}  .
\]
Thus, all addends in the sum $\sum_{\substack{I\subseteq\left[  n\right]
;\\\left\vert I\right\vert \leq m}}\left(  -1\right)  ^{\left\vert
I\right\vert }$ cancel except for those with $\left\vert I\setminus\left\{
1\right\}  \right\vert =m$. We get%
\[
\sum_{\substack{I\subseteq\left[  n\right]  ;\\\left\vert I\right\vert \leq
m}}\left(  -1\right)  ^{\left\vert I\right\vert }=\sum_{\substack{I\subseteq
\left[  n\right]  ;\\\left\vert I\right\vert \leq m;\\\left\vert
I\setminus\left\{  1\right\}  \right\vert =m}}\left(  -1\right)  ^{\left\vert
I\right\vert }=\sum_{\substack{I\subseteq\left[  n\right]  ;\\1\notin
I;\\\left\vert I\right\vert =m}}\left(  -1\right)  ^{\left\vert I\right\vert
}=\left(  -1\right)  ^{m}\dbinom{n-1}{m},
\]
since there are exactly $\dbinom{n-1}{m}$ many subsets $I$ of $\left[
n\right]  $ satisfying $1\notin I$ and $\left\vert I\right\vert =m$. This
completes our proof.
\end{itemize}

\subsection{Lacunar subsets}

\begin{itemize}
\item Now to the third identity:

\textbf{Theorem.} Let $n$ be a nonnegative integer. Then,%
\[
\sum_{k=0}^{\left\lfloor n/2\right\rfloor }\left(  -1\right)  ^{k}\dbinom
{n-k}{k}=%
\begin{cases}
1, & \text{if }n\%6\in\left\{  0,1\right\}  ;\\
0, & \text{if }n\%6\in\left\{  2,5\right\}  ;\\
-1, & \text{if }n\%6\in\left\{  3,4\right\}  ,
\end{cases}
\]
where $n\%6$ means the remainder of $n$ divided by $6$.

\item To prove this combinatorially, we need to find out what $\dbinom{n-k}%
{k}$ counts.

\item \textbf{Convention.} We shall write $\left[  m\right]  $ for $\left\{
1,2,\ldots,m\right\}  $ whenever $m\in\mathbb{Z}$.

\item \textbf{Definition.} A set $I$ of integers is said to be
\textit{lacunar} if it contains no two consecutive integers (i.e., there is no
$i\in I$ such that $i+1\in I$).

\item For example, $\left\{  1,3,6\right\}  $ is lacunar, but $\left\{
1,3,4\right\}  $ is not. Empty and one-element sets are always lacunar.

\item Note that any lacunar subset of $\left[  n-1\right]  $ has size
$\leq\left\lfloor n/2\right\rfloor $.

\item \textbf{Proposition.} For any $n\geq k\geq0$, the number of lacunar
$k$-element subsets of $\left[  n-1\right]  $ is $\dbinom{n-k}{k}$.

\item \textbf{Proof.} Write \textquotedblleft elt\textquotedblright\ for
\textquotedblleft element\textquotedblright, and \textquotedblleft
subs\textquotedblright\ for \textquotedblleft subsets\textquotedblright.

There is a bijection%
\begin{align*}
\left\{  \text{lacunar }k\text{-elt subs of }\left[  n-1\right]  \right\}   &
\rightarrow\left\{  k\text{-elt subs of }\left\{  0,1,\ldots,n-k-1\right\}
\right\}  ,\\
\left\{  i_{1}<i_{2}<\cdots<i_{k}\right\}   &  \mapsto\left\{  i_{1}%
-1<i_{2}-2<\cdots<i_{k}-k\right\}  .
\end{align*}


\item Thus, we can start a \textbf{combinatorial proof} of our theorem as
follows:%
\[
\sum_{k=0}^{\left\lfloor n/2\right\rfloor }\left(  -1\right)  ^{k}\dbinom
{n-k}{k}=\sum_{\substack{I\subseteq\left[  n-1\right]  ;\\I\text{ is lacunar}%
}}\left(  -1\right)  ^{\left\vert I\right\vert }.
\]


We want to prove that this is $1$ or $0$ or $-1$.

So let us try to construct a sign-reversing involution on the set%
\[
\left\{  \text{lacunar subsets of }\left[  n-1\right]  \right\}
\]
except for possibly one element.

Let $I$ be a lacunar subset of $\left[  n-1\right]  $.

\begin{itemize}
\item We try to toggle $1$ in $I$, but we only do this if the result is lacunar.

If we succeed (i.e., if the result is lacunar), then we are done.

[\textbf{Examples:}

\begin{itemize}
\item If $I=\left\{  1,3,7\right\}  $, then we toggle $1$, and obtain the set
$\left\{  3,7\right\}  $. Thus, in this case, we succeed and have found the
image of $I$ under our involution.

\item If $I=\left\{  3,7\right\}  $, then we toggle $1$, and obtain the set
$\left\{  1,3,7\right\}  $. Thus, in this case, we succeed and have found the
image of $I$ under our involution.

\item If $I=\left\{  2,7\right\}  $, then we cannot toggle $1$, since this
would produce the non-lacunar set $\left\{  1,2,7\right\}  $. Thus, in this
case, we don't succeed and move on to the next step.]
\end{itemize}

\item If we have not succeeded in the previous step, then $2\in I$ and thus
$3\notin I$.

Thus we try to toggle $4$ in $I$, but we only do this if the result is lacunar.

If we succeed, then we are done.

[\textbf{Examples:}

\begin{itemize}
\item If $I=\left\{  2,4,9\right\}  $, then we toggle $4$, and obtain the set
$\left\{  2,9\right\}  $. Thus, in this case, we succeed and have found the
image of $I$ under our involution.

\item If $I=\left\{  2,9\right\}  $, then we toggle $4$, and obtain the set
$\left\{  2,4,9\right\}  $. Thus, in this case, we succeed and have found the
image of $I$ under our involution.

\item If $I=\left\{  2,5,8\right\}  $, then we cannot toggle $4$, since this
would produce the non-lacunar set $\left\{  2,4,5,8\right\}  $. Thus, in this
case, we don't succeed and move on to the next step.

\item If $I=\left\{  1,3,7\right\}  $, then we do not get to this step in the
first place, since the first step has already succeeded (turning $I$ into
$\left\{  3,7\right\}  $).]
\end{itemize}

\item If we have not succeeded in the previous step, then $5\in I$ and thus
$6\notin I$.

Thus we try to toggle $7$ in $I$, but we only do this if the result is lacunar.

If we succeed, then we are done.

\item And so on.
\end{itemize}

This operation goes on until we have run out of elements of $\left[
n-1\right]  $ to toggle. The only case in which we fail to toggle anything is
if%
\[
n\not \equiv 2\operatorname{mod}3\text{ and }I=\left\{  2,5,8,\ldots\right\}
\cap\left[  n-1\right]  .
\]


Thus we have found a sign-reversing involution on the set $\left\{
\text{lacunar subsets of }\left[  n-1\right]  \right\}  $ with the exception
of a single lacunar subset if $n\not \equiv 2\operatorname{mod}3$ (and with no
exceptions if $n\equiv2\operatorname{mod}3$). The conclusion easily follows.

\item This proof is in \cite{BenQui08} (where it is worded using domino
tilings instead of lacunar subsets).
\end{itemize}

\subsection{Independent sets of a graph}

\begin{itemize}
\item Let us generalize this.

\item \textbf{Definition.} Let $\Gamma=\left(  V,E\right)  $ be an
(undirected) graph. An \textit{independent set} of $\Gamma$ means a subset $I$
of $V$ such that no two vertices in $I$ are adjacent (i.e., no edge of
$\Gamma$ connects two vertices in $I$).

\item \textbf{Example.} For the following graph:%
\[%
%TCIMACRO{\TeXButton{tikz kiepert graph}{\begin{tikzpicture}%
%[-,auto,node distance=3cm, thick,main node/.style={circle,fill=blue!20,draw}]
%\node[main node] (u) at (180:3) {$u$};
%\node[main node] (y) at (240:3) {$y$};
%\node[main node] (w) at (300:3) {$w$};
%\node[main node] (x) at (0:3) {$x$};
%\node[main node] (v) at (60:3) {$v$};
%\node[main node] (z) at (120:3) {$z$};
%\path[every node/.style={font=\sffamily\small}]
%(x) edge (v) (v) edge (z) (z) edge (u) (u) edge (y) (y) edge (w) (w) edge (x)
%(u) edge (v) (v) edge (w) (w) edge (u);
%\end{tikzpicture}}}%
%BeginExpansion
\begin{tikzpicture}%
[-,auto,node distance=3cm, thick,main node/.style={circle,fill=blue!20,draw}]
\node[main node] (u) at (180:3) {$u$};
\node[main node] (y) at (240:3) {$y$};
\node[main node] (w) at (300:3) {$w$};
\node[main node] (x) at (0:3) {$x$};
\node[main node] (v) at (60:3) {$v$};
\node[main node] (z) at (120:3) {$z$};
\path[every node/.style={font=\sffamily\small}]
(x) edge (v) (v) edge (z) (z) edge (u) (u) edge (y) (y) edge (w) (w) edge (x)
(u) edge (v) (v) edge (w) (w) edge (u);
\end{tikzpicture}%
%EndExpansion
\]
the independent sets are%
\[
\left\{  x,y\right\}  ,\ \left\{  y,z\right\}  ,\ \left\{  z,x\right\}
,\ \left\{  u,x\right\}  ,\ \left\{  v,y\right\}  ,\ \left\{  w,z\right\}
,\ \left\{  x,y,z\right\}
\]
as well as all $1$-element sets and the empty set.

\item For any $m\geq0$, let the $m$\textit{-path} be the graph%
\[
1-2-3-\cdots-m
\]
(that is, the graph with vertices $1,2,\ldots,m$ and edges $\left\{
i,i+1\right\}  $ for each $0<i<m$).

Then, the lacunar subsets of $\left[  m\right]  $ are the independent sets of
the $m$-path.

\item Now we can generalize our previous theorem as follows:

\textbf{Question:} For what graphs $\Gamma$ do we have%
\[
\sum_{\substack{I\text{ is an independent}\\\text{set of }\Gamma}}\left(
-1\right)  ^{\left\vert I\right\vert }\in\left\{  1,0,-1\right\}  \text{ ?}%
\]


\item Certainly not for all graphs $\Gamma$ (e.g., the $4$-cycle is a counterexample).

\item But we know it's true for path graphs. For what other graphs?

\item We can try to construct a sign-reversing involution again, and see where
we fail.

\item What order do we try to toggle the vertices in?

\item Well, we can always pick some order at random.

\item Unfortunately, toggling a vertex might be blocked by several vertices.

\item Trying to solve the resulting conflicts often fails (e.g., for a
$4$-cycle, even though the sum is $-1$ for a $4$-cycle).

\item Our above proof can be adapted when $\Gamma$ is a forest
(\cite[Corollary 6.1]{EhrHet06})).

\item However, a much more general result holds:

\item \textbf{Theorem (conjectured by Kalai and Meshulam, 1990s, proved by
Chudnovsky, Scott, Seymour, Spirkl, 2018 (\cite{CSSS18})):} Let $\Gamma$ be a
simple loopless undirected graph that has no induced cycle of length divisible
by $3$. Then,%
\[
\sum_{\substack{I\text{ is an independent}\\\text{set of }\Gamma}}\left(
-1\right)  ^{\left\vert I\right\vert }\in\left\{  1,0,-1\right\}  .
\]


\item \textbf{Question:} Is there any proof under 10 pages length?
\end{itemize}

\subsection{Dominating sets of a graph}

\begin{itemize}
\item \textbf{Definition.} Let $\Gamma=\left(  V,E\right)  $ be an
(undirected) graph. A \textit{dominating set} of $\Gamma$ means a subset $I$
of $V$ such that each vertex of $\Gamma$ belongs to $I$ or has a neighbor in
$I$.

\item \textbf{Example.} For the following graph:%
\[%
%TCIMACRO{\TeXButton{tikz kiepert graph}{\begin{tikzpicture}%
%[-,auto,node distance=3cm, thick,main node/.style={circle,fill=blue!20,draw}]
%\node[main node] (u) at (180:3) {$u$};
%\node[main node] (y) at (240:3) {$y$};
%\node[main node] (w) at (300:3) {$w$};
%\node[main node] (x) at (0:3) {$x$};
%\node[main node] (v) at (60:3) {$v$};
%\node[main node] (z) at (120:3) {$z$};
%\path[every node/.style={font=\sffamily\small}]
%(x) edge (v) (v) edge (z) (z) edge (u) (u) edge (y) (y) edge (w) (w) edge (x)
%(u) edge (v) (v) edge (w) (w) edge (u);
%\end{tikzpicture}}}%
%BeginExpansion
\begin{tikzpicture}%
[-,auto,node distance=3cm, thick,main node/.style={circle,fill=blue!20,draw}]
\node[main node] (u) at (180:3) {$u$};
\node[main node] (y) at (240:3) {$y$};
\node[main node] (w) at (300:3) {$w$};
\node[main node] (x) at (0:3) {$x$};
\node[main node] (v) at (60:3) {$v$};
\node[main node] (z) at (120:3) {$z$};
\path[every node/.style={font=\sffamily\small}]
(x) edge (v) (v) edge (z) (z) edge (u) (u) edge (y) (y) edge (w) (w) edge (x)
(u) edge (v) (v) edge (w) (w) edge (u);
\end{tikzpicture}%
%EndExpansion
\]
the \textbf{non-dominating} sets are%
\[
\left\{  u,y,z\right\}  ,\ \ \left\{  v,z,x\right\}  ,\ \ \left\{
w,x,y\right\}
\]
as well as all their subsets.

\item \textbf{Theorem (e.g., Brouwer 2009 (\cite{Brouwe09}, \cite{BrCsSc09}%
)):} The number of dominating sets of a graph $\Gamma$ is always odd.

\item \textbf{Theorem (Heinrich, Tittmann, 2017 (\cite{HeiTit17},
\cite[Theorem 3.2.2]{nogra})):} The number of dominating sets of a graph
$\Gamma=\left(  V,E\right)  $ is%
\[
2^{\left\vert V\right\vert }-1+\underbrace{\sum_{\substack{\text{pairs
}\left(  A,B\right)  \text{ of disjoint}\\\text{nonempty subsets of
}V;\\\left\{  a,b\right\}  \notin E\text{ for all }a\in A\text{ and }b\in
B;\\\left\vert A\right\vert \equiv\left\vert B\right\vert \operatorname{mod}%
2}}\left(  -1\right)  ^{\left\vert A\right\vert }}_{\substack{\text{This is
even for symmetry reasons}\\\text{(for any }\left(  A,B\right)  \text{, there
is a }\left(  B,A\right)  \text{)}}}.
\]


\item What about the alternating sum%
\[
\sum_{\substack{I\text{ is a dominating}\\\text{set of }\Gamma}}\left(
-1\right)  ^{\left\vert I\right\vert }\text{\ ?}%
\]
Is it $\pm1$ ?

\item No; for example:

\textbf{Theorem (Alikhani, 2012 (\cite[Lemma 1]{Alikha12})):} If $\Gamma$ is
an $n$-cycle (for $n>0$), then this alternating sum is%
\[%
\begin{cases}
3, & \text{if }n\equiv0\operatorname{mod}4;\\
-1, & \text{otherwise.}%
\end{cases}
\]


\textbf{Exercise:} Prove this! (Is there a nice proof without too much casework?)

\item \textbf{Theorem (Ehrenborg, Hetyei, 2005 (\cite[\S 7]{EhrHet06})):} The
alternating sum is $\pm1$ whenever $\Gamma$ is a forest.
\end{itemize}

\section{Simplicial complexes}

\subsection{Basic definitions}

\begin{itemize}
\item The sums we have been discussing so far didn't range over some random
collections of sets. Most of them had a commonality: If a set $I$ appeared in
the sum, then so did any subset of $I$.

\item Such collections of sets are called \textbf{simplicial complexes}.

\item Formally:

\textbf{Definition.} A \textit{simplicial complex} means a pair $\left(
S,\Delta\right)  $, where $S$ is a finite set and $\Delta$ is a collection (=
set) of subsets of $S$ such that%
\[
\text{any }I\in\Delta\text{ and }J\subseteq I\text{ satisfy }J\in\Delta.
\]


\item We often just write $\Delta$ for a simplicial complex $\left(
S,\Delta\right)  $.

\item A \textit{face} of a simplicial complex $\Delta$ means a set $I\in
\Delta$.

\item Note that $\left\{  {}\right\}  $ and $\left\{  \varnothing\right\}  $
are two different simplicial complexes on any set $S$.

\item \textbf{Examples} of simplicial complexes\textbf{:}

\begin{itemize}
\item $\left\{  \text{all subsets of }S\right\}  $ for a given finite set $S$.

\item $\left\{  \text{all lacunar subsets of }\left[  m\right]  \right\}  $
for a given $m\in\mathbb{N}$.

\item $\left\{  \text{all independent sets of }\Gamma\right\}  $ for a given
graph $\Gamma$.

\item \textbf{not }$\left\{  \text{all dominating sets of }\Gamma\right\}  $
for a given graph $\Gamma$.

\item $\left\{  \text{all non-dominating sets of }\Gamma\right\}  $ and
$\left\{  \text{all complements of dominating sets of }\Gamma\right\}  $ for a
given graph $\Gamma$.
\end{itemize}

(Here the ground set is the set of vertices of $\Gamma$.)
\end{itemize}

\subsection{Geometric realizations}

\begin{itemize}
\item Each simplicial complex $\left(  S,\Delta\right)  $ has a
\textit{geometric realization} $\left\vert \Delta\right\vert $, which is a
topological space glued out of (geometric) simplices. The easiest way to
define it is by assuming (WLOG) that $S=\left[  n\right]  $ for some
$n\in\mathbb{N}$, and setting%
\begin{align*}
\left\vert \Delta\right\vert  &  =\left\{  \left(  t_{1},t_{2},\ldots
,t_{n}\right)  \in\mathbb{R}_{\geq0}^{n}\ \mid\ t_{1}+t_{2}+\cdots
+t_{n}=1\right. \\
&  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left.  \text{and }\left\{
i\ \mid\ t_{i}>0\right\}  \in\Delta\right\}  .
\end{align*}


\item Normally we don't draw the literal $\left\vert \Delta\right\vert $
(since $\mathbb{R}^{n}$ has too high dimension) but just something
homeomorphic to it (usually in a smaller space).

\item Some examples:

\begin{itemize}
\item The complex $\left\{  \text{all independent sets of }\Gamma\right\}  $
of the graph $\Gamma$ on the left is the simplicial complex drawn on the
right:%
\[%
%TCIMACRO{\TeXButton{tikz kiepert graph}{\begin{tikzpicture}%
%[-,auto,node distance=3cm, thick,main node/.style={circle,fill=blue!20,draw}]
%\node[main node] (u) at (180:3) {$u$};
%\node[main node] (y) at (240:3) {$y$};
%\node[main node] (w) at (300:3) {$w$};
%\node[main node] (x) at (0:3) {$x$};
%\node[main node] (v) at (60:3) {$v$};
%\node[main node] (z) at (120:3) {$z$};
%\path[every node/.style={font=\sffamily\small}]
%(x) edge (v) (v) edge (z) (z) edge (u) (u) edge (y) (y) edge (w) (w) edge (x)
%(u) edge (v) (v) edge (w) (w) edge (u);
%\end{tikzpicture}}}%
%BeginExpansion
\begin{tikzpicture}%
[-,auto,node distance=3cm, thick,main node/.style={circle,fill=blue!20,draw}]
\node[main node] (u) at (180:3) {$u$};
\node[main node] (y) at (240:3) {$y$};
\node[main node] (w) at (300:3) {$w$};
\node[main node] (x) at (0:3) {$x$};
\node[main node] (v) at (60:3) {$v$};
\node[main node] (z) at (120:3) {$z$};
\path[every node/.style={font=\sffamily\small}]
(x) edge (v) (v) edge (z) (z) edge (u) (u) edge (y) (y) edge (w) (w) edge (x)
(u) edge (v) (v) edge (w) (w) edge (u);
\end{tikzpicture}%
%EndExpansion
\ \ \ \ \ \
%TCIMACRO{\TeXButton{tikz triangle with antlers}{\begin{tikzpicture}%
%[thick, main node/.style={circle,fill=yellow!20,draw}]
%\filldraw[draw=black, fill=red!70] (-1, -1) -- (0, 1) -- (1, -1) -- cycle;
%\node[main node] (w) at (0, 2.4) {$w$};
%\node[main node] (x) at (-1, -1) {$x$};
%\node[main node] (v) at (2, -2) {$v$};
%\node[main node] (z) at (0, 1) {$z$};
%\node[main node] (u) at (-2, -2) {$u$};
%\node[main node] (y) at (1, -1) {$y$};
%\draw(u) edge (x);
%\draw(v) edge (y);
%\draw(w) edge (z);
%\end{tikzpicture}}}%
%BeginExpansion
\begin{tikzpicture}[thick, main node/.style={circle,fill=yellow!20,draw}]
\filldraw[draw=black, fill=red!70] (-1, -1) -- (0, 1) -- (1, -1) -- cycle;
\node[main node] (w) at (0, 2.4) {$w$};
\node[main node] (x) at (-1, -1) {$x$};
\node[main node] (v) at (2, -2) {$v$};
\node[main node] (z) at (0, 1) {$z$};
\node[main node] (u) at (-2, -2) {$u$};
\node[main node] (y) at (1, -1) {$y$};
\draw(u) edge (x);
\draw(v) edge (y);
\draw(w) edge (z);
\end{tikzpicture}%
%EndExpansion
\]


\item The complex $\left\{  \text{all non-dominating sets of }\Gamma\right\}
$ of the graph $\Gamma$ on the left is the simplicial complex drawn on the
right:%
\[%
%TCIMACRO{\TeXButton{tikz kiepert graph}{\begin{tikzpicture}%
%[-,auto,node distance=3cm, thick,main node/.style={circle,fill=blue!20,draw}]
%\node[main node] (u) at (180:3) {$u$};
%\node[main node] (y) at (240:3) {$y$};
%\node[main node] (w) at (300:3) {$w$};
%\node[main node] (x) at (0:3) {$x$};
%\node[main node] (v) at (60:3) {$v$};
%\node[main node] (z) at (120:3) {$z$};
%\path[every node/.style={font=\sffamily\small}]
%(x) edge (v) (v) edge (z) (z) edge (u) (u) edge (y) (y) edge (w) (w) edge (x)
%(u) edge (v) (v) edge (w) (w) edge (u);
%\end{tikzpicture}}}%
%BeginExpansion
\begin{tikzpicture}%
[-,auto,node distance=3cm, thick,main node/.style={circle,fill=blue!20,draw}]
\node[main node] (u) at (180:3) {$u$};
\node[main node] (y) at (240:3) {$y$};
\node[main node] (w) at (300:3) {$w$};
\node[main node] (x) at (0:3) {$x$};
\node[main node] (v) at (60:3) {$v$};
\node[main node] (z) at (120:3) {$z$};
\path[every node/.style={font=\sffamily\small}]
(x) edge (v) (v) edge (z) (z) edge (u) (u) edge (y) (y) edge (w) (w) edge (x)
(u) edge (v) (v) edge (w) (w) edge (u);
\end{tikzpicture}%
%EndExpansion
\ \ \ \ \
%TCIMACRO{\TeXButton{tikz kiepert complex}{\begin{tikzpicture}%
%[-,auto,node distance=3cm, thick,main node/.style={circle,fill=blue!20,draw}]
%\filldraw[draw=black, fill=red!70] (60:3) -- (300:3) -- (0:3) -- cycle;
%\filldraw[draw=black, fill=red!70] (300:3) -- (180:3) -- (240:3) -- cycle;
%\filldraw[draw=black, fill=red!70] (180:3) -- (60:3) -- (120:3) -- cycle;
%\node[main node] (x) at (180:3) {$x$};
%\node[main node] (v) at (240:3) {$v$};
%\node[main node] (z) at (300:3) {$z$};
%\node[main node] (u) at (0:3) {$u$};
%\node[main node] (y) at (60:3) {$y$};
%\node[main node] (w) at (120:3) {$w$};
%\path[every node/.style={font=\sffamily\small}]
%(u) edge (y) (y) edge (w) (w) edge (x) (x) edge (v) (v) edge (z) (z) edge (u)
%(x) edge (y) (y) edge (z) (z) edge (x);
%\end{tikzpicture}}}%
%BeginExpansion
\begin{tikzpicture}%
[-,auto,node distance=3cm, thick,main node/.style={circle,fill=blue!20,draw}]
\filldraw[draw=black, fill=red!70] (60:3) -- (300:3) -- (0:3) -- cycle;
\filldraw[draw=black, fill=red!70] (300:3) -- (180:3) -- (240:3) -- cycle;
\filldraw[draw=black, fill=red!70] (180:3) -- (60:3) -- (120:3) -- cycle;
\node[main node] (x) at (180:3) {$x$};
\node[main node] (v) at (240:3) {$v$};
\node[main node] (z) at (300:3) {$z$};
\node[main node] (u) at (0:3) {$u$};
\node[main node] (y) at (60:3) {$y$};
\node[main node] (w) at (120:3) {$w$};
\path[every node/.style={font=\sffamily\small}]
(u) edge (y) (y) edge (w) (w) edge (x) (x) edge (v) (v) edge (z) (z) edge (u)
(x) edge (y) (y) edge (z) (z) edge (x);
\end{tikzpicture}%
%EndExpansion
\]

\end{itemize}
\end{itemize}

\subsection{Homotopy and homology}

\begin{itemize}
\item A lot of features come for free with the geometric realization:

The \textit{homotopy type}, the \textit{homology} and the \textit{reduced
Euler characteristic} of a simplicial complex $\Delta$ are defined to be the
homotopy type, the homology and the reduced Euler characteristic of its
geometric realization.

\item Explicitly, the Euler characteristic of a complex $\Delta$ is simply%
\[
\sum_{I\in\Delta}\left(  -1\right)  ^{\left\vert I\right\vert -1}.
\]
(The \textquotedblleft$-1$\textquotedblright\ in the exponent just negates the
whole sum.)

\item Thus, the alternating sums we have been computing are actually Euler
characteristics in disguise.

\item Homology is a stronger invariant than Euler characteristic, and homotopy
type is an even stronger invariant than homology:%
\begin{align*}
&  \left(  \text{homotopy type}\right)  \twoheadrightarrow\left(
\text{homology over }\mathbb{Z}\right)  \twoheadrightarrow\left(
\text{homology over }\mathbb{Q}\right) \\
&  \twoheadrightarrow\left(  \text{Euler characteristic}\right)  .
\end{align*}
Our results above are all about Euler characteristics; can we lift them to
those stronger invariants?

\item Note that homology can be easily redefined combinatorially in terms of
$\Delta$. (Homotopy type, too, but less easily; see \cite[Proposition
9.28]{Kozlov20}.)
\end{itemize}

\subsection{Examples of homotopy types}

\begin{itemize}
\item Our first theorem said that the reduced Euler characteristic of the
simplicial complex%
\[
\left\{  \text{all subsets of }E\right\}
\]
is $0$ for any nonempty finite set $E$. This lifts all the way up to homotopy level:

\textbf{Proposition.} This simplicial complex is contractible (i.e.,
homotopy-equivalent to a point).

Geometrically, this is clear: Its geometric realization is a simplex, hence
homeomorphic to an $\left(  n-1\right)  $-ball, where $n=\left\vert
E\right\vert $.

\item Our second theorem was%
\[
\sum_{k=0}^{m}\left(  -1\right)  ^{k}\dbinom{n}{k}=\left(  -1\right)
^{m}\dbinom{n-1}{m}.
\]
This corresponds to the simplicial complex%
\[
\left\{  \text{all subsets of }\left[  n\right]  \text{ having size }\leq
m\right\}  .
\]
This is called the $\left(  m-1\right)  $\textit{-skeleton} of the $\left(
n-1\right)  $-ball. By classical algebraic topology, it is homotopy-equivalent
to a bouquet of $\dbinom{n-1}{m}$ many $\left(  m-1\right)  $-spheres, which
again explains the Euler characteristic.

\item Now, recall the independent sets of graphs.

\textbf{Theorem (Kalai, Meshulam, Engstr\"{o}m, Chudnovsky, Scott, Seymour,
Spirkl, Zhang, Wu, Kim, 2021 (\cite{ZhaWu20}, \cite{Kim21})):} Let $\Gamma$ be
a simple loopless undirected graph that has no induced cycle of length
divisible by $3$. Then, the simplicial complex%
\[
\left\{  \text{independent sets of }\Gamma\right\}
\]
is either contractible or homotopy-equivalent to a sphere (whence its reduced
Euler characteristic is in $\left\{  1,0,-1\right\}  $).

\item As we recall, the dominating sets of a graph do not form a simplicial
complex, but their complements do, and so do the non-dominating sets. As far
as the alternating sum $\sum_{I}\left(  -1\right)  ^{\left\vert I\right\vert
}$ is concerned, these are just as good (switching between dominating and
non-dominating sets or between the sets and their complements changes the sum
by a factor of $\pm1$).

\textbf{Theorem (Ehrenborg, Hetyei, 2005 (\cite[\S 7]{EhrHet06})):} Let
$\Gamma$ be a forest. Then, both simplicial complexes
\begin{align*}
&  \left\{  \text{non-dominating sets of }\Gamma\right\}
\ \ \ \ \ \ \ \ \ \ \text{and}\\
&  \left\{  \text{complements of dominating sets of }\Gamma\right\}
\end{align*}
are either contractible or homotopy-equivalent to a sphere.

\item \textbf{Question:} What can be said about the case when $\Gamma$ is an
$n$-cycle?
\end{itemize}

\subsection{Discrete Morse theory}

\begin{itemize}
\item Thus we have two approaches to proving formulas for alternating sums:%
\[%
%TCIMACRO{\TeXButton{V}{\xymatrix{
%{\substack{\text{sign-reversing}\\\text{involution}}} \ar[rd] & & {\substack
%{\text{homotopy}\\\text{type}}} \ar[ld] \\
%& \sum_{I \in\Delta} \left(-1\right)^{\left|I\right|}
%}}}%
%BeginExpansion
\xymatrix{
{\substack{\text{sign-reversing}\\\text{involution}}} \ar[rd] & & {\substack
{\text{homotopy}\\\text{type}}} \ar[ld] \\
& \sum_{I \in\Delta} \left(-1\right)^{\left|I\right|}
}%
%EndExpansion
\]


\item Could these two approaches be combined? I.e., is there a technique that
gets us both homotopy information and a sign-reversing involution in one
(possibly harder) swoop?%
\[%
%TCIMACRO{\TeXButton{diamond with ???}{\xymatrix{
%& ??? \ar[rd] \ar[ld] \\
%{\substack{\text{sign-reversing}\\\text{involution}}} \ar[rd] & & {\substack
%{\text{homotopy}\\\text{type}}} \ar[ld] \\
%& \sum_{I \in\Delta} \left(-1\right)^{\left|I\right|}
%}}}%
%BeginExpansion
\xymatrix{
& ??? \ar[rd] \ar[ld] \\
{\substack{\text{sign-reversing}\\\text{involution}}} \ar[rd] & & {\substack
{\text{homotopy}\\\text{type}}} \ar[ld] \\
& \sum_{I \in\Delta} \left(-1\right)^{\left|I\right|}
}%
%EndExpansion
\]


\item \textit{Discrete Morse theory} is an answer. We will use some of its
very basics.

\item \textbf{Definition.} For two sets $I$ and $J$, we write $I\prec J$ if
$J=I\cup\left\{  \text{a single element}\right\}  $ (that is, if $I\subseteq
J$ and $\left\vert J\setminus I\right\vert =1$). Equivalently, we write
$J\succ I$ for this.

\item \textbf{Definition.} Let $\left(  S,\Delta\right)  $ be a simplicial
complex. A \textit{partial matching} on $\Delta$ shall mean an involution
$\mu:\Delta\rightarrow\Delta$ such that
\[
\mu\left(  I\right)  =I\text{ or }\mu\left(  I\right)  \prec I\text{ or }%
\mu\left(  I\right)  \succ I\qquad\text{for each }I\in\Delta.
\]


In other words, $\mu\left(  I\right)  $ is either $I$ itself or is obtained
from $I$ by removing or inserting a single element.

\item \textbf{Definition.} If $\mu$ is a partial matching on $\Delta$, then
the sets $I\in\Delta$ satisfying $\mu\left(  I\right)  =I$ will be called
\textit{unmatched} (by $\mu$).

\item Thus, if $\mu$ is a partial matching on $\Delta$, then%
\[
\sum_{I\in\Delta}\left(  -1\right)  ^{\left\vert I\right\vert }=\sum
_{\substack{I\in\Delta\text{ is}\\\text{unmatched}}}\left(  -1\right)
^{\left\vert I\right\vert }%
\]
(by cancellation).

\item Thus, partial matchings are just our partial sign-reversing involutions
rewritten (instead of taking some sets out of our complex, we are now leaving
them fixed).

\item What about the homotopy information? We cannot in general
\textquotedblleft cancel\textquotedblright\ matched faces from a simplicial
complex and hope that the homotopy information is preserved.

\item However, we can restrict our matchings in a way that will make them
homotopy-friendly! This is one of the main contributions of Forman that became
discrete Morse theory (\cite[\S 3, \S 6]{Forman02}, \cite{Kozlov20}):

\item \textbf{Definition.} Let $\left(  S,\Delta\right)  $ be a simplicial
complex. A partial matching $\mu$ on $\Delta$ is said to be \textit{acyclic}
(or a \textit{Morse matching}) if there exists no \textquotedblleft
cycle\textquotedblright\ of the form%
\[
I_{1}\succ\mu\left(  I_{1}\right)  \prec I_{2}\succ\mu\left(  I_{2}\right)
\prec I_{3}\succ\cdots\prec I_{n}\succ\mu\left(  I_{n}\right)  \prec I_{1}%
\]
with $n\geq2$ and with $I_{1},I_{2},\ldots,I_{n}$ distinct.

\item \textbf{Intuition:} The easiest way to ensure this is by making sure
that when $\mu$ adds an element to a face $I$, then it does so in an
\textquotedblleft optimal\textquotedblright\ way (i.e., among all ways to add
an element to $I$ and still obtain a face of $\Delta$, it picks the
\textquotedblleft best\textquotedblright\ one in some sense). This way, in the
above \textquotedblleft cycle\textquotedblright, the faces $I_{1},I_{2}%
,\ldots,I_{n},I_{1}$ become \textquotedblleft better and
better\textquotedblright, so the cycle cannot exist. There is freedom in
defining what \textquotedblleft optimal\textquotedblright/\textquotedblleft
best\textquotedblright\ is (it means specifying some partial order on the
faces of any given size).

This is why Forman calls acyclic matchings \textquotedblleft\textit{gradient
vector fields}\textquotedblright\ in \cite{Forman02}.

\item \textbf{Empiric fact(?):} Sign-reversing involutions in combinatorics
tend to be acyclic partial matchings.

\item \textbf{Question:} Really? Check some of the more complicated ones!

\item \textbf{Theorem (Forman, I believe).} Let $\left(  S,\Delta\right)  $ be
a simplicial complex, and $\mu$ an acyclic partial matching on $\Delta$. For
each $k\in\mathbb{N}$, let $c_{k}$ be the number of unmatched size-$k$ faces
of $\Delta$.

Then, there is a CW-complex homotopy-equivalent to $\Delta$ that has exactly
$c_{k}$ faces of dimension $k-1$ for each $k\in\mathbb{N}$.

\item \textbf{Corollary.} \textbf{(a)} If a simplicial complex $\left(
S,\Delta\right)  $ has an acyclic partial matching that leaves no face
unmatched, then it is contractible.

\textbf{(b)} If a simplicial complex $\left(  S,\Delta\right)  $ has an
acyclic partial matching that leaves exactly one face unmatched, then it is
homotopy-equivalent to a sphere.

\item As a consequence, having a good Morse matching gets us good (if not
100\% complete) information both about the homotopy type and about the
combinatorics of a simplicial complex.

\item For example, all the sign-reversing involutions we used in our proofs
above are Morse matchings.
\end{itemize}

\section{Elser's \textquotedblleft pandemic\textquotedblright\ complex}

\begin{itemize}
\item A remarkable alternating sum identity appeared in a 1984 paper by Elser
on mathematical physics (percolation theory) \cite{Elser84}. I shall restate
it in a slightly simpler language.

\item Fix a (finite undirected multi)graph $\Gamma$ with vertex set $V$ and
edge set $E$.

Fix a vertex $v\in V$.

\item If $F\subseteq E$, then an $F$\emph{-path} shall mean a path of $\Gamma$
such that all edges of the path belong to $F$.

\item If $e\in E$ is any edge and $F\subseteq E$ is any subset, then we say
that $F$ \emph{infects }$e$ if there exists an $F$-path from $v$ to some
endpoint of $e$.

(My go-to mental model: A virus starts out in $v$ and spreads along any
$F$-edge it can get to. Then, $F$ infects $e$ if the virus will eventually
reach an endpoint of $e$. Note that $F$ always infects any edge through $v$.)

\item A subset $F\subseteq E$ is said to be \emph{pandemic} if it infects each
edge $e\in E$.

\item \textbf{Example:} Let $\Gamma$ be%
\[%
%TCIMACRO{\TeXButton{graph with 6 vertices and 8 edges}{\begin{tikzpicture}%
%[-,>=stealth',shorten >=1pt,auto,node distance=3cm, thick,main node/.style={circle,fill=blue!20,draw}%
%]
%\node[main node] (1) {$v$};
%\node[main node] [above of=1] (2) {$p$};
%\node[main node] [right of=1] (3) {$w$};
%\node[main node] [above of=3] (4) {$q$};
%\node[main node] [right of=3] (5) {$t$};
%\node[main node] [above of=5] (6) {$r$};
%\path[every node/.style={font=\sffamily\small}] (1) edge node {$1$}
%(2) (2) edge node {$2$} (4) (4) edge node {$3$}
%(6) (6) edge [bend left] node {$4$} (5) (5) edge node {$5$}
%(3) (3) edge node {$6$} (1) (5) edge [bend left] node {$7$}
%(6) (4) edge node {$8$} (3);
%\end{tikzpicture}}}%
%BeginExpansion
\begin{tikzpicture}%
[-,>=stealth',shorten >=1pt,auto,node distance=3cm, thick,main node/.style={circle,fill=blue!20,draw}%
]
\node[main node] (1) {$v$};
\node[main node] [above of=1] (2) {$p$};
\node[main node] [right of=1] (3) {$w$};
\node[main node] [above of=3] (4) {$q$};
\node[main node] [right of=3] (5) {$t$};
\node[main node] [above of=5] (6) {$r$};
\path[every node/.style={font=\sffamily\small}] (1) edge node {$1$}
(2) (2) edge node {$2$} (4) (4) edge node {$3$}
(6) (6) edge [bend left] node {$4$} (5) (5) edge node {$5$}
(3) (3) edge node {$6$} (1) (5) edge [bend left] node {$7$}
(6) (4) edge node {$8$} (3);
\end{tikzpicture}%
%EndExpansion
\ \ .
\]
Then:

\begin{itemize}
\item The set $\left\{  1,2\right\}  \subseteq E$ infects edges $1,2,3,6,8$
(but no others), since the virus gets to the vertices $v,p,q$.

\item The set $\left\{  1,2,5\right\}  $ infects the same edges.

\item The set $\left\{  1,2,3\right\}  $ infects every edge other than $5$.

\item The set $\left\{  1,2,3,4\right\}  $ infects each edge, and thus is
pandemic (even though the virus never gets to vertex $w$).
\end{itemize}

\item \textbf{Theorem (Elser, 1984 (\cite[Lemma 1]{Elser84}, \cite[Theorem
1.2]{Grinbe20})):} Assume that $E\neq\varnothing$. Then,%
\[
\sum_{\substack{F\subseteq E\text{ is}\\\text{pandemic}}}\left(  -1\right)
^{\left\vert F\right\vert }=0.
\]


\item \textbf{Remark:} A version of pandemicity in which $F$ has to infect all
vertices (rather than all edges) would fail to produce such a theorem.
\end{itemize}

\subsection{More generally}

\begin{itemize}
\item If $F$ is a subset of $E$, then we define a subset
$\operatorname*{Shade}F$ of $E$ by%
\[
\operatorname*{Shade}F=\left\{  e\in E\ \mid\ F\text{ infects }e\right\}  .
\]


\item \textbf{Example:} Let $\Gamma$ be%
\[%
%TCIMACRO{\TeXButton{graph with 6 vertices and 8 edges}{\begin{tikzpicture}%
%[-,>=stealth',shorten >=1pt,auto,node distance=3cm, thick,main node/.style={circle,fill=blue!20,draw}%
%]
%\node[main node] (1) {$v$};
%\node[main node] [above of=1] (2) {$p$};
%\node[main node] [right of=1] (3) {$w$};
%\node[main node] [above of=3] (4) {$q$};
%\node[main node] [right of=3] (5) {$t$};
%\node[main node] [above of=5] (6) {$r$};
%\path[every node/.style={font=\sffamily\small}] (1) edge node {$1$}
%(2) (2) edge node {$2$} (4) (4) edge node {$3$}
%(6) (6) edge [bend left] node {$4$} (5) (5) edge node {$5$}
%(3) (3) edge node {$6$} (1) (5) edge [bend left] node {$7$}
%(6) (4) edge node {$8$} (3);
%\end{tikzpicture}}}%
%BeginExpansion
\begin{tikzpicture}%
[-,>=stealth',shorten >=1pt,auto,node distance=3cm, thick,main node/.style={circle,fill=blue!20,draw}%
]
\node[main node] (1) {$v$};
\node[main node] [above of=1] (2) {$p$};
\node[main node] [right of=1] (3) {$w$};
\node[main node] [above of=3] (4) {$q$};
\node[main node] [right of=3] (5) {$t$};
\node[main node] [above of=5] (6) {$r$};
\path[every node/.style={font=\sffamily\small}] (1) edge node {$1$}
(2) (2) edge node {$2$} (4) (4) edge node {$3$}
(6) (6) edge [bend left] node {$4$} (5) (5) edge node {$5$}
(3) (3) edge node {$6$} (1) (5) edge [bend left] node {$7$}
(6) (4) edge node {$8$} (3);
\end{tikzpicture}%
%EndExpansion
\ \ .
\]
Then, $\operatorname*{Shade}\left\{  1,2\right\}  =\left\{  1,2,3,6,8\right\}
$ and $\operatorname*{Shade}\left\{  1\right\}  =\left\{  1,2,6\right\}  $ and
$\operatorname*{Shade}\left\{  8\right\}  =\left\{  1,6\right\}  $.

\item \textbf{Theorem (\cite[Theorem 2.5]{Grinbe20}, generalizing Elser's
theorem):} Let $G$ be any subset of $E$. Assume that $E\neq\varnothing$. Then,%
\[
\sum_{\substack{F\subseteq E;\\G\subseteq\operatorname*{Shade}F}}\left(
-1\right)  ^{\left\vert F\right\vert }=0.
\]


\item \textbf{Theorem (\cite[Theorem 2.6]{Grinbe20}, equivalent restatement of
previous theorem):} Let $G$ be any subset of $E$. Then,%
\[
\sum_{\substack{F\subseteq E;\\G\not \subseteq \operatorname*{Shade}F}}\left(
-1\right)  ^{\left\vert F\right\vert }=0.
\]


\item This restatement looks useful since it gets rid of the $E\neq
\varnothing$ assumption. That's a good sign!
\end{itemize}

\subsection{Proof idea}

\begin{itemize}
\item Let's prove this latter restatement. Here is it again:

\textbf{Theorem (\cite[Theorem 2.6]{Grinbe20}, equivalent restatement of
previous theorem):} Let $G$ be any subset of $E$. Then,%
\[
\sum_{\substack{F\subseteq E;\\G\not \subseteq \operatorname*{Shade}F}}\left(
-1\right)  ^{\left\vert F\right\vert }=0.
\]


\item \textbf{Proof.} Let
\[
\mathcal{A}=\left\{  F\subseteq E\ \mid\ G\not \subseteq \operatorname*{Shade}%
F\right\}  .
\]
Equip the set $E$ with a total order. If $F\in\mathcal{A}$, then let
$\varepsilon\left(  F\right)  $ be the \textbf{smallest} edge $e\in
G\setminus\operatorname*{Shade}F$.

Define a sign-reversing involution%
\begin{align*}
\mathcal{A}  &  \rightarrow\mathcal{A},\\
F  &  \mapsto F\bigtriangleup\left\{  \varepsilon\left(  F\right)  \right\}  .
\end{align*}
Check that this works! (The key observation: $\operatorname*{Shade}F$ does not
change when we toggle $\varepsilon\left(  F\right)  $ in $F$.)
\end{itemize}

\subsection{Variants}

\begin{itemize}
\item We cannot replace \textquotedblleft infects all edges\textquotedblright%
\ by \textquotedblleft infects all vertices\textquotedblright\ as long as we
work with sets of edges.

\item However, we can work with sets of vertices instead (mutatis mutandis).

\item In detail:

\item If $F\subseteq V$, then an $F$\emph{-vertex-path} shall mean a path of
$\Gamma$ such that all vertices of the path except (possibly) for its two
endpoints belong to $F$. (Thus, if a path has only one edge or none, then it
automatically is an $F$-vertex-path.)

\item If $w\in V\setminus\left\{  v\right\}  $ is any vertex and $F\subseteq
V\setminus\left\{  v\right\}  $ is any subset, then we say that $F$
\emph{vertex-infects }$w$ if there exists an $F$-vertex-path from $v$ to $w$.
(This is always true when $w$ is $v$ or a neighbor of $v$.)

\item A subset $F\subseteq V\setminus\left\{  v\right\}  $ is said to be
\emph{vertex-pandemic} if it vertex-infects each vertex $w\in V\setminus
\left\{  v\right\}  $.

\item \textbf{Theorem (\cite[Theorem 3.2]{Grinbe20}).} Assume that
$V\setminus\left\{  v\right\}  \neq\varnothing$. Then,%
\[
\sum_{\substack{F\subseteq V\setminus\left\{  v\right\}  \text{ is}%
\\\text{vertex-pandemic}}}\left(  -1\right)  ^{\left\vert F\right\vert }=0.
\]


\item Generalizations similar to the one above also hold.
\end{itemize}

\subsection{A hammer in search of nails}

\begin{itemize}
\item The proofs of the original Elser's theorem and of its vertex variant are
suspiciously similar.

\item Even worse, they use barely any graph theory. All we needed is that $E$
is a finite set, and that $\operatorname*{Shade}:\mathcal{P}\left(  E\right)
\rightarrow\mathcal{P}\left(  E\right)  $ (where $\mathcal{P}\left(  E\right)
=\left\{  \text{all subsets of }E\right\}  $) is a map with the property that
\begin{align*}
\operatorname*{Shade}\left(  F\bigtriangleup\left\{  u\right\}  \right)   &
=\operatorname*{Shade}F\\
\qquad\text{for any }F  &  \subseteq E\text{ and }u\in E\setminus
\operatorname*{Shade}F.
\end{align*}
I call such a map $\operatorname*{Shade}$ a \textit{shade map}. Our above
argument then shows that%
\[
\sum_{\substack{F\subseteq E;\\G\not \subseteq \operatorname*{Shade}F}}\left(
-1\right)  ^{\left\vert F\right\vert }=0\qquad\text{for any }G\subseteq E.
\]


\item \textbf{Question.} Have you seen other maps satisfying this property in
the wild?

\item \textbf{Answer 1 (\cite[Example 4.10]{Grinbe20}).} Let $A$ be an affine
space over $\mathbb{R}$. Fix a finite subset $E$ of $A$. For any $F\subseteq
E$, we define%
\[
\operatorname*{Shade}F=\left\{  e\in E\ \mid\ e\text{ is \textbf{not} a
nontrivial convex combination of }F\right\}  .
\]
(A convex combination is said to be \textit{nontrivial} if all coefficients
are $<1$.)

Then, this map $\operatorname*{Shade}:\mathcal{P}\left(  E\right)
\rightarrow\mathcal{P}\left(  E\right)  $ is a shade map.

\item \textbf{Answer 2 (\cite[Theorem 4.18]{Grinbe20}).} Each antimatroid (a
type of greedoids, a variation on the concept of matroids) produces a shade map.

\item Other answers? Can you get shade maps from matroids? spanning trees? lattices?

\item \textbf{Remark (\cite[Theorem 4.33]{Grinbe20}).} Shade maps on $E$ are
in bijection with the partitions of the Boolean lattice $\mathcal{B}\left(
E\right)  $ into intervals.
\end{itemize}

\subsection{The topological viewpoint}

\begin{itemize}
\item Now let us return to the case of a graph $\Gamma=\left(  V,E\right)  $.
Fix a subset $G$ of $E$, and let
\begin{align*}
\mathcal{A}  &  =\left\{  F\subseteq E\ \mid\ G\not \subseteq
\operatorname*{Shade}F\right\} \\
&  =\left\{  F\subseteq E\ \mid\ \text{not every edge in }G\text{ is infected
by }F\right\}
\end{align*}
as in the proof above.

\item This $\mathcal{A}$ is clearly a simplicial complex on ground set $E$.

\item \textbf{Theorem (G., 2020 (\cite[Theorem 5.5]{Grinbe20})).} This
simplicial complex has a Morse matching (i.e., an acyclic partial matching)
with no unmatched faces. Thus, it is contractible.

\item \textbf{Proof idea.} Argue that the sign-reversing involution above is a
Morse matching.
\end{itemize}

\subsection{The Alexander dual}

\begin{itemize}
\item The complex%
\[
\mathcal{A}=\left\{  F\subseteq E\ \mid\ G\not \subseteq \operatorname*{Shade}%
F\right\}
\]
is not the only simplicial complex we can obtain from our setup. There is also%
\[
\mathcal{A}^{\ast}=\left\{  F\subseteq E\ \mid\ G\subseteq
\operatorname*{Shade}\left(  E\setminus F\right)  \right\}  .
\]


\item More generally, if $\left(  S,\Delta\right)  $ is any simplicial
complex, then we can define a new simplicial complex $\left(  S,\Delta^{\ast
}\right)  $, where%
\begin{align*}
\Delta^{\ast}  &  :=\left\{  I\subseteq S\ \mid\ S\setminus I\notin%
\Delta\right\} \\
&  =\left\{  \text{the complements of the non-faces of }\Delta\right\}  .
\end{align*}
This $\left(  S,\Delta^{\ast}\right)  $ is called the \textit{Alexander dual}
of $\left(  S,\Delta\right)  $.

\item The homologies of $\left(  S,\Delta^{\ast}\right)  $ and $\left(
S,\Delta\right)  $ are isomorphic (folklore -- see, e.g., \cite{BjoTan09});
thus the Euler characteristics agree up to sign.

But the homotopy types are not in general equivalent! Nor is the existence of
a Morse matching with good properties.

\item Thus, for any homotopy type question we can answer, we can state an
analogous one for its dual.

\item \textbf{Question.} What is the homotopy type of the $\mathcal{A}^{\ast}$ above?
\end{itemize}

\subsection{Multi-shades?}

\begin{itemize}
\item I can't help spreading yet another open question that essentially comes
from Dorpalen-Barry et al. \cite[Conjecture 9.1]{DHLetc19}.

\item Return to the setup of a graph $\Gamma=\left(  V,E\right)  $, but don't
fix the vertex $v$ this time.

\item Rename $\operatorname*{Shade}F$ as $\operatorname*{Shade}\nolimits_{v}F$
to stress its dependence on $v$.

\item For any subset $U\subseteq V$, define the simplicial complex%
\[
\mathcal{A}_{U}:=\left\{  F\subseteq E\ \mid\ G\not \subseteq
\operatorname*{Shade}\nolimits_{v}F\text{ for some }v\in U\right\}  .
\]


\item \textbf{Question:} What can we say about the homotopy and discrete Morse
theory of $\mathcal{A}_{U}$ ? What about its Alexander dual?

\item An optimistic yet reasonable expectation would be: a Morse matching
whose unmatched faces all have the same size. (Thus, $\mathcal{A}_{U}$ should
be homotopy-equivalent to a bouquet of spheres.)

\item \textbf{Update:} I am skeptical about the proof given in
\href{https://arxiv.org/abs/2203.12525v2}{arXiv:2203.12525v2} (but I might be
misunderstanding it).
\end{itemize}

\section{Bonus: Path-free and path-missing complexes}

\begin{itemize}
\item This is \textbf{joint work with Lukas Katth\"{a}n and Joel Brewster
Lewis} \cite{GrKaLe21}.

\item Fix a \textbf{directed} graph $G=\left(  V,E\right)  $ and two vertices
$s$ and $t$. We define the two simplicial complexes%
\begin{align*}
\mathcal{PF}\left(  G\right)   &  =\left\{  F\subseteq E\ \mid\ \text{there is
no }F\text{-path from }s\text{ to }t\right\} \\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{the \textit{\textquotedblleft
path-free\textquotedblright\ complex} of }G\right)
\end{align*}
and%
\begin{align*}
\mathcal{PM}\left(  G\right)   &  =\left\{  F\subseteq E\ \mid\ \text{there is
an }\left(  E\setminus F\right)  \text{-path from }s\text{ to }t\right\} \\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{the \textit{\textquotedblleft
path-missing\textquotedblright\ complex} of }G\right)  .
\end{align*}
(These are Alexander duals of each other.)

\item \textbf{Example:} Let $G$ be the following directed graph:
\[
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=3cm, thick,main node/.style={circle,fill=blue!20,draw}]
\node[main node] (1) {$s$};
\node[main node] (2) [above right of=1] {$p$};
\node[main node] (3) [below right of=1] {$q$};
\node[main node] (4) [right of=2] {$r$};
\node[main node] (5) [below right of=4] {$t$};
\path[every node/.style={font=\sffamily\small}] (1) edge node {$a$} (2) (2) edge node {$b$} (4) (4) edge node {$c$} (5) (1) edge node[below left] {$d$} (3) (3) edge node[below right] {$e$} (5) (3) edge node {$f$} (2) (4) edge node {$g$} (3);
\end{tikzpicture}.
\]
Then:

\begin{itemize}
\item The faces of the simplicial complex $\mathcal{PF}(G)$ are the sets
\[
\left\{  b,c,e,f,g\right\}  ,\ \left\{  a,c,e,f,g\right\}  ,\ \left\{
b,c,d,g\right\}  ,\ \left\{  a,c,d,f,g\right\}  ,\ \left\{  a,b,e,f\right\}
,\ \left\{  a,b,d,f,g\right\}
\]
as well as all their subsets.

\item The faces of the simplicial complex $\mathcal{PM}(G)$ are the sets
\[
\left\{  d,e,f,g\right\}  ,\ \left\{  c,d,f\right\}  ,\ \left\{
a,b,c,f,g\right\}  ,\ \left\{  a,e,g\right\}
\]
as well as all their subsets.
\end{itemize}

\item \textbf{Theorem (G., Katth\"{a}n, Lewis, 2021 (\cite{GrKaLe21})).}
Assume that $s\neq t$ and $E\neq\varnothing$ (the other cases are trivial).
Then, both complexes $\mathcal{PF}\left(  G\right)  $ and $\mathcal{PM}\left(
G\right)  $ are contractible or homotopy-equivalent to spheres. The dimensions
of the spheres can be determined explicitly. The complexes are contractible if
and only if $G$ has a useless edge (i.e., an edge that appears in no path from
$s$ to $t$) or a (directed) cycle.

\item \textbf{Theorem (G., Katth\"{a}n, Lewis, 2024 (\cite{GrKaLe21})).} Both
complexes $\mathcal{PF}\left(  G\right)  $ and $\mathcal{PM}\left(  G\right)
$ have Morse matchings with at most one unmatched face.

\item The proofs use (fairly intricate) deletion/contraction arguments.

\item \textbf{Question.} Is there a good non-recursive description of these
Morse matchings?
\end{itemize}

\subsection*{Acknowledgments}

Thanks to

\begin{itemize}
\item \textbf{Lukas Katth\"{a}n}, who showed me how simple discrete Morse
theory is;

\item \textbf{Anders Bj\"{o}rner, Galen Dorpalen-Barry, Dmitry
Feichtner-Kozlov, Patricia Hersh, Joel Brewster Lewis, Vic Reiner, Tom Roby
}and\textbf{ Richard Stanley} for insightful conversations;

\item \textbf{an anonymous referee} for one of the most useful reports I have
ever gotten (within just 2 weeks), greatly simplifying one of my proofs;

\item the \textbf{Mathematisches Forschungsinstitut Oberwolfach} and
specifically the programme \textquotedblleft Oberwolfach Leibniz
Fellows\textquotedblright\ for its hospitality (in 2020, of all times);

\item \textbf{you} for your patience!
\end{itemize}

\begin{thebibliography}{999999999}                                                                                        %


\bibitem[Alikha12]{Alikha12}%
\href{https://doi.org/10.1007/s00373-012-1211-x}{Saeid Alikhani, \textit{The
Domination Polynomial of a Graph at }$-1$, Graphs and Combinatorics
\textbf{29} (2013), pp. 1175--1181, doi:10.1007/s00373-012-1211-x}.

\bibitem[BenQui08]{BenQui08}%
\href{https://scholarship.claremont.edu/cgi/viewcontent.cgi?referer=&httpsredir=1&article=1581&context=hmc_fac_pub}{Arthur
T. Benjamin and Jennifer J. Quinn, \textit{An Alternate Approach to
Alternating Sums: A Method to DIE for}, The College Mathematics Journal,
Volume 39, Number 3, May 2008, pp. 191-202(12).}

\bibitem[BjoTan09]{BjoTan09}%
\href{https://doi.org/10.1007/s00454-008-9102-x}{Anders Bj\"{o}rner, Martin
Tancer, \textit{Combinatorial Alexander Duality -- A Short and Elementary
Proof}, Discrete Comput Geom (2009) 42, pp. 586--593.}

\bibitem[Brouwe09]{Brouwe09}A. E. Brouwer, \textit{The number of dominating
sets of a finite graph is odd}, 2 June 2009.\newline\url{https://www.win.tue.nl/~aeb/preprints/domin2.pdf}

\bibitem[BrCsSc09]{BrCsSc09}A. E. Brouwer, P. Csorba \& A. Schrijver,
\textit{The number of dominating sets of a finite graph is odd}, 2 June
2009.\newline\url{https://www.win.tue.nl/~aeb/preprints/domin4a.pdf}

\bibitem[CSSS18]{CSSS18}\href{https://doi.org/10.1007/s11856-020-2034-8}{Maria
Chudnovsky, Alex Scott, Paul Seymour, Sophie Spirkl, \textit{Proof of the
Kalai-Meshulam conjecture}, Israel Journal of Mathematics volume \textbf{238}
(2020), pp. 639--661}. \newline See
\url{https://uwspace.uwaterloo.ca/handle/10012/18516} for a preprint.

\bibitem[DHLetc19]{DHLetc19}\href{https://arxiv.org/abs/1905.11330v5}{Galen
Dorpalen-Barry, Cyrus Hettle, David C. Livingston, Jeremy L. Martin, George
Nasr, Julianne Vega, Hays Whitlatch, \textit{A positivity phenomenon in
Elser's Gaussian-cluster percolation model}, arXiv:1905.11330v5},
\href{https://doi.org/10.1016/j.jcta.2020.105364}{Journal of Combinatorial
Theory, Series A, \textbf{179}:105364, April 2021,
doi:10.1016/j.jcta.2020.105364}.

\bibitem[EhrHet06]{EhrHet06}%
\href{https://doi.org/10.1016/j.ejc.2005.04.010}{Richard Ehrenborg, G\'{a}bor
Hetyei, \textit{The topology of the independence complex}, European Journal of
Combinatorics \textbf{27} (2006), pp. 906--923}.

\bibitem[Elser84]{Elser84}%
\href{https://doi.org/10.1088/0305-4470/17/7/019}{Veit Elser,
\textit{Gaussian-cluster models of percolation and self-avoiding walks}, J.
Phys. A: Math. Gen. \textbf{17} (1984), pp. 1515--1523}.

\bibitem[Forman02]{Forman02}%
\href{https://www.emis.de/journals/SLC/wpapers/s48forman.html}{Robin Forman,
\textit{A User's Guide to discrete Morse theory}, S\'{e}minaire Lotharingien
de Combinatoire \textbf{48} (2002), Article B48c}.

\bibitem[Grinbe17]{nogra}Darij Grinberg, \textit{Notes on graph theory}, 10
January 2019.\newline\url{http://www.cip.ifi.lmu.de/~grinberg/t/17s/}

\bibitem[Grinbe20]{Grinbe20}%
\href{http://www.cip.ifi.lmu.de/~grinberg/algebra/elsersum-long.pdf}{Darij
Grinberg, \textit{The Elser nuclei sum revisited}, detailed version}. Also
available as an ancillary file at
\href{https://arxiv.org/abs/2009.11527v8}{arXiv:2009.11527v8}.

\bibitem[GrKaLe21]{GrKaLe21}\href{https://arxiv.org/abs/2102.07894v3}{Darij
Grinberg, Lukas Katth\"{a}n, Joel Brewster Lewis, \textit{The path-missing and
path-free complexes of a directed graph}, arXiv:2102.0784v3}.

\bibitem[HeiTit17]{HeiTit17}\href{https://arxiv.org/abs/1701.03453v1}{Irene
Heinrich, Peter Tittmann, \textit{Counting Dominating Sets of Graphs},
arXiv:1701.03453v1}.

\bibitem[Kim21]{Kim21}\href{https://arxiv.org/abs/2101.07131v3}{Jinha Kim,
\textit{The homotopy type of the independence complex of graphs with no
induced cycle of length divisible by 3}, arXiv:2101.07131v3}.

\bibitem[Kozlov20]{Kozlov20}\href{https://bookstore.ams.org/gsm-207}{Dmitry N.
Kozlov, \textit{Organized Collapse: An Introduction to Discrete Morse Theory},
Graduate Studies in Mathematics \textbf{207}, AMS 2020}.\newline See
\url{https://dfklab.com/books/} for a preprint.

\bibitem[Sagan20]{Sagan20}\href{https://bookstore.ams.org/gsm-210/}{Bruce
Sagan, \textit{Combinatorics: The Art of Counting}, Graduate Studies in
Mathematics \textbf{210}, AMS 2020}.\newline See
\url{https://users.math.msu.edu/users/bsagan/Books/Aoc/final.pdf} for a preprint.

\bibitem[Stanle11]{Stanley-EC1}Richard P. Stanley, \textit{Enumerative
Combinatorics, volume 1}, 2nd edition, version of 15 July 2011.\newline%
\url{http://math.mit.edu/~rstan/ec/} .\newline See
\url{http://math.mit.edu/~rstan/ec/} for errata.

\bibitem[Striker15]{Striker15}%
\href{https://arxiv.org/abs/1503.08898v2}{Jessica Striker, \textit{The toggle
group, homomesy, and the Razumov-Stroganov correspondence},
arXiv:1503.08898v2}, Electron. J. Combin. \textbf{22} (2015) no. 2.

\bibitem[ZhaWu20]{ZhaWu20}\href{https://arxiv.org/abs/2011.10939v3}{Hehui Wu,
Wentao Zhang, \textit{The Betti Number of the Independence Complex of Ternary
Graphs}, arXiv:2011.10939v3}.
\end{thebibliography}


\end{document}