\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=Sunday, October 25, 2020 17:09:13}
%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{\PER}{\operatorname{PER}}
\newcommand{\PD}{\operatorname{PD}}
\newcommand{\proj}{\operatorname{proj}}
\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}
\renewcommand{\subset}{\subseteq}
\iffalse
\NOEXPAND{\timesu}{\mathbin{\underline{\times}}}
\fi
\newcommand{\nuo}{\nu^{\circ}}
\newtheoremstyle{plainsl}
{8pt plus 2pt minus 4pt}
{8pt plus 2pt minus 4pt}
{\slshape}
{0pt}
{\bfseries}
{.}
{5pt plus 1pt minus 1pt}
{}
\theoremstyle{plainsl}
\ihead{The Elser nuclei sum revisited}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\title{The Elser nuclei sum revisited}
\author{Darij Grinberg\thanks{Drexel University, Korman Center, Room 291, 15 S 33rd
Street, Philadelphia PA, 19104, USA}}
\date{version 1.1 (corrected version of arXiv:2009.11527v1), \today}
\maketitle

\begin{abstract}
\textbf{Abstract.} Fix a finite undirected graph $G$ and a vertex $v$ of $G$.
Let $E$ be the set of edges of $G$; assume that $E\neq\varnothing$. We call a
subset $F$ of $E$ \textit{pandemic} if each edge of $G$ has at least one
endpoint that can be connected to $v$ by an $F$-path (i.e., a path using edges
from $F$ only). In 1984, Elser showed that the sum of $\left(  -1\right)
^{\left\vert F\right\vert }$ over all pandemic subsets $F$ of $E$ is $0$. We
give a simpler proof and discuss variants and generalizations.

\end{abstract}

\section*{****}

In \cite{Elser84}, Veit Elser studied the probabilities of clusters forming
when $n$ points are sampled randomly in a $d$-dimensional volume. In the
process, he found a purely graph-theoretical lemma \cite[Lemma 1]{Elser84},
which served a crucial role in his work. For decades, the lemma stayed hidden
from the eyes of combinatorialists in a physics journal, until it resurfaced
in recent work \cite{DHLetc19} by Dorpalen-Barry, Hettle, Livingston, Martin,
Nasr, Vega and Whitlatch. In this note, I will show a simpler proof of the
lemma that illustrates the use of the inclusion-exclusion principle and also
suggests a mysterious generalization.

\section{Elser's result}

Let us first introduce our setting, which is slightly more general (and
perhaps also simpler) than that used in \cite{Elser84}.

We fix an arbitrary graph $\Gamma$ with vertex set $V$ and edge set $E$. Here,
\textquotedblleft graph\textquotedblright\ means \textquotedblleft finite
undirected multigraph\textquotedblright\ -- i.e., it can have self-loops and
parallel edges, but it has finitely many vertices and edges, and its edges are undirected.

We fix a vertex $v\in V$.

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$.

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$. (The terminology is inspired by the idea of an infectious disease
starting in the vertex $v$ and being transmitted along edges.)\footnote{Note
that if an edge $e$ contains the vertex $v$, then any subset $F$ of $E$ (even
the empty one) infects $e$, since there is a trivial (edgeless) $F$-path from
$v$ to $v$.}

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

\begin{example}
\label{exa.example1} Let $\Gamma$ be the following graph:%
\[%
%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
\]
(where the vertex $v$ is the vertex labelled $v$). Then, for example, the set
$\left\{  1,2\right\}  \subseteq E$ infects edges $1,2,3,6,8$ (but none of the
other edges). The set $\left\{  1,2,5\right\}  $ infects the same edges as
$\left\{  1,2\right\}  $ (indeed, the additional edge $5$ does not increase
its infectiousness, since it is not on any $\left\{  1,2,5\right\}  $-path
from $v$). The set $\left\{  1,2,3\right\}  $ infects every edge other than
$5$. The set $\left\{  1,2,3,4\right\}  $ infects each edge, and thus is pandemic.
\end{example}

Now, we can state our version of \cite[Lemma 1]{Elser84}:

\begin{theorem}
\label{thm.elser0}Assume that $E\neq\varnothing$. Then,%
\begin{equation}
\sum_{\substack{F\subseteq E\text{ is}\\\text{pandemic}}}\left(  -1\right)
^{\left\vert F\right\vert }=0. \label{eq.thm.elser0.eq}%
\end{equation}

\end{theorem}

\begin{example}
\label{exa.example2} Let $\Gamma$ be the following graph:%
\[%
%TCIMACRO{\TeXButton{C4 graph}{\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=2] (3) {$q$};
%\node[main node] [right of=1] (4) {$w$};
%\path[every node/.style={font=\sffamily\small}] (1) edge node {$1$}
%(2) (2) edge node {$2$} (3) (3) edge node {$3$} (4) (4) edge node {$4$} (1);
%\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=2] (3) {$q$};
\node[main node] [right of=1] (4) {$w$};
\path[every node/.style={font=\sffamily\small}] (1) edge node {$1$}
(2) (2) edge node {$2$} (3) (3) edge node {$3$} (4) (4) edge node {$4$} (1);
\end{tikzpicture}%
%EndExpansion
\]
(where the vertex $v$ is the vertex labelled $v$). Then, the pandemic subsets
of $E$ are the sets%
\[
\left\{  1,2\right\}  ,\ \ \left\{  1,4\right\}  ,\ \ \left\{  3,4\right\}
,\ \ \left\{  1,2,3\right\}  ,\ \ \left\{  1,3,4\right\}  ,\ \ \left\{
1,2,4\right\}  ,\ \ \left\{  2,3,4\right\}  ,\ \ \left\{  1,2,3,4\right\}  .
\]
The sizes of these subsets are $2,2,2,3,3,3,3,4$, respectively. Hence,
(\ref{eq.thm.elser0.eq}) says that%
\[
\left(  -1\right)  ^{2}+\left(  -1\right)  ^{2}+\left(  -1\right)
^{2}+\left(  -1\right)  ^{3}+\left(  -1\right)  ^{3}+\left(  -1\right)
^{3}+\left(  -1\right)  ^{3}+\left(  -1\right)  ^{4}=0.
\]

\end{example}

We note that the equality (\ref{eq.thm.elser0.eq}) can be restated as
\textquotedblleft there are equally many pandemic subsets $F\subseteq E$ of
even size and pandemic subsets $F\subseteq E$ of odd size\textquotedblright.
Thus, in particular, the number of all pandemic subsets $F$ of $E$ is even
(when $E\neq\varnothing$).

\begin{remark}
Theorem \ref{thm.elser0} is a bit more general than \cite[Lemma 1]{Elser84}.
To see why, we assume that the graph $\Gamma$ is connected and simple (i.e.,
has no self-loops and parallel edges). Then, a \textit{nucleus} is defined in
\cite{Elser84} as a subgraph $N$ of $\Gamma$ with the properties that

\begin{enumerate}
\item the subgraph $N$ is connected, and

\item each edge of $\Gamma$ has at least one endpoint in $N$.
\end{enumerate}

\noindent Given a subgraph $N$ of $\Gamma$, we let $\operatorname*{E}\left(
N\right)  $ denote the set of all edges of $N$. Now, \cite[Lemma 1]{Elser84}
claims that if $E\neq\varnothing$, then%
\[
\sum_{\substack{N\text{ is a nucleus}\\\text{containing }v}}\left(  -1\right)
^{\left\vert \operatorname*{E}\left(  N\right)  \right\vert }=0.
\]


But this is equivalent to (\ref{eq.thm.elser0.eq}), because there is a
bijection%
\begin{align*}
\left\{  \text{nuclei containing }v\right\}   &  \rightarrow\left\{
\text{pandemic subsets }F\subseteq E\right\}  ,\\
N  &  \mapsto\operatorname*{E}\left(  N\right)  .
\end{align*}
We leave it to the reader to check this in detail; what needs to be checked
are the following three statements:

\begin{itemize}
\item If $N$ is a nucleus containing $v$, then $\operatorname*{E}\left(
N\right)  $ is a pandemic subset of $E$.

\item Every nucleus $N$ containing $v$ is uniquely determined by the set
$\operatorname*{E}\left(  N\right)  $. (Indeed, since a nucleus has to be
connected, each of its vertices must be an endpoint of one of its edges,
unless its only vertex is $v$.)

\item If $F$ is a pandemic subset of $E$, then there is a nucleus $N$
containing $v$ such that $\operatorname*{E}\left(  N\right)  =F$. (Indeed, $N$
can be defined as the subgraph of $\Gamma$ whose vertices are the endpoints of
all edges in $F$ as well as the vertex $v$, and whose edges are the edges in
$F$. To see that this subgraph $N$ is connected, it suffices to argue that
each of its vertices has a path to $v$; but this follows from the definition
of \textquotedblleft pandemic\textquotedblright, since each vertex of $N$
other than $v$ belongs to at least one edge in $F$.)
\end{itemize}

Thus, Theorem \ref{thm.elser0} is equivalent to \cite[Lemma 1]{Elser84} in the
case when $\Gamma$ is connected and simple.
\end{remark}

\begin{remark}
It might appear more natural to talk about a subset $F\subseteq E$ infecting a
vertex rather than an edge. (Namely, we can say that $F$ infects a vertex $w$
if there is an $F$-path from $v$ to $w$.) However, the analogue of Theorem
\ref{thm.elser0} in which pandemicity is defined via infecting all vertices is
not true. The graph of Example \ref{exa.example2} provides a counterexample.
\end{remark}

\section{The proof}

Our proof of Theorem \ref{thm.elser0} will rest on a few lemmas. The first is
one of the simplest facts in enumerative combinatorics:

\begin{lemma}
\label{lem.toggle}Let $U$ be a finite set with $U\neq\varnothing$. Then,%
\[
\sum_{F\subseteq U}\left(  -1\right)  ^{\left\vert F\right\vert }=0.
\]

\end{lemma}

We shall prove Lemma \ref{lem.toggle} via a more general result, which we will
also use. To state it, we need a definition:

\begin{definition}
Let $U$ be a set. Let $\mathcal{S}$ be a set of subsets of $U$. Let $u\in U$.
We say that $u$ is \emph{toggleable} in $\mathcal{S}$ if the following two
statements hold:

\begin{itemize}
\item For every $F\in\mathcal{S}$ satisfying $u\notin F$, we have
$F\cup\left\{  u\right\}  \in\mathcal{S}$.

\item For every $F\in\mathcal{S}$ satisfying $u\in F$, we have $F\setminus
\left\{  u\right\}  \in\mathcal{S}$.
\end{itemize}
\end{definition}

Now, we can generalize Lemma \ref{lem.toggle} as follows:

\begin{lemma}
\label{lem.toggle-gen}Let $U$ be a finite set. Let $\mathcal{S}$ be a set of
subsets of $U$. Let $u\in U$ be toggleable in $\mathcal{S}$. Then,%
\[
\sum_{F\in\mathcal{S}}\left(  -1\right)  ^{\left\vert F\right\vert }=0.
\]

\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.toggle-gen}.]For every $F\in\mathcal{S}$ satisfying
$u\notin F$, we have $F\cup\left\{  u\right\}  \in\mathcal{S}$ (since $u$ is
toggleable in $\mathcal{S}$) and $u\in F\cup\left\{  u\right\}  $. Hence, the
map%
\begin{align*}
\Phi:\left\{  F\in\mathcal{S}\ \mid\ u\notin F\right\}   &  \rightarrow
\left\{  F\in\mathcal{S}\ \mid\ u\in F\right\}  ,\\
F  &  \mapsto F\cup\left\{  u\right\}
\end{align*}
is well-defined. Consider this map $\Phi$.

For every $F\in\mathcal{S}$ satisfying $u\in F$, we have $F\setminus\left\{
u\right\}  \in\mathcal{S}$ (since $u$ is toggleable in $\mathcal{S}$) and
$u\notin F\setminus\left\{  u\right\}  $. Hence, the map%
\begin{align*}
\Psi:\left\{  F\in\mathcal{S}\ \mid\ u\in F\right\}   &  \rightarrow\left\{
F\in\mathcal{S}\ \mid\ u\notin F\right\}  ,\\
F  &  \mapsto F\setminus\left\{  u\right\}
\end{align*}
is well-defined. Consider this map $\Psi$.

The maps $\Phi$ and $\Psi$ we just defined are clearly mutually inverse. Thus,
they are bijections. Hence, in particular, $\Psi$ is a bijection. Thus, we can
substitute $\Psi\left(  F\right)  $ for $F$ in the sum $\sum_{\substack{F\in
\mathcal{S};\\u\notin F}}\left(  -1\right)  ^{\left\vert F\right\vert }$. We
thus obtain%
\begin{align*}
\sum_{\substack{F\in\mathcal{S};\\u\notin F}}\left(  -1\right)  ^{\left\vert
F\right\vert }  &  =\sum_{\substack{F\in\mathcal{S};\\u\in F}%
}\underbrace{\left(  -1\right)  ^{\left\vert \Psi\left(  F\right)  \right\vert
}}_{\substack{=\left(  -1\right)  ^{\left\vert F\setminus\left\{  u\right\}
\right\vert }\\\text{(since }\Psi\left(  F\right)  =F\setminus\left\{
u\right\}  \\\text{(by the definition of }\Psi\text{))}}}=\sum_{\substack{F\in
\mathcal{S};\\u\in F}}\underbrace{\left(  -1\right)  ^{\left\vert
F\setminus\left\{  u\right\}  \right\vert }}_{\substack{=\left(  -1\right)
^{\left\vert F\right\vert -1}\\\text{(since }\left\vert F\setminus\left\{
u\right\}  \right\vert =\left\vert F\right\vert -1\\\text{(because }u\in
F\text{))}}}\\
&  =\sum_{\substack{F\in\mathcal{S};\\u\in F}}\underbrace{\left(  -1\right)
^{\left\vert F\right\vert -1}}_{=-\left(  -1\right)  ^{\left\vert F\right\vert
}}=-\sum_{\substack{F\in\mathcal{S};\\u\in F}}\left(  -1\right)  ^{\left\vert
F\right\vert }.
\end{align*}
But each $F\in\mathcal{S}$ satisfies either $u\in F$ or $u\notin F$ (but not
both). Hence,%
\[
\sum_{F\in\mathcal{S}}\left(  -1\right)  ^{\left\vert F\right\vert }%
=\sum_{\substack{F\in\mathcal{S};\\u\in F}}\left(  -1\right)  ^{\left\vert
F\right\vert }+\underbrace{\sum_{\substack{F\in\mathcal{S};\\u\notin
F}}\left(  -1\right)  ^{\left\vert F\right\vert }}_{=-\sum_{\substack{F\in
\mathcal{S};\\u\in F}}\left(  -1\right)  ^{\left\vert F\right\vert }}%
=\sum_{\substack{F\in\mathcal{S};\\u\in F}}\left(  -1\right)  ^{\left\vert
F\right\vert }-\sum_{\substack{F\in\mathcal{S};\\u\in F}}\left(  -1\right)
^{\left\vert F\right\vert }=0.
\]
This proves Lemma \ref{lem.toggle-gen}.
\end{proof}

\begin{proof}
[Proof of Lemma \ref{lem.toggle}.]We have $U\neq\varnothing$; hence, there
exists some $u\in U$. Consider this $u$.

Let $\mathcal{S}$ be the entire power set of $U$. Then, $u$ is toggleable in
$\mathcal{S}$ (for obvious reasons). Hence, Lemma \ref{lem.toggle-gen} yields
$\sum_{F\in\mathcal{S}}\left(  -1\right)  ^{\left\vert F\right\vert }=0$. But
$\sum_{F\in\mathcal{S}}\left(  -1\right)  ^{\left\vert F\right\vert }%
=\sum_{F\subseteq U}\left(  -1\right)  ^{\left\vert F\right\vert }$ (since
$\mathcal{S}$ is the entire power set of $U$). Comparing the last two
equalities, we obtain $\sum_{F\subseteq U}\left(  -1\right)  ^{\left\vert
F\right\vert }=0$. This proves Lemma \ref{lem.toggle}.
\end{proof}

Theorem \ref{thm.elser0} is about a sum over all pandemic subsets of $E$ --
that is, all subsets of $E$ that infect every edge in $E$. We shall consider
this sum as part of a family of sums $A\left(  P\right)  $, indexed over all
subsets $P$ of $E$:

\begin{definition}
\label{def.APNP}For any subset $P$ of $E$, we define two subsets%
\[
A\left(  P\right)  =\left\{  F\subseteq E\ \mid\ F\text{ infects each }p\in
P\right\}
\]
and%
\[
N\left(  P\right)  =\left\{  F\subseteq E\ \mid\ F\text{ infects no }p\in
P\right\}
\]
of the power set of $E$.
\end{definition}

\begin{lemma}
\label{lem.APNP}Let $G$ be a subset of $E$. Then,%
\[
\sum_{F\in A\left(  G\right)  }\left(  -1\right)  ^{\left\vert F\right\vert
}=\sum_{P\subseteq G}\left(  -1\right)  ^{\left\vert P\right\vert }\sum_{F\in
N\left(  P\right)  }\left(  -1\right)  ^{\left\vert F\right\vert }.
\]

\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.APNP}.]For any subset $F$ of $E$, we let%
\[
X\left(  F\right)  =\left\{  e\in G\ \mid\ F\text{ does not infect }e\right\}
.
\]
This $X\left(  F\right)  $ is always a subset of $G$.

For any subset $F\subseteq E$ and every set $P$, we have the following chain
of equivalences:%
\begin{align*}
&  \ \left(  P\subseteq X\left(  F\right)  \right) \\
&  \Longleftrightarrow\ \left(  \text{each }p\in P\text{ belongs to }X\left(
F\right)  \right) \\
&  \Longleftrightarrow\ \left(  \text{each }p\in P\text{ is an }e\in G\text{
with the property that }F\text{ does not infect }e\right) \\
&  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left(  \text{by the definition of
}X\left(  F\right)  \right) \\
&  \Longleftrightarrow\ \left(  \text{each }p\in P\text{ belongs to }G\text{
and has the property that }F\text{ does not infect }p\right) \\
&  \Longleftrightarrow\ \underbrace{\left(  \text{each }p\in P\text{ belongs
to }G\right)  }_{\Longleftrightarrow\ \left(  P\subseteq G\right)  }%
\wedge\left(  F\text{ infects no }p\in P\right) \\
&  \Longleftrightarrow\ \left(  P\subseteq G\right)  \wedge\left(  F\text{
infects no }p\in P\right)  .
\end{align*}
Thus, for any subset $F\subseteq E$, we have the following equality of
summation signs:%
\begin{equation}
\sum_{P\subseteq X\left(  F\right)  }=\sum_{\substack{P\subseteq G;\\F\text{
infects no }p\in P}}\ . \label{pf.lem.APNP.sum=sum1}%
\end{equation}


Moreover, for any subset $F\subseteq E$, we have the following chain of
equivalences:%
\begin{align}
&  \ \left(  X\left(  F\right)  =\varnothing\right) \nonumber\\
&  \Longleftrightarrow\ \left(  \text{there exists no element of }X\left(
F\right)  \right) \nonumber\\
&  \Longleftrightarrow\ \left(  \text{there exists no }e\in G\text{ such that
}F\text{ does not infect }e\right) \nonumber\\
&  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left(  \text{by the definition of
}X\left(  F\right)  \right) \nonumber\\
&  \Longleftrightarrow\ \left(  F\text{ infects each }e\in G\right)
\nonumber\\
&  \Longleftrightarrow\ \left(  F\text{ infects each }p\in G\right)
\nonumber\\
&  \Longleftrightarrow\ \left(  F\in A\left(  G\right)  \right)
\ \ \ \ \ \ \ \ \ \ \left(  \text{by the definition of }A\left(  G\right)
\right)  . \label{pf.lem.APNP.sum=sum2equiv}%
\end{align}


Now, we have%
\begin{align*}
&  \sum_{P\subseteq G}\left(  -1\right)  ^{\left\vert P\right\vert
}\underbrace{\sum_{F\in N\left(  P\right)  }}_{\substack{=\sum
_{\substack{F\subseteq E;\\F\text{ infects no }p\in P}}\\\text{(by the
definition of }N\left(  P\right)  \text{)}}}\left(  -1\right)  ^{\left\vert
F\right\vert }\\
&  =\sum_{P\subseteq G}\left(  -1\right)  ^{\left\vert P\right\vert }%
\sum_{\substack{F\subseteq E;\\F\text{ infects no }p\in P}}\left(  -1\right)
^{\left\vert F\right\vert }=\underbrace{\sum_{P\subseteq G}\sum
_{\substack{F\subseteq E;\\F\text{ infects no }p\in P}}}_{=\sum_{F\subseteq
E}\sum_{\substack{P\subseteq G;\\F\text{ infects no }p\in P}}}\left(
-1\right)  ^{\left\vert P\right\vert }\left(  -1\right)  ^{\left\vert
F\right\vert }\\
&  =\sum_{F\subseteq E}\underbrace{\sum_{\substack{P\subseteq G;\\F\text{
infects no }p\in P}}}_{\substack{=\sum_{P\subseteq X\left(  F\right)
}\\\text{(by (\ref{pf.lem.APNP.sum=sum1}))}}}\left(  -1\right)  ^{\left\vert
P\right\vert }\left(  -1\right)  ^{\left\vert F\right\vert }=\sum_{F\subseteq
E}\ \ \sum_{P\subseteq X\left(  F\right)  }\left(  -1\right)  ^{\left\vert
P\right\vert }\left(  -1\right)  ^{\left\vert F\right\vert }\\
&  =\sum_{Q\subseteq E}\ \ \sum_{F\subseteq X\left(  Q\right)  }\left(
-1\right)  ^{\left\vert F\right\vert }\left(  -1\right)  ^{\left\vert
Q\right\vert }\ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{here, we renamed the}\\
\text{summation indices }F\text{ and }P\\
\text{as }Q\text{ and }F\text{, respectively}%
\end{array}
\right) \\
&  =\sum_{\substack{Q\subseteq E;\\X\left(  Q\right)  =\varnothing
}}\underbrace{\sum_{F\subseteq X\left(  Q\right)  }\left(  -1\right)
^{\left\vert F\right\vert }}_{\substack{=\sum_{F\subseteq\varnothing}\left(
-1\right)  ^{\left\vert F\right\vert }\\\text{(since }X\left(  Q\right)
=\varnothing\text{)}}}\left(  -1\right)  ^{\left\vert Q\right\vert }%
+\sum_{\substack{Q\subseteq E;\\X\left(  Q\right)  \neq\varnothing
}}\underbrace{\sum_{F\subseteq X\left(  Q\right)  }\left(  -1\right)
^{\left\vert F\right\vert }}_{\substack{=0\\\text{(by Lemma \ref{lem.toggle}%
,}\\\text{applied to }U=X\left(  Q\right)  \text{)}}}\left(  -1\right)
^{\left\vert Q\right\vert }\\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{since each subset }Q\text{ of }E\text{ satisfies either }X\left(
Q\right)  =\varnothing\\
\text{or }X\left(  Q\right)  \neq\varnothing\text{ (but not both)}%
\end{array}
\right)
\end{align*}%
\begin{align*}
&  =\sum_{\substack{Q\subseteq E;\\X\left(  Q\right)  =\varnothing
}}\underbrace{\sum_{F\subseteq\varnothing}\left(  -1\right)  ^{\left\vert
F\right\vert }}_{=\left(  -1\right)  ^{\left\vert \varnothing\right\vert
}=\left(  -1\right)  ^{0}=1}\left(  -1\right)  ^{\left\vert Q\right\vert
}+\underbrace{\sum_{\substack{Q\subseteq E;\\X\left(  Q\right)  \neq
\varnothing}}0\left(  -1\right)  ^{\left\vert Q\right\vert }}_{=0}\\
&  =\sum_{\substack{Q\subseteq E;\\X\left(  Q\right)  =\varnothing}}\left(
-1\right)  ^{\left\vert Q\right\vert }=\underbrace{\sum_{\substack{F\subseteq
E;\\X\left(  F\right)  =\varnothing}}}_{\substack{=\sum_{\substack{F\subseteq
E;\\F\in A\left(  G\right)  }}\\\text{(by (\ref{pf.lem.APNP.sum=sum2equiv}))}%
}}\left(  -1\right)  ^{\left\vert F\right\vert }=\underbrace{\sum
_{\substack{F\subseteq E;\\F\in A\left(  G\right)  }}}_{\substack{=\sum_{F\in
A\left(  G\right)  }\\\text{(since}\\\text{every }F\in A\left(  G\right)
\\\text{satisfies }F\subseteq E\text{)}}}\left(  -1\right)  ^{\left\vert
F\right\vert }=\sum_{F\in A\left(  G\right)  }\left(  -1\right)  ^{\left\vert
F\right\vert }.
\end{align*}
This proves Lemma \ref{lem.APNP}.
\end{proof}

So far, we have used nothing about graphs and infection; Lemma \ref{lem.APNP}
does not depend on any property of the \textquotedblleft
infects\textquotedblright\ relation other than it being a relation between
subsets of $E$ and elements of $E$. Actually, Lemma \ref{lem.APNP} can be
viewed as an instance of the Principle of Inclusion and Exclusion, or of
M\"{o}bius inversion of the Boolean lattice; a reader familiar with these
results will easily find a way to derive it from them.\footnote{See
\cite{Rota64}, \cite[Sections 2.1--2.3]{Sagan19}, \cite[Chapter 2]%
{Stanley-EC1}, \cite{BenQui08}, \cite[Chapter 5]{Aigner07} for various aspects
of this theory. For example, Lemma \ref{lem.APNP} can be obtained as a
particular case of \cite[Chapter 5, (16)]{Aigner07}.} We found it easier to
prove Lemma \ref{lem.APNP} from scratch, however, particularly since the main
auxiliary result (Lemma \ref{lem.toggle-gen}) will be needed again anyway.

The next lemma (which, unlike the previous ones, does rely on the actual
nature of \textquotedblleft infection\textquotedblright) shows that the sums
$\sum_{F\in N\left(  P\right)  }\left(  -1\right)  ^{\left\vert F\right\vert
}$ in Lemma \ref{lem.APNP} are almost always $0$:

\begin{lemma}
\label{lem.NP}We have the following:

\begin{enumerate}
\item[\textbf{(a)}] Every nonempty set $P$ of $E$ satisfies%
\[
\sum_{F\in N\left(  P\right)  }\left(  -1\right)  ^{\left\vert F\right\vert
}=0.
\]


\item[\textbf{(b)}] If $E\neq\varnothing$, then every subset $P$ of $E$
satisfies%
\[
\sum_{F\in N\left(  P\right)  }\left(  -1\right)  ^{\left\vert F\right\vert
}=0.
\]

\end{enumerate}
\end{lemma}

In order to prove this, we will need the following:

\begin{lemma}
\label{lem.NP-tog}Let $P$ be a subset of $E$. Let $u\in P$. Then, $u$ is
toggleable in $N\left(  P\right)  $.
\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.NP-tog}.]We must prove the following two claims:

\begin{statement}
\textit{Claim 1:} For every $F\in N\left(  P\right)  $ satisfying $u\notin F$,
we have $F\cup\left\{  u\right\}  \in N\left(  P\right)  $.
\end{statement}

\begin{statement}
\textit{Claim 2:} For every $F\in N\left(  P\right)  $ satisfying $u\in F$, we
have $F\setminus\left\{  u\right\}  \in N\left(  P\right)  $.
\end{statement}

[\textit{Proof of Claim 1:} Let $F\in N\left(  P\right)  $ satisfy $u\notin
F$. We must show that $F\cup\left\{  u\right\}  \in N\left(  P\right)  $.

We have $F\in N\left(  P\right)  $. In other words, $F$ is a subset of $E$
that infects no $p\in P$. Thus, $F\cup\left\{  u\right\}  $ is a subset of $E$
(since $F\subseteq E$ and $u\in P\subseteq E$).

Now we claim that $F\cup\left\{  u\right\}  $ infects no $p\in P$. Indeed,
assume the contrary. Then, $F\cup\left\{  u\right\}  $ infects some $p\in P$.
In other words, $F\cup\left\{  u\right\}  $ infects some $q\in P$. In other
words, there exists some $q\in P$ such that $F\cup\left\{  u\right\}  $
infects $q$. Consider this $q$. Note that $F$ does not infect $q$ (since $F$
infects no $p\in P$). In other words, there exists no $F$-path from $v$ to any
endpoint of $q$ (by the definition of \textquotedblleft
infects\textquotedblright).

We know that $F\cup\left\{  u\right\}  $ infects $q$. In other words, there
exists an $\left(  F\cup\left\{  u\right\}  \right)  $-path from $v$ to some
endpoint of $q$ (by the definition of \textquotedblleft
infects\textquotedblright). Let $\pi$ be this path. If this $\left(
F\cup\left\{  u\right\}  \right)  $-path $\pi$ did not contain the edge $u$,
then it would be an $F$-path, which would contradict the fact that there
exists no $F$-path from $v$ to any endpoint of $q$. Hence, this $\left(
F\cup\left\{  u\right\}  \right)  $-path $\pi$ must contain the edge $u$. By
removing $u$, we can thus cut this path $\pi$ into two segments: The first
segment is a path from $v$ to some endpoint of $u$, while the second segment
is a path from the other endpoint of $u$ to some endpoint of $q$. Both
segments are $F$-paths (since they arise by removing $u$ from an $\left(
F\cup\left\{  u\right\}  \right)  $-path). Thus, in particular, the first
segment is an $F$-path from $v$ to some endpoint of $u$. Hence, there exists
an $F$-path from $v$ to some endpoint of $u$. In other words, $F$ infects $u$
(by the definition of \textquotedblleft infects\textquotedblright).

But we have $u\in P$; hence, $F$ does not infect $u$ (since $F$ infects no
$p\in P$). This contradicts the fact that $F$ infects $u$. This contradiction
shows that our assumption was false. Hence, we have shown that $F\cup\left\{
u\right\}  $ infects no $p\in P$. In other words, $F\cup\left\{  u\right\}
\in N\left(  P\right)  $ (by the definition of $N\left(  P\right)  $). This
proves Claim 1.]

[\textit{Proof of Claim 2:} Let $F\in N\left(  P\right)  $ satisfy $u\in F$.
We must show that $F\setminus\left\{  u\right\}  \in N\left(  P\right)  $.

We have $F\in N\left(  P\right)  $. In other words, $F$ is a subset of $E$
that infects no $p\in P$. Thus, $F\setminus\left\{  u\right\}  $ is a subset
of $E$ (since $F\subseteq E$).

Now we claim that $F\setminus\left\{  u\right\}  $ infects no $p\in P$.
Indeed, assume the contrary. Then, $F\setminus\left\{  u\right\}  $ infects
some $p\in P$. In other words, $F\setminus\left\{  u\right\}  $ infects some
$q\in P$. In other words, there exists some $q\in P$ such that $F\setminus
\left\{  u\right\}  $ infects $q$. Consider this $q$. Note that $F$ does not
infect $q$ (since $F$ infects no $p\in P$).

We know that $F\setminus\left\{  u\right\}  $ infects $q$. In other words,
there exists an $\left(  F\setminus\left\{  u\right\}  \right)  $-path from
$v$ to some endpoint of $q$ (by the definition of \textquotedblleft
infects\textquotedblright). Hence, there exists an $F$-path from $v$ to some
endpoint of $q$ (since any $\left(  F\setminus\left\{  u\right\}  \right)
$-path is automatically an $F$-path\footnote{because $F\setminus\left\{
u\right\}  \subseteq F$}). In other words, $F$ infects $q$ (by the definition
of \textquotedblleft infects\textquotedblright). This contradicts the fact
that $F$ does not infect $q$. This contradiction shows that our assumption was
false. Hence, we have shown that $F\setminus\left\{  u\right\}  $ infects no
$p\in P$. In other words, $F\setminus\left\{  u\right\}  \in N\left(
P\right)  $ (by the definition of $N\left(  P\right)  $). This proves Claim 2.]

We have now proved both Claim 1 and Claim 2. Hence, we conclude that $u$ is
toggleable in $N\left(  P\right)  $ (by the definition of \textquotedblleft
toggleable\textquotedblright). This proves Lemma \ref{lem.NP-tog}.
\end{proof}

We can now easily obtain Lemma \ref{lem.NP}:

\begin{proof}
[Proof of Lemma \ref{lem.NP}.]\textbf{(a)} Let $P$ be a nonempty subset of
$E$. Then, there exists some $u\in P$ (since $P$ is nonempty). Consider this
$u$. Lemma \ref{lem.NP-tog} yields that $u$ is toggleable in $N\left(
P\right)  $. Thus, Lemma \ref{lem.toggle-gen} (applied to $U=E$ and
$\mathcal{S}=N\left(  P\right)  $) yields%
\[
\sum_{F\in N\left(  P\right)  }\left(  -1\right)  ^{\left\vert F\right\vert
}=0.
\]
This proves Lemma \ref{lem.NP} \textbf{(a)}.

\textbf{(b)} Assume that $E\neq\varnothing$. Let $P$ be a subset of $E$. We
must prove that
\[
\sum_{F\in N\left(  P\right)  }\left(  -1\right)  ^{\left\vert F\right\vert
}=0.
\]
If $P$ is nonempty, then this follows from Lemma \ref{lem.NP} \textbf{(a)}.
Thus, we WLOG assume that $P$ is empty. Hence, $N\left(  P\right)  $ is the
entire power set of $E$ (since the condition \textquotedblleft$F$ infects no
$p\in P$\textquotedblright\ in the definition of $N\left(  P\right)  $ is
vacuously true when $P$ is empty). Therefore,%
\[
\sum_{F\in N\left(  P\right)  }\left(  -1\right)  ^{\left\vert F\right\vert
}=\sum_{F\subseteq E}\left(  -1\right)  ^{\left\vert F\right\vert }=0
\]
(by Lemma \ref{lem.toggle}, applied to $U=E$). This proves Lemma \ref{lem.NP}
\textbf{(b)}.
\end{proof}

Lemma \ref{lem.NP} easily yields something slightly more general than Theorem
\ref{thm.elser0}:

\begin{theorem}
\label{thm.elser0G}Assume that $E\neq\varnothing$. Let $G$ be a subset of $E$.
Then,%
\[
\sum_{F\in A\left(  G\right)  }\left(  -1\right)  ^{\left\vert F\right\vert
}=0.
\]

\end{theorem}

\begin{proof}
[Proof of Theorem \ref{thm.elser0G}.]Lemma \ref{lem.APNP} yields%
\[
\sum_{F\in A\left(  G\right)  }\left(  -1\right)  ^{\left\vert F\right\vert
}=\sum_{P\subseteq G}\left(  -1\right)  ^{\left\vert P\right\vert
}\underbrace{\sum_{F\in N\left(  P\right)  }\left(  -1\right)  ^{\left\vert
F\right\vert }}_{\substack{=0\\\text{(by Lemma \ref{lem.NP} \textbf{(b)})}%
}}=\sum_{P\subseteq G}\left(  -1\right)  ^{\left\vert P\right\vert }0=0.
\]
This proves Theorem \ref{thm.elser0G}.
\end{proof}

\begin{proof}
[Proof of Theorem \ref{thm.elser0}.]Let $G$ be the set $E$. Thus, $G=E$, so
that%
\begin{align*}
A\left(  G\right)   &  =A\left(  E\right) \\
&  =\left\{  F\subseteq E\ \mid\ F\text{ infects each }p\in E\right\}
\ \ \ \ \ \ \ \ \ \ \left(  \text{by the definition of }A\left(  E\right)
\right) \\
&  =\left\{  F\subseteq E\ \mid\ F\text{ infects each }e\in E\right\}
=\left\{  F\subseteq E\ \mid\ F\text{ is pandemic}\right\}
\end{align*}
(by the definition of \textquotedblleft pandemic\textquotedblright). Hence,
\[
\sum_{F\in A\left(  G\right)  }\left(  -1\right)  ^{\left\vert F\right\vert
}=\sum_{\substack{F\subseteq E\text{ is}\\\text{pandemic}}}\left(  -1\right)
^{\left\vert F\right\vert }.
\]
But Theorem \ref{thm.elser0G} yields%
\[
\sum_{F\in A\left(  G\right)  }\left(  -1\right)  ^{\left\vert F\right\vert
}=0.
\]
Comparing these two equalities, we find
\[
\sum_{\substack{F\subseteq E\text{ is}\\\text{pandemic}}}\left(  -1\right)
^{\left\vert F\right\vert }=0.
\]
This proves Theorem \ref{thm.elser0}.
\end{proof}

\section{Vertex infection and other variants}

In our study of graphs so far, we have barely ever mentioned vertices (even
though they are, of course, implicit in the notion of a path). It may appear
somewhat strange to talk about a subset infecting an edge, when the infection
is spread from vertex to vertex. One might thus wonder if there is also a
vertex counterpart of Theorem \ref{thm.elser0}. So let us define analogues of
our notions for vertices:

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.)

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$.)

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

\begin{example}
Let $\Gamma$ be as in Example \ref{exa.example2}. Then, the path
$v\overset{1}{\longrightarrow}p\overset{2}{\longrightarrow}q$ is an
$F$-vertex-path for any subset $F\subseteq V$ that satisfies $p\in F$. The
subset $\left\{  p\right\}  $ of $V\setminus\left\{  v\right\}  $
vertex-infects each vertex (for example, $v\overset{1}{\longrightarrow
}p\overset{2}{\longrightarrow}q$ is a $\left\{  p\right\}  $-vertex-path from
$v$ to $q$, and $v\overset{4}{\longrightarrow}w$ is a $\left\{  p\right\}
$-vertex-path from $v$ to $w$), and thus is vertex-pandemic. The
vertex-pandemic subsets of $V\setminus\left\{  v\right\}  $ are the sets%
\[
\left\{  p\right\}  ,\ \ \left\{  w\right\}  ,\ \ \left\{  p,q\right\}
,\ \ \left\{  p,w\right\}  ,\ \ \left\{  q,w\right\}  ,\ \ \left\{
p,q,w\right\}  .
\]

\end{example}

We now have the following analogue of Theorem \ref{thm.elser0}:

\begin{theorem}
\label{thm.elser0-vert}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.
\]

\end{theorem}

\begin{proof}
[Proof of Theorem \ref{thm.elser0-vert}.]With just a few easy modifications,
our above proof of Theorem \ref{thm.elser0} can be repurposed as a proof of
Theorem \ref{thm.elser0-vert}. Namely:

\begin{itemize}
\item We need to replace \textquotedblleft edge\textquotedblright\ by
\textquotedblleft vertex\textquotedblright\ throughout the argument (including
Lemma \ref{lem.APNP}, Lemma \ref{lem.NP}, Lemma \ref{lem.NP-tog} and Theorem
\ref{thm.elser0G}), as well as replace $E$ by $V\setminus\left\{  v\right\}  $.

\item The words \textquotedblleft$F$-path\textquotedblright, \textquotedblleft
infects\textquotedblright\ and \textquotedblleft pandemic\textquotedblright%
\ have to be replaced by \textquotedblleft$F$-vertex-path\textquotedblright,
\textquotedblleft vertex-infects\textquotedblright\ and \textquotedblleft
vertex-pandemic\textquotedblright, respectively.

\item In the proof of Lemma \ref{lem.NP-tog}, the words \textquotedblleft an
endpoint of\textquotedblright\ (as well as \textquotedblleft any endpoint
of\textquotedblright\ and \textquotedblleft some endpoint of\textquotedblright%
) need to be removed (since the notion of \textquotedblleft
vertex-infects\textquotedblright\ is defined not in terms of paths to an
endpoint of a given edge, but in terms of paths to a given vertex).

\item In the proof of Lemma \ref{lem.NP-tog}, specifically in the proof of
Claim 1, the path $\pi$ is now cut not by removing the edge $u$, but by
splitting the path $\pi$ at the vertex $u$.
\end{itemize}

\noindent The reader may check that these changes result in a valid proof of
Theorem \ref{thm.elser0-vert}.
\end{proof}

Another variant of Theorem \ref{thm.elser0} (and Theorem \ref{thm.elser0G}) is
obtained by replacing the undirected graph $\Gamma$ with a directed graph
(while, of course, replacing paths by directed paths). More generally, we can
replace $\Gamma$ by a \textquotedblleft hybrid\textquotedblright\ graph with
some directed and some undirected edges.\footnote{We understand that a
directed edge still has two endpoints: its source and its target.} No changes
are required to the above proofs. Yet another variation can be obtained by
replacing \textquotedblleft endpoint\textquotedblright\ by \textquotedblleft
source\textquotedblright\ (for directed edges). We cannot, however, replace
\textquotedblleft endpoint\textquotedblright\ by \textquotedblleft
target\textquotedblright.

\section{An abstract perspective}

Seeing how little graph theory we have used in proving Theorem
\ref{thm.elser0}, and how easily the same argument adapted to Theorem
\ref{thm.elser0-vert}, we get the impression that there might be some general
theory lurking behind it. What follows is an attempt at building this theory.

Let $\mathcal{P}\left(  E\right)  $ denote the power set of $E$. The
\textquotedblleft infects\textquotedblright\ relation can be encoded as a map
$\operatorname*{Shade}:\mathcal{P}\left(  E\right)  \rightarrow\mathcal{P}%
\left(  E\right)  $ defined by%
\[
\operatorname*{Shade}F=\left\{  e\in E\ \mid\ F\text{ infects }e\right\}  .
\]
The definitions of the sets $A\left(  P\right)  $ and $N\left(  P\right)  $ in
Definition \ref{def.APNP} can thus be rewritten as%
\begin{align*}
A\left(  P\right)   &  =\left\{  F\subseteq E\ \mid\ P\subseteq
\operatorname*{Shade}F\right\}  \ \ \ \ \ \ \ \ \ \ \text{and}\\
N\left(  P\right)   &  =\left\{  F\subseteq E\ \mid\ P\cap
\operatorname*{Shade}F=\varnothing\right\}  .
\end{align*}


Hence, the claim of Theorem \ref{thm.elser0G} can be rewritten as%
\begin{equation}
\sum_{\substack{F\subseteq E;\\G\subseteq\operatorname*{Shade}F}}\left(
-1\right)  ^{\left\vert F\right\vert }=0 \label{eq.Shade.goal}%
\end{equation}
for any $G\subseteq E$, under the assumption that $E\neq\varnothing$.

To generalize this, we forget about the graph $\Gamma$ and the map
$\operatorname*{Shade}$, and instead start with an \textbf{arbitrary} finite
set $E$. (This corresponds to the set $E$ in Theorem \ref{thm.elser0} and to
the set $V\setminus\left\{  v\right\}  $ in Theorem \ref{thm.elser0-vert}.)
Let $\mathcal{P}\left(  E\right)  $ be the power set of $E$. Let
$\operatorname*{Shade}:\mathcal{P}\left(  E\right)  \rightarrow\mathcal{P}%
\left(  E\right)  $ be an arbitrary map (meant to generalize the map
$\operatorname*{Shade}$ from the previous paragraph). We may now ask:

\begin{question}
What (combinatorial) properties must $\operatorname*{Shade}$ satisfy in order
for (\ref{eq.Shade.goal}) to hold for any $G\subseteq E$ under the assumption
that $E\neq\varnothing$ ?
\end{question}

A partial answer to this question can be given by analyzing our above proof of
Theorem \ref{thm.elser0G} and extracting what was used:

\begin{theorem}
\label{thm.elser.genE0}Let $E$ be a finite set. Let $\operatorname*{Shade}%
:\mathcal{P}\left(  E\right)  \rightarrow\mathcal{P}\left(  E\right)  $ be an
arbitrary map that satisfies the following axioms:

\begin{statement}
\textit{Axiom 1:} Let $P,F\in\mathcal{P}\left(  E\right)  $ and $u\in
P\setminus F$ be such that $P\cap\operatorname*{Shade}F=\varnothing$. Then,
$P\cap\operatorname*{Shade}\left(  F\cup\left\{  u\right\}  \right)
=\varnothing$.
\end{statement}

\begin{statement}
\textit{Axiom 2:} Let $P,F\in\mathcal{P}\left(  E\right)  $ and $u\in P\cap F$
be such that $P\cap\operatorname*{Shade}F=\varnothing$. Then, $P\cap
\operatorname*{Shade}\left(  F\setminus\left\{  u\right\}  \right)
=\varnothing$.
\end{statement}

Assume that $E\neq\varnothing$. Let $G$ be any subset of $E$. Then,%
\[
\sum_{\substack{F\subseteq E;\\G\subseteq\operatorname*{Shade}F}}\left(
-1\right)  ^{\left\vert F\right\vert }=0.
\]

\end{theorem}

\begin{proof}
[Proof sketch.]Again, analogous to our above proof of Theorem
\ref{thm.elser0G}. (This time, in the proof of Lemma \ref{lem.NP-tog}, Claim 1
and Claim 2 follow from Axiom 1 and Axiom 2, respectively.)
\end{proof}

\begin{question}
Can the two axioms in Theorem \ref{thm.elser.genE0} be rewritten in a simpler
or more transparent way?
\end{question}

Here is one restatement of both Axioms 1 and 2: For any $F\subseteq E$ and any
two elements $u,v\in E\setminus\operatorname*{Shade}F$, we have $v\notin%
\operatorname*{Shade}\left(  F\cup\left\{  u\right\}  \right)  $ (Axiom 1) and
$v\notin\operatorname*{Shade}\left(  F\setminus\left\{  u\right\}  \right)  $
(Axiom 2).

\begin{question}
What are examples of maps $\operatorname*{Shade}:\mathcal{P}\left(  E\right)
\rightarrow\mathcal{P}\left(  E\right)  $ satisfying the two axioms in Theorem
\ref{thm.elser.genE0}?
\end{question}

We note that the map $\operatorname*{Shade}$ does not have to be monotonic
(i.e., it is not necessary that $\operatorname*{Shade}F\subseteq
\operatorname*{Shade}G$ whenever $F\subseteq G$). Examples of non-monotonic
maps $\operatorname*{Shade}$ that satisfy Axioms 1 and 2 are easily
constructed. (Indeed, if $\operatorname*{Shade}:\mathcal{P}\left(  E\right)
\rightarrow\mathcal{P}\left(  E\right)  $ is any map satisfying Axioms 1 and
2, then the map $\operatorname*{Shade}\nolimits^{\prime}:\mathcal{P}\left(
E\right)  \rightarrow\mathcal{P}\left(  E\right)  $ that sends each
$F\in\mathcal{P}\left(  E\right)  $ to $\operatorname*{Shade}\left(
E\setminus F\right)  \in\mathcal{P}\left(  E\right)  $ also satisfies Axioms
1' and 2'; but it is rare for both $\operatorname*{Shade}$ and
$\operatorname*{Shade}\nolimits^{\prime}$ to be monotonic.)

\subsection*{Acknowledgments}

I thank Galen Dorpalen-Barry and Tom Roby for insightful conversations. This
research was supported through the programme \textquotedblleft Oberwolfach
Leibniz Fellows\textquotedblright\ by the Mathematisches Forschungsinstitut
Oberwolfach in 2020. I am deeply grateful to the Institute for its hospitality
during a turbulent time.

\begin{thebibliography}{99999999}                                                                                         %


\bibitem[Aigner07]{Aigner07}%
\href{http://doi.org/10.1007/978-3-540-39035-0}{Martin Aigner, \textit{A
Course in Enumeration}, Graduate Texts in Mathematics \#238, Springer 2007.}

\bibitem[BenQui08]{BenQui08}%
\href{https://www.math.hmc.edu/~benjamin/papers/DIE.pdf}{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[DHLetc19]{DHLetc19}\href{https://arxiv.org/abs/1905.11330v4}{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.11330v4}. Accepted at
Journal of Combinatorial Theory A.

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

\bibitem[Rota64]{Rota64}\href{https://doi.org/10.1007/BF00531932}{Gian-Carlo
Rota, \textit{On the Foundations of Combinatorial Theory I. Theory of
M\"{o}bius Functions}, Z. Wahrscheinlichkeitstheorie \textbf{2} (1964), pp.
340--368}.

\bibitem[Sagan20]{Sagan19}Bruce Sagan, \textit{Combinatorics: The Art of
Counting}, preliminary version, 17 September 2020.\newline\url{https://users.math.msu.edu/users/bsagan/Books/Aoc/final.pdf}

\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.
\end{thebibliography}


\end{document}