2320211157012

# The Elser nuclei sum revisited

Darij Grinberg1  Drexel University, Philadelphia, PA, USA

(2020-12-22; 2021-01-12, 2021-04-28; 2021-05-04)

###### Abstract

Fix a finite undirected graph $\Gamma$ and a vertex $v$ of $\Gamma$. Let $E$
be the set of edges of $\Gamma$. We call a subset $F$ of $E$ _pandemic_ if
each edge of $\Gamma$ 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|F\right|}$ over all pandemic subsets
$F$ of $E$ is $0$ if $E\neq\varnothing$. We give a simple proof of this result
via a sign-reversing involution, and discuss variants, generalizations and a
refinement using discrete Morse theory.

###### keywords:

graph, simplicial complex, alternating sum, discrete Morse theory

In Elser (1984), 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 (Elser, 1984, Lemma 1), 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
Dorpalen-Barry et al. (2021) by Dorpalen-Barry, Hettle, Livingston, Martin,
Nasr, Vega and Whitlatch. In this note, I will show a simpler proof of the
lemma using a sign-reversing involution. The proof also suggests multiple
venues of generalization that I will explore in the later sections; one
extends the lemma to a statement about arbitrary antimatroids (and even a
wider setting). Finally, I will strengthen the lemma to a Morse-theoretical
result, stating the collapsibility of a certain simplicial complex. Some open
questions will be posed.

### Remark on alternative versions

The current version of this paper is written with a combinatorially
experienced reader in mind. The previous arXiv version Grinberg (2021)
includes more details in the proofs.

##  1 Elser’s result

Let us first introduce our setting, which is slightly more general (and
perhaps also simpler) than that used in Elser (1984). (In Section 4, we will
move to a more general setup.)

We fix an arbitrary graph $\Gamma$ with vertex set $V$ and edge set $E$. Here,
“graph” means “finite undirected multigraph” – 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$_-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$
_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.)111Note 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 _pandemic_ if it infects each edge $e\in
E$.

######  Example 1.1.

Let $\Gamma$ be the following graph:

$v$$p$$w$$q$$t$$r$$1$$2$$3$$4$$5$$6$$7$$8$

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

Now, we can state our version of (Elser, 1984, Lemma 1):

######  Theorem 1.2.

Assume that $E\neq\varnothing$. Then,

$\sum_{\begin{subarray}{c}F\subseteq E\text{ is}\\\
\text{pandemic}\end{subarray}}\left(-1\right)^{\left|F\right|}=0.$ (1)

######  Example 1.3.

Let $\Gamma$ be the following graph:

$v$$p$$q$$w$$1$$2$$3$$4$

(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, (1)
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.$

We note that the equality (1) can be restated as “there are equally many
pandemic subsets $F\subseteq E$ of even size and pandemic subsets $F\subseteq
E$ of odd size”. Thus, in particular, the number of all pandemic subsets $F$
of $E$ is even (when $E\neq\varnothing$).

######  Remark 1.4.

Theorem 1.2 is a bit more general than (Elser, 1984, Lemma 1). To see why, we
assume that the graph $\Gamma$ is connected and simple (i.e., has no self-
loops and parallel edges). Then, a _nucleus_ is defined in Elser (1984) as a
subgraph $N$ of $\Gamma$ with the properties that

  1. 1.

the subgraph $N$ is connected, and

  2. 2.

each edge of $\Gamma$ has at least one endpoint in $N$.

Given a subgraph $N$ of $\Gamma$, we let $\operatorname*{E}\left(N\right)$
denote the set of all edges of $N$. Now, (Elser, 1984, Lemma 1) claims that if
$E\neq\varnothing$, then

$\sum_{\begin{subarray}{c}N\text{ is a nucleus}\\\ \text{containing
}v\end{subarray}}\left(-1\right)^{\left|\operatorname*{E}\left(N\right)\right|}=0.$

But this is equivalent to (1), because there is a bijection

$\displaystyle\left\\{\text{nuclei containing }v\right\\}$
$\displaystyle\rightarrow\left\\{\text{pandemic subsets }F\subseteq
E\right\\},$ $\displaystyle N$
$\displaystyle\mapsto\operatorname*{E}\left(N\right).$

We leave it to the reader to check this in detail; what needs to be checked
are the following three statements:

  * •

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

  * •

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

  * •

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 “pandemic”, since
each vertex of $N$ other than $v$ belongs to at least one edge in $F$.)

Thus, Theorem 1.2 is equivalent to (Elser, 1984, Lemma 1) in the case when
$\Gamma$ is connected and simple.

######  Remark 1.5.

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 1.2
in which pandemicity is defined via infecting all vertices is not true. The
graph of Example 1.3 provides a counterexample.

##  2 The proof

###  2.1 Set-theoretical notions

We shall first introduce some concepts and notations pertaining to arbitrary
sets. They will aid us in proving Theorem 1.2, and also in generalizing it
later on.

######  Definition 2.1.

Let $A$ and $B$ be two sets. Then, we say that $A\prec B$ if we have
$B=A\cup\left\\{b\right\\}$ for some $b\in B\setminus A$. Equivalently,
$A\prec B$ holds if and only if $A\subseteq B$ and $\left|B\setminus
A\right|=1$.

######  Definition 2.2.

We let $\mathcal{P}\left(E\right)$ denote the power set of $E$ (that is, the
set of all subsets of $E$).

######  Definition 2.3.

Let $\mathcal{A}$ be a set. A map $\mu:\mathcal{A}\rightarrow\mathcal{A}$ is
said to be an _involution_ if
$\mu\circ\mu=\operatorname*{id}\nolimits_{\mathcal{A}}$.

######  Definition 2.4.

Let $\mathcal{A}$ be a subset of $\mathcal{P}\left(E\right)$. A _complete
matching_ of $\mathcal{A}$ shall mean an involution
$\mu:\mathcal{A}\rightarrow\mathcal{A}$ with the property that each
$F\in\mathcal{A}$ satisfies

$\text{either }\mu\left(F\right)\prec F\text{ or }F\prec\mu\left(F\right).$
(2)

The following simple fact abstracts an idea that will be used at least twice:

######  Lemma 2.5.

Let $\mathcal{A}$ be a subset of $\mathcal{P}\left(E\right)$. Let
$\mu:\mathcal{A}\rightarrow\mathcal{A}$ be a complete matching of
$\mathcal{A}$. Then,

$\sum_{F\in\mathcal{A}}\left(-1\right)^{\left|F\right|}=0.$ (3)

###### Proof.

This is a standard argument in enumerative combinatorics (see (Sagan, 2020,
(2.3)) or Benjamin and Quinn (2008) for a more general viewpoint). Here is the
proof: For each $F\in\mathcal{A}$, we have
$\left|\mu\left(F\right)\right|=\left|F\right|\pm 1$ (because (2) shows that
the sets $F$ and $\mu\left(F\right)$ differ in exactly one element) and thus
$\left(-1\right)^{\left|\mu\left(F\right)\right|}+\left(-1\right)^{\left|F\right|}=0$.
This shows, in particular, that $\mu$ has no fixed points. Thus, the
involution $\mu$ partitions the set $\mathcal{A}$ into $2$-element subsets
$\left\\{F,\mu\left(F\right)\right\\}$. Each such $2$-element subset
contributes
$\left(-1\right)^{\left|\mu\left(F\right)\right|}+\left(-1\right)^{\left|F\right|}=0$
to the sum on the left hand side of (3). Hence, this sum is $0$. This proves
Lemma 2.5. ∎

###  2.2 Shades

Next, we shall introduce the notion of a _shade_ ; this will be crucial to
proving and generalizing Theorem 1.2.

######  Definition 2.6.

Let $F$ be 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\\}.$
(4)

We refer to $\operatorname*{Shade}F$ as the _shade_ of $F$.

Thus, the shade of a subset $F\subseteq E$ is the set of all edges of $\Gamma$
that are infected by $F$. (In more standard graph-theoretical lingo, this
means that $\operatorname*{Shade}F$ is the set of edges that contain at least
one vertex of the connected component containing $v$ of the graph
$\left(V,F\right)$.)

######  Example 2.7.

In Example 1.1, we have
$\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\\}$.

The following property of shades is rather obvious:

######  Lemma 2.8.

Let $A$ and $B$ be two subsets of $E$ such that $A\subseteq B$. Then,
$\operatorname*{Shade}A\subseteq\operatorname*{Shade}B$.

The major property of shades that we will need is the following:

######  Lemma 2.9.

Let $F$ be a subset of $E$. Let $u\in E$ be such that
$u\notin\operatorname*{Shade}F$. Then,

$\operatorname*{Shade}\left(F\cup\left\\{u\right\\}\right)=\operatorname*{Shade}F$
(5)

and

$\operatorname*{Shade}\left(F\setminus\left\\{u\right\\}\right)=\operatorname*{Shade}F.$
(6)

###### Proof.

There is no $F$-path from $v$ to any endpoint of $u$ (since
$u\notin\operatorname*{Shade}F$). Hence, any
$\left(F\cup\left\\{u\right\\}\right)$-path that starts at $v$ must be an
$F$-path (as it would otherwise use the edge $u$ and thus contain an $F$-path
from $v$ to some endpoint of $u$). This entails
$\operatorname*{Shade}\left(F\cup\left\\{u\right\\}\right)\subseteq\operatorname*{Shade}F$.
Combined with the opposite inclusion (which follows from Lemma 2.8), this
yields (5).

Also, Lemma 2.8 yields
$\operatorname*{Shade}\left(F\setminus\left\\{u\right\\}\right)\subseteq\operatorname*{Shade}F$,
so that
$u\notin\operatorname*{Shade}\left(F\setminus\left\\{u\right\\}\right)$.
Hence, (6) follows by applying (5) to $F\setminus\left\\{u\right\\}$ instead
of $F$. ∎

###  2.3 A slightly more general claim

Lemma 2.9 might not look very powerful, but it contains all we need to prove
Theorem 1.2. Better yet, we shall prove the following slightly more general
version of Theorem 1.2:

######  Theorem 2.10.

Let $G$ be any subset of $E$. Assume that $E\neq\varnothing$. Then,

$\sum_{\begin{subarray}{c}F\subseteq E;\\\
G\subseteq\operatorname*{Shade}F\end{subarray}}\left(-1\right)^{\left|F\right|}=0.$

We will soon prove Theorem 2.10 and explain how Theorem 1.2 follows from it.
First, however, let us give an equivalent (but slightly easier to prove)
version of Theorem 2.10:

######  Theorem 2.11.

Let $G$ be any subset of $E$. Then,

$\sum_{\begin{subarray}{c}F\subseteq E;\\\
G\not\subseteq\operatorname*{Shade}F\end{subarray}}\left(-1\right)^{\left|F\right|}=0.$
(7)

###### Proof.

Let

$\mathcal{A}=\left\\{F\subseteq E\ \mid\
G\not\subseteq\operatorname*{Shade}F\right\\}.$ (8)

Thus, $\mathcal{A}$ is a subset of $\mathcal{P}\left(E\right)$, and each
$F\in\mathcal{A}$ satisfies $G\not\subseteq\operatorname*{Shade}F$.

We equip the finite set $E$ with a total order (chosen arbitrarily, but fixed
henceforth). If $F\in\mathcal{A}$, then we define $\varepsilon\left(F\right)$
to be the smallest edge $e\in G\setminus\operatorname*{Shade}F$. (Such an edge
exists, since $F\in\mathcal{A}$ entails $G\not\subseteq\operatorname*{Shade}F$
and thus $G\setminus\operatorname*{Shade}F\neq\varnothing$.)

For any $F\in\mathcal{A}$, we have
$\varepsilon\left(F\right)\notin\operatorname*{Shade}F$ (by the definition of
$\varepsilon\left(F\right)$). Thus, any $F\in\mathcal{A}$ satisfies
$\operatorname*{Shade}\left(F\cup\left\\{\varepsilon\left(F\right)\right\\}\right)=\operatorname*{Shade}F$
(by (5)) and
$\operatorname*{Shade}\left(F\setminus\left\\{\varepsilon\left(F\right)\right\\}\right)=\operatorname*{Shade}F$
(by (6)). In other words, if we replace a set $F\in\mathcal{A}$ by
$F\cup\left\\{\varepsilon\left(F\right)\right\\}$ or
$F\setminus\left\\{\varepsilon\left(F\right)\right\\}$, then
$\operatorname*{Shade}F$ does not change. Hence, $\varepsilon\left(F\right)$
does not change either (since $\varepsilon\left(F\right)$ depends only on
$\operatorname*{Shade}F$, but not on $F$ itself). Furthermore, the resulting
set ($F\cup\left\\{\varepsilon\left(F\right)\right\\}$ or
$F\setminus\left\\{\varepsilon\left(F\right)\right\\}$) still belongs to
$\mathcal{A}$ (since $\operatorname*{Shade}F$ has not changed). Thus, we can
define a map

$\displaystyle\mu:\mathcal{A}$ $\displaystyle\rightarrow\mathcal{A},$
$\displaystyle F$
$\displaystyle\mapsto\begin{cases}F\cup\left\\{\varepsilon\left(F\right)\right\\},&\text{if
}\varepsilon\left(F\right)\notin F;\\\
F\setminus\left\\{\varepsilon\left(F\right)\right\\},&\text{if
}\varepsilon\left(F\right)\in F.\end{cases}$

Clearly, this map $\mu$ is an involution (since we have shown that
$\varepsilon\left(F\right)$ does not change when we replace $F$ by
$\mu\left(F\right)$). Moreover, this map $\mu$ is a complete matching (since
each $F\in\mathcal{A}$ satisfies $F\prec\mu\left(F\right)$ if
$\varepsilon\left(F\right)\notin F$, and satisfies $\mu\left(F\right)\prec F$
otherwise). Hence, Lemma 2.5 yields
$\sum\limits_{F\in\mathcal{A}}\left(-1\right)^{\left|F\right|}=0$. In view of
how we defined $\mathcal{A}$, this is equivalent to (7). Thus, (7) is proven.
∎

In order to derive Theorem 2.10 from Theorem 2.11, we need the following
innocent lemma:

######  Lemma 2.12.

Let $U$ be a finite set with $U\neq\varnothing$. Then,

$\sum_{F\subseteq U}\left(-1\right)^{\left|F\right|}=0.$

###### Proof.

This is an easy (and well-known) consequence of Lemma 2.5. It also follows
from the well-known binomial identity
$\sum_{k=0}^{n}\left(-1\right)^{k}\dbinom{n}{k}=0$ that holds for any integer
$n>0$. ∎

We can now easily derive Theorem 2.10 from Theorem 2.11:

###### of Theorem 2.10.

We have

$\sum_{F\subseteq
E}\left(-1\right)^{\left|F\right|}=\sum_{\begin{subarray}{c}F\subseteq E;\\\
G\subseteq\operatorname*{Shade}F\end{subarray}}\left(-1\right)^{\left|F\right|}+\underbrace{\sum_{\begin{subarray}{c}F\subseteq
E;\\\
G\not\subseteq\operatorname*{Shade}F\end{subarray}}\left(-1\right)^{\left|F\right|}}_{\begin{subarray}{c}=0\\\
\text{(by Theorem \ref{thm.elser-
Shade0})}\end{subarray}}=\sum_{\begin{subarray}{c}F\subseteq E;\\\
G\subseteq\operatorname*{Shade}F\end{subarray}}\left(-1\right)^{\left|F\right|}.$

However, Lemma 2.12 (applied to $U=E$) shows that the left hand side of this
equality is $0$. Thus, so is the right hand side. This proves Theorem 2.10. ∎

###  2.4 Proving Theorem 1.2

###### of Theorem 1.2.

Theorem 1.2 follows by applying Theorem 2.10 to $G=E$ (since a subset $F$ of
$E$ satisfies $E\subseteq\operatorname*{Shade}F$ if and only if it is
pandemic). ∎

##  3 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). Even though the
infection is spread from vertex to vertex, our sets so far have infected edges
(not vertices). One might thus wonder if there is also a vertex counterpart of
Theorem 1.2. So let us define analogues of our notions for vertices:

If $F\subseteq V$, then an $F$_-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$ _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 _vertex-
pandemic_ if it vertex-infects each vertex $w\in
V\setminus\left\\{v\right\\}$.

######  Example 3.1.

Let $\Gamma$ be as in Example 1.3. 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\\}.$

We now have the following analogue of Theorem 1.2:

######  Theorem 3.2.

Assume that $V\setminus\left\\{v\right\\}\neq\varnothing$. Then,

$\sum_{\begin{subarray}{c}F\subseteq V\setminus\left\\{v\right\\}\text{ is}\\\
\text{vertex-pandemic}\end{subarray}}\left(-1\right)^{\left|F\right|}=0.$

###### Proof.

With a few easy modifications, our above proof of Theorem 1.2 can be
repurposed as a proof of Theorem 3.2. Most importantly, we need to replace the
set $E$ by $V\setminus\left\\{v\right\\}$, and we need to replace the words
“edge”, “$F$-path”, “infects” and “pandemic” by “vertex”, “$F$-vertex-path”,
“vertex-infects” and “vertex-pandemic”, respectively. ∎

Another variant of Theorem 1.2 (and Theorem 2.10 and Theorem 2.11) 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 “hybrid” graph with some directed and some undirected
edges.222We 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 “endpoint” by “source” (for
directed edges). We cannot, however, replace “endpoint” by “target”.

##  4 An abstract perspective

Seeing how little graph theory we have used in proving Theorem 1.2, and how
easily the same argument adapted to Theorem 3.2, we get the impression that
there might be some general theory lurking behind it. What follows is an
attempt at building this theory.

Most proofs in this section are omitted; some are outlined. In fact, they are
all sufficiently simple and straightforward that the reader should have little
trouble filling them in; alternatively, almost all of them can be found in the
detailed version of Grinberg (2021).

###  4.1 Shade maps

Let $\mathcal{P}\left(E\right)$ denote the power set of $E$. In Definition
2.6, we have encoded the “infects” relation 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\\}$. As we recall, Theorem 2.10 (a generalization of Theorem 1.2)
states that

$\sum_{\begin{subarray}{c}F\subseteq E;\\\
G\subseteq\operatorname*{Shade}F\end{subarray}}\left(-1\right)^{\left|F\right|}=0$
(9)

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 arbitrary finite set $E$.
(This set $E$ corresponds to the set $E$ in Theorem 1.2 and to the set
$V\setminus\left\\{v\right\\}$ in Theorem 3.2.) 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:

######  Question 4.1.

What (combinatorial) properties must $\operatorname*{Shade}$ satisfy in order
for (9) to hold for any $G\subseteq E$ under the assumption that
$E\neq\varnothing$ ?

A partial answer to this question can be given by analyzing our above proof of
Theorem 2.10 and extracting what was used:

######  Definition 4.2.

Let $E$ be a set. A _shade map_ on $E$ shall mean a map
$\operatorname*{Shade}:\mathcal{P}\left(E\right)\rightarrow\mathcal{P}\left(E\right)$
that satisfies the following two axioms:

> Axiom 1: If $F\in\mathcal{P}\left(E\right)$ and $u\in
> E\setminus\operatorname*{Shade}F$, then
> $\operatorname*{Shade}\left(F\cup\left\\{u\right\\}\right)=\operatorname*{Shade}F$.

> Axiom 2: If $F\in\mathcal{P}\left(E\right)$ and $u\in
> E\setminus\operatorname*{Shade}F$, then
> $\operatorname*{Shade}\left(F\setminus\left\\{u\right\\}\right)=\operatorname*{Shade}F$.

######  Theorem 4.3.

Let $E$ be a finite set. Let
$\operatorname*{Shade}:\mathcal{P}\left(E\right)\rightarrow\mathcal{P}\left(E\right)$
be a shade map on $E$.

Assume that $E\neq\varnothing$. Let $G$ be any subset of $E$. Then,

$\sum_{\begin{subarray}{c}F\subseteq E;\\\
G\subseteq\operatorname*{Shade}F\end{subarray}}\left(-1\right)^{\left|F\right|}=0.$

###### Proof.

Again, the proof is analogous to our above proof of Theorem 2.10. (This time,
in the proof of Lemma 2.9, the equalities (5) and (6) follow directly from
Axiom 1 and Axiom 2, respectively.) ∎

How do shade maps relate to known concepts in the combinatorics of set
families (such as topologies, clutters, matroids, or submodular functions)?
Are they just one of these known concepts in disguise? We shall answer two
versions of this question in the following subsections. Specifically:

  * •

In Subsection 4.3, we will show that inclusion-reversing shade maps on $E$
(i.e., shade maps $\operatorname*{Shade}$ that satisfy
$\operatorname*{Shade}B\subseteq\operatorname*{Shade}A$ whenever $A\subseteq
B$) are in bijection with _antimatroidal quasi-closure operators_ (a slight
variant of antimatroids) on $E$.

  * •

In Subsection 4.4, we will show that arbitrary shade maps are in bijection
with _Boolean interval partitions_ of $\mathcal{P}\left(E\right)$ (that is,
set partitions of $\mathcal{P}\left(E\right)$ into intervals of the Boolean
lattice $\mathcal{P}\left(E\right)$).

Before we come to these characterizations, we shall however make a few
elementary remarks on shade maps.

First, we observe that Axioms 1 and 2 in Definition 4.2 can be weakened to the
following statements:

> Axiom 1’: If $F\in\mathcal{P}\left(E\right)$ and $u\in
> E\setminus\operatorname*{Shade}F$, then
> $\operatorname*{Shade}\left(F\cup\left\\{u\right\\}\right)\subseteq\operatorname*{Shade}F$.

> Axiom 2’: If $F\in\mathcal{P}\left(E\right)$ and $u\in
> E\setminus\operatorname*{Shade}F$, then
> $\operatorname*{Shade}\left(F\setminus\left\\{u\right\\}\right)\subseteq\operatorname*{Shade}F$.

Axiom 1’ is weaker than Axiom 1, and likewise Axiom 2’ is weaker than Axiom 2.
However, Axioms 1’ and 2’ combined are equivalent to Axioms 1 and 2 combined:

######  Proposition 4.4.

Let $E$ be a set. Let
$\operatorname*{Shade}:\mathcal{P}\left(E\right)\rightarrow\mathcal{P}\left(E\right)$
be any map. Then, $\operatorname*{Shade}$ is a shade map on $E$ if and only if
$\operatorname*{Shade}$ satisfies the two Axioms 1’ and 2’ stated above.

Axioms 1 and 2 can also be combined into one common axiom:

> Axiom 3: If $F\in\mathcal{P}\left(E\right)$ and $u\in E\setminus F$, then we
> have
> $\operatorname*{Shade}F=\operatorname*{Shade}\left(F\cup\left\\{u\right\\}\right)$
> or
> $u\in\left(\operatorname*{Shade}F\right)\cap\operatorname*{Shade}\left(F\cup\left\\{u\right\\}\right)$.

######  Proposition 4.5.

Let $E$ be a set. Let
$\operatorname*{Shade}:\mathcal{P}\left(E\right)\rightarrow\mathcal{P}\left(E\right)$
be any map. Then, $\operatorname*{Shade}$ is a shade map on $E$ if and only if
$\operatorname*{Shade}$ satisfies Axiom 3.

We will soon see some examples. First, let us introduce two more basic
concepts that will help clarify these examples:

######  Definition 4.6.

Let $E$ be a set. Let
$\operatorname*{Shade}:\mathcal{P}\left(E\right)\rightarrow\mathcal{P}\left(E\right)$
be any map (not necessarily a shade map).

(a) We say that $\operatorname*{Shade}$ is _inclusion-preserving_ if it
satisfies the following property: If $A$ and $B$ are two subsets of $E$ such
that $A\subseteq B$, then
$\operatorname*{Shade}A\subseteq\operatorname*{Shade}B$.

(b) We say that $\operatorname*{Shade}$ is _inclusion-reversing_ if it
satisfies the following property: If $A$ and $B$ are two subsets of $E$ such
that $A\subseteq B$, then
$\operatorname*{Shade}B\subseteq\operatorname*{Shade}A$.

For instance, the map $\operatorname*{Shade}$ from Definition 2.6 is
inclusion-preserving (because of Lemma 2.8) and is a shade map (by Lemma 2.9).
The same holds for the analogue of the map $\operatorname*{Shade}$ that uses
vertex-infection instead of infection. We will soon see some inclusion-
reversing shade maps, and it is not hard to construct shade maps that are
neither inclusion-preserving nor inclusion-reversing.

Let us observe that there is a simple bijection between inclusion-preserving
and inclusion-reversing maps, and this bijection preserves shadeness:

######  Proposition 4.7.

Let $E$ be a set. Let
$\operatorname*{Shade}:\mathcal{P}\left(E\right)\rightarrow\mathcal{P}\left(E\right)$
be any map (not necessarily a shade map). Let
$\operatorname*{Shade}\nolimits^{\prime}:\mathcal{P}\left(E\right)\rightarrow\mathcal{P}\left(E\right)$
be the map that sends each $F\in\mathcal{P}\left(E\right)$ to
$\operatorname*{Shade}\left(E\setminus F\right)\in\mathcal{P}\left(E\right)$.
Then:

(a) The map $\operatorname*{Shade}$ is inclusion-preserving if and only if the
map $\operatorname*{Shade}\nolimits^{\prime}$ is inclusion-reversing.

(b) The map $\operatorname*{Shade}$ is a shade map if and only if the map
$\operatorname*{Shade}\nolimits^{\prime}$ is a shade map.

######  Definition 4.8.

Let $E$, $\operatorname*{Shade}$ and $\operatorname*{Shade}\nolimits^{\prime}$
be as in Proposition 4.7. We then say that the map
$\operatorname*{Shade}\nolimits^{\prime}$ is _dual_ to
$\operatorname*{Shade}$.

###  4.2 Some examples of shade maps

As we already mentioned, Lemma 2.9 and its analogue for vertex-infection
provide two examples of inclusion-preserving shade maps
$\operatorname*{Shade}$. An example of an inclusion-reversing shade map comes
from the theory of posets:

######  Example 4.9.

Let $E$ be a poset. For any $F\subseteq E$, we define

$F_{\downarrow}=\left\\{e\in E\ \mid\ \text{there exists an }f\in F\text{ with
}e<f\right\\}$

and

$\operatorname*{Shade}F=E\setminus F_{\downarrow}.$

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

Another example of a shade map comes from discrete geometry:

######  Example 4.10.

Let $A$ be an affine space over $\mathbb{R}$. If $S$ is a finite subset of
$A$, then a _nontrivial convex combination_ of $S$ will mean a point of the
form $\sum_{s\in S}\lambda_{s}s\in A$, where the coefficients $\lambda_{s}$
are nonnegative reals smaller than $1$ and satisfying $\sum_{s\in
S}\lambda_{s}=1$.

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 {not} a nontrivial
convex combination of }F\right\\}.$

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

As a contrast to Example 4.10, let us mention a not-quite-example (satisfying
only one of the two axioms in Theorem 4.3):

######  Example 4.11.

Let $V$ be a vector space over $\mathbb{R}$. If $S$ is a finite subset of $V$,
then a _nontrivial conic combination_ of $S$ will mean a vector of the form
$\sum_{s\in S}\lambda_{s}s\in V$, where the coefficients $\lambda_{s}$ are
nonnegative reals with the property that at least two elements $s\in S$
satisfy $\lambda_{s}>0$.

Fix a finite subset $E$ of $V$. For any $F\subseteq E$, we define

$\operatorname*{Shade}F=\left\\{e\in E\ \mid\ e\text{ is {not} a nontrivial
conic combination of }F\right\\}.$

It can be shown that this map
$\operatorname*{Shade}:\mathcal{P}\left(E\right)\rightarrow\mathcal{P}\left(E\right)$
satisfies Axiom 1 in Definition 4.2. In general, it does not satisfy Axiom 2.
Thus, it is not a shade map in general.

###  4.3 Antimatroids and inclusion-reversing shade maps

Examples 4.9 and 4.10 are instances of a general class of examples: shade maps
coming from _antimatroids_. Not unlike matroids, antimatroids are a
combinatorial concept with many equivalent avatars (see, e.g., (Korte et al.,
1991, Chapter III)). Here we shall view them through one of these avatars:
that of _antimatroidal quasi-closure operators_ (roughly equivalent to _convex
geometries_). We begin by defining the notions we need:

######  Definition 4.12.

Let $E$ be any set.

(a) A _quasi-closure operator_ on $E$ means a map
$\tau:\mathcal{P}\left(E\right)\rightarrow\mathcal{P}\left(E\right)$ with the
following properties:

  1. 1.

We have $A\subseteq\tau\left(A\right)$ for any $A\subseteq E$.

  2. 2.

If $A$ and $B$ are two subsets of $E$ satisfying $A\subseteq B$, then
$\tau\left(A\right)\subseteq\tau\left(B\right)$.

  3. 3.

We have $\tau\left(\tau\left(A\right)\right)=\tau\left(A\right)$ for any
$A\subseteq E$.

(b) A quasi-closure operator $\tau$ on $E$ is said to be _antimatroidal_ if it
has the following additional property:

  1. 4.

If $X$ is a subset of $E$, and if $y$ and $z$ are two distinct elements of
$E\setminus\tau\left(X\right)$ satisfying
$z\in\tau\left(X\cup\left\\{y\right\\}\right)$, then
$y\notin\tau\left(X\cup\left\\{z\right\\}\right)$.

(c) A _closure operator_ on $E$ means a quasi-closure operator $\tau$ on $E$
that satisfies $\tau\left(\varnothing\right)=\varnothing$.

(d) If $\tau$ is an antimatroidal closure operator on $E$, then the pair
$\left(E,\tau\right)$ is called a _convex geometry_.

Here are some examples of antimatroidal quasi-closure operators:

######  Example 4.13.

Let $E$ be a poset. For any $F\subseteq E$, we define

$\tau\left(F\right)=\left\\{e\in E\ \mid\ \text{there exists an }f\in F\text{
with }e\leq f\right\\}.$

Then, $\tau$ is an antimatroidal closure operator on $E$. (This example is the
“downset alignment” from (Edelman and Jamison, 1985, §3, Example II), and is
equivalent to the “poset antimatroid” from (Korte et al., 1991, §III.2.3).)

######  Example 4.14.

Let $E$ be a poset. For any $F\subseteq E$, we define

$\tau\left(F\right)=\left\\{e\in E\ \mid\ \text{there exist }f\in F\text{ and
}g\in F\text{ with }g\leq e\leq f\right\\}.$

Then, $\tau$ is an antimatroidal closure operator on $E$. (This example is the
“order convex alignment” from (Edelman and Jamison, 1985, §3, Example II), and
is the “double shelling of a poset” example from (Korte et al., 1991,
§III.2.4).)

######  Example 4.15.

Let $A$ be an affine space over $\mathbb{R}$. If $S$ is a finite subset of
$A$, then a _convex combination_ of $S$ will mean a point of the form
$\sum_{s\in S}\lambda_{s}s\in A$, where the coefficients $\lambda_{s}$ are
nonnegative reals satisfying $\sum_{s\in S}\lambda_{s}=1$.

Fix a finite subset $E$ of $A$. For any $F\subseteq E$, we define

$\tau\left(F\right)=\left\\{e\in E\ \mid\ e\text{ is a convex combination of
}F\right\\}.$

Then, $\tau$ is an antimatroidal closure operator on $E$. (This example is
(Edelman and Jamison, 1985, §3, Example I); it gave the name “convex geometry”
to the notion defined in Definition 4.12 (d).)

######  Example 4.16.

Let $\Gamma$ be any graph with edge set $E$. Fix a vertex $v$ of $\Gamma$. We
say that a subset $F\subseteq E$ _blocks_ an edge $e\in E$ if each path of
$\Gamma$ that contains $v$ and $e$ must contain at least one edge of $F$. (In
particular, this is automatically the case when $e\in F$.) For each
$F\subseteq E$, we define

$\tau\left(F\right)=\left\\{e\in E\ \mid\ F\text{ blocks }e\right\\}.$

Then, $\tau$ is an antimatroidal quasi-closure operator on $E$. (This example
is the “line-search antimatroid” from (Korte et al., 1991, §III.2.11).) If
$\Gamma$ is connected, then $\tau$ is actually a closure operator.

Further examples of antimatroidal closure operators can be found in (Korte et
al., 1991, §III.2) and (Edelman and Jamison, 1985, §3).

We shall be dealing with quasi-closure operators rather than closure operators
most of the time. However, since the latter concept is somewhat more
widespread, let us comment on the connection between the two. Roughly
speaking, the relation between quasi-closure and closure operators is
comparable to the relation between semigroups and monoids, or between
nonunital rings and unital rings, or (perhaps the best analogue) between
simplicial complexes in general and simplicial complexes without ghost
vertices (i.e., simplicial complexes for which every element of the ground set
is a dimension-$0$ face). More concretely, specifying a quasi-closure operator
on a set $E$ is tantamount to specifying a subset of $E$ and a closure
operator on this subset. To wit:

######  Proposition 4.17.

Let $E$ be a set. Let $L$ be a subset of $E$.

(a) Then, there is a bijection

$\displaystyle\text{from }\left\\{\text{quasi-closure operators }\tau\text{ on
}E\text{ satisfying }\tau\left(\varnothing\right)=L\right\\}$
$\displaystyle\text{to }\left\\{\text{closure operators }\sigma\text{ on
}E\setminus L\right\\}$

that is defined as follows: It sends each quasi-closure operator $\tau$ to the
closure operator $\sigma$ that sends each $F\subseteq E\setminus L$ to
$\tau\left(F\right)\setminus L$.

(b) This bijection restricts to a bijection

$\displaystyle\text{from }\left\\{\text{antimatroidal quasi-closure operators
}\tau\text{ on }E\text{ satisfying }\tau\left(\varnothing\right)=L\right\\}$
$\displaystyle\text{to }\left\\{\text{antimatroidal closure operators
}\sigma\text{ on }E\setminus L\right\\}.$

Now, we claim the following:

######  Theorem 4.18.

Let $E$ be a set. Let
$\tau:\mathcal{P}\left(E\right)\rightarrow\mathcal{P}\left(E\right)$ be an
antimatroidal quasi-closure operator on $E$. For any $F\subseteq E$, we define

$\operatorname*{Shade}F=\left\\{e\in E\ \mid\
e\notin\tau\left(F\setminus\left\\{e\right\\}\right)\right\\}.$ (10)

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

Theorem 4.18 generalizes Examples 4.9 and 4.10. Indeed, the latter two
examples are obtained by applying Theorem 4.18 to the settings of Examples
4.13 and 4.15, respectively. Less directly, Lemma 2.9 and its vertex-infection
analogue are particular cases of Theorem 4.18 as well (even though they
involve shade maps that are inclusion-preserving rather than inclusion-
reversing). Indeed, if we apply Theorem 4.18 to the setting of Example 4.16,
then we obtain the claim of Lemma 2.9 with $\operatorname*{Shade}F$ replaced
by $\operatorname*{Shade}\left(E\setminus F\right)$; this is easily seen to be
equivalent to Lemma 2.9 (by the duality stated in Proposition 4.7).

Our proof of Theorem 4.18 will rely on two easy lemmas:

######  Lemma 4.19.

Let $E$ be a set. Let $\tau$ be a quasi-closure operator on $E$. Let $X$ be a
subset of $E$, and let $z\in\tau\left(X\right)$. Then,
$\tau\left(X\cup\left\\{z\right\\}\right)=\tau\left(X\right)$.

######  Lemma 4.20.

Let $E$ be a set. Let $\tau$ be an antimatroidal quasi-closure operator on
$E$. Let $X$ be a subset of $E$, and let $y$ and $z$ be two distinct elements
of $E$ satisfying $z\in\tau\left(X\cup\left\\{y\right\\}\right)$ and
$y\in\tau\left(X\cup\left\\{z\right\\}\right)$. Then,
$y\in\tau\left(X\right)$.

Note that Lemma 4.20 has a converse: If $\tau$ is a quasi-closure operator on
$E$ satisfying the claim of Lemma 4.20, then $\tau$ is antimatroidal. This is
easy to see but will not be used in what follows.

###### of Theorem 4.18.

We shall prove the following three statements:

> Statement 0: If $A$ and $B$ are two subsets of $E$ such that $A\subseteq B$,
> then $\operatorname*{Shade}B\subseteq\operatorname*{Shade}A$.

> Statement 1: If $F\in\mathcal{P}\left(E\right)$ and $u\in
> E\setminus\operatorname*{Shade}F$, then
> $\operatorname*{Shade}\left(F\cup\left\\{u\right\\}\right)=\operatorname*{Shade}F$.

> Statement 2: If $F\in\mathcal{P}\left(E\right)$ and $u\in
> E\setminus\operatorname*{Shade}F$, then
> $\operatorname*{Shade}\left(F\setminus\left\\{u\right\\}\right)=\operatorname*{Shade}F$.

Our proofs of these three statements will use Property 2 in Definition 4.12
(a) (which we shall just refer to as “Property 2”).

[Proof of Statement 0: Let $A$ and $B$ be two subsets of $E$ such that
$A\subseteq B$. We must prove that
$\operatorname*{Shade}B\subseteq\operatorname*{Shade}A$.

Let $u\in\operatorname*{Shade}B$. Thus, $u\in E$ and
$u\notin\tau\left(B\setminus\left\\{u\right\\}\right)$ (by the definition of
$\operatorname*{Shade}B$). However, $A\setminus\left\\{u\right\\}\subseteq
B\setminus\left\\{u\right\\}$ (since $A\subseteq B$) and thus
$\tau\left(A\setminus\left\\{u\right\\}\right)\subseteq\tau\left(B\setminus\left\\{u\right\\}\right)$
(by Property 2). Hence, from
$u\notin\tau\left(B\setminus\left\\{u\right\\}\right)$, we obtain
$u\notin\tau\left(A\setminus\left\\{u\right\\}\right)$. Therefore,
$u\in\operatorname*{Shade}A$ (by the definition of $\operatorname*{Shade}A$).

Since we have shown this for each $u\in\operatorname*{Shade}B$, we thus obtain
$\operatorname*{Shade}B\subseteq\operatorname*{Shade}A$. This proves Statement
0.]

[Proof of Statement 2: Let $F\in\mathcal{P}\left(E\right)$ and $u\in
E\setminus\operatorname*{Shade}F$. We must prove that
$\operatorname*{Shade}\left(F\setminus\left\\{u\right\\}\right)=\operatorname*{Shade}F$.

We have $u\in E\setminus\operatorname*{Shade}F$, so that
$u\notin\operatorname*{Shade}F$. In other words, $u\in E$ and
$u\in\tau\left(F\setminus\left\\{u\right\\}\right)$ (by the definition of
$\operatorname*{Shade}F$).

We have $F\setminus\left\\{u\right\\}\subseteq F$ and thus
$\operatorname*{Shade}F\subseteq\operatorname*{Shade}\left(F\setminus\left\\{u\right\\}\right)$
(by Statement 0).

Now, let $v\in\operatorname*{Shade}\left(F\setminus\left\\{u\right\\}\right)$.
We shall prove that $v\in\operatorname*{Shade}F$.

Indeed, assume the contrary. Hence, $v\notin\operatorname*{Shade}F$. In other
words, $v\in E$ and $v\in\tau\left(F\setminus\left\\{v\right\\}\right)$ (by
the definition of $\operatorname*{Shade}F$).

Let $X=\left(F\setminus\left\\{u\right\\}\right)\setminus\left\\{v\right\\}$.
Then, $F\setminus\left\\{u\right\\}\subseteq X\cup\left\\{v\right\\}$ and
therefore
$\tau\left(F\setminus\left\\{u\right\\}\right)\subseteq\tau\left(X\cup\left\\{v\right\\}\right)$
(by Property 2). Hence,
$u\in\tau\left(F\setminus\left\\{u\right\\}\right)\subseteq\tau\left(X\cup\left\\{v\right\\}\right)$.

Also, from
$X=\left(F\setminus\left\\{u\right\\}\right)\setminus\left\\{v\right\\}=\left(F\setminus\left\\{v\right\\}\right)\setminus\left\\{u\right\\}$,
we obtain $F\setminus\left\\{v\right\\}\subseteq X\cup\left\\{u\right\\}$ and
therefore
$\tau\left(F\setminus\left\\{v\right\\}\right)\subseteq\tau\left(X\cup\left\\{u\right\\}\right)$
(by Property 2). Hence,
$v\in\tau\left(F\setminus\left\\{v\right\\}\right)\subseteq\tau\left(X\cup\left\\{u\right\\}\right)$.

However, from
$v\in\operatorname*{Shade}\left(F\setminus\left\\{u\right\\}\right)$, we
obtain
$v\notin\tau\left(\left(F\setminus\left\\{u\right\\}\right)\setminus\left\\{v\right\\}\right)$
(by the definition of
$\operatorname*{Shade}\left(F\setminus\left\\{u\right\\}\right)$). In other
words, $v\notin\tau\left(X\right)$ (since
$X=\left(F\setminus\left\\{u\right\\}\right)\setminus\left\\{v\right\\}$).
However, if $v$ and $u$ were distinct, then Lemma 4.20 (applied to $y=v$ and
$z=u$) would yield $v\in\tau\left(X\right)$ (since
$v\in\tau\left(X\cup\left\\{u\right\\}\right)$ and
$u\in\tau\left(X\cup\left\\{v\right\\}\right)$), which would contradict
$v\notin\tau\left(X\right)$. Thus, $v$ and $u$ cannot be distinct. In other
words, $v=u$. Now,
$X=\left(F\setminus\left\\{u\right\\}\right)\setminus\left\\{v\right\\}=F\setminus\left\\{u\right\\}$
(since $v=u$). Therefore, $u\in\tau\left(F\setminus\left\\{u\right\\}\right)$
rewrites as $u\in\tau\left(X\right)$. Hence, $v=u\in\tau\left(X\right)$; but
this contradicts $v\notin\tau\left(X\right)$.

This contradiction shows that our assumption was false; hence, we conclude
that $v\in\operatorname*{Shade}F$. Since we have proved this for each
$v\in\operatorname*{Shade}\left(F\setminus\left\\{u\right\\}\right)$, we thus
obtain
$\operatorname*{Shade}\left(F\setminus\left\\{u\right\\}\right)\subseteq\operatorname*{Shade}F$.
Combining this with
$\operatorname*{Shade}F\subseteq\operatorname*{Shade}\left(F\setminus\left\\{u\right\\}\right)$,
we obtain
$\operatorname*{Shade}\left(F\setminus\left\\{u\right\\}\right)=\operatorname*{Shade}F$.
This proves Statement 2.]

[Proof of Statement 1: Let $F\in\mathcal{P}\left(E\right)$ and $u\in
E\setminus\operatorname*{Shade}F$. We must prove that
$\operatorname*{Shade}\left(F\cup\left\\{u\right\\}\right)=\operatorname*{Shade}F$.
If $u\in F$, then this is obvious (since $F\cup\left\\{u\right\\}=F$ in this
case). Thus, we WLOG assume that $u\notin F$. Hence,
$\left(F\cup\left\\{u\right\\}\right)\setminus\left\\{u\right\\}=F$.

We have $F\subseteq F\cup\left\\{u\right\\}$ and thus
$\operatorname*{Shade}\left(F\cup\left\\{u\right\\}\right)\subseteq\operatorname*{Shade}F$
(by Statement 0).

Now, $u\in E\setminus\operatorname*{Shade}F\subseteq
E\setminus\operatorname*{Shade}\left(F\cup\left\\{u\right\\}\right)$ (since
$\operatorname*{Shade}\left(F\cup\left\\{u\right\\}\right)\subseteq\operatorname*{Shade}F$).
Hence, Statement 2 (applied to $F\cup\left\\{u\right\\}$ instead of $F$)
yields
$\operatorname*{Shade}F=\operatorname*{Shade}\left(F\cup\left\\{u\right\\}\right)$
(since $\left(F\cup\left\\{u\right\\}\right)\setminus\left\\{u\right\\}=F$).
This proves Statement 1.]

Now, we have proved Statements 1 and 2. Thus, the map
$\operatorname*{Shade}:\mathcal{P}\left(E\right)\rightarrow\mathcal{P}\left(E\right)$
is a shade map. Moreover, this map is inclusion-reversing (by Statement 0).
Thus, Theorem 4.18 is proved. ∎

We note that the quasi-closure operator $\tau$ in Theorem 4.18 can be
reconstructed from the map $\operatorname*{Shade}$. This does not even require
$\tau$ to be antimatroidal; the following holds for any quasi-closure
operator:

######  Proposition 4.21.

Let $E$ be a set. Let
$\tau:\mathcal{P}\left(E\right)\rightarrow\mathcal{P}\left(E\right)$ be a
quasi-closure operator on $E$. For any $F\subseteq E$, we define

$\operatorname*{Shade}F=\left\\{e\in E\ \mid\
e\notin\tau\left(F\setminus\left\\{e\right\\}\right)\right\\}.$

Then, each $F\subseteq E$ satisfies

$\tau\left(F\right)=F\cup\left(E\setminus\operatorname*{Shade}F\right).$ (11)

It turns out that if one applies the formula (11) to an inclusion-reversing
shade map $\operatorname*{Shade}$, then the resulting map $\tau$ is an
antimatroidal quasi-closure operator, at least when $E$ is finite. In fact, we
have the following:

######  Proposition 4.22.

Let $E$ be a finite set. Let
$\operatorname*{Shade}:\mathcal{P}\left(E\right)\rightarrow\mathcal{P}\left(E\right)$
be an inclusion-reversing shade map. Define a map
$\tau:\mathcal{P}\left(E\right)\rightarrow\mathcal{P}\left(E\right)$ by
setting

$\tau\left(F\right)=F\cup\left(E\setminus\operatorname*{Shade}F\right)$ (12)

for each $F\subseteq E$. Then, $\tau$ is an antimatroidal quasi-closure
operator on $E$.

The proof of this proposition rests on the following lemma:

######  Lemma 4.23.

Let $E$ be a set. Let
$\operatorname*{Shade}:\mathcal{P}\left(E\right)\rightarrow\mathcal{P}\left(E\right)$
be a shade map. Let $A$ and $B$ be two subsets of $E$ such that $B$ is finite
and $B\cap\operatorname*{Shade}A=\varnothing$. Then,
$\operatorname*{Shade}\left(A\cup B\right)=\operatorname*{Shade}A$.

Proposition 4.21 has a (sort of) converse:

######  Proposition 4.24.

Let $E$ be a set. Let
$\operatorname*{Shade}:\mathcal{P}\left(E\right)\rightarrow\mathcal{P}\left(E\right)$
be an inclusion-reversing shade map. For any $F\subseteq E$, we define

$\tau\left(F\right)=F\cup\left(E\setminus\operatorname*{Shade}F\right).$

Then, each $F\subseteq E$ satisfies

$\operatorname*{Shade}F=\left\\{e\in E\ \mid\
e\notin\tau\left(F\setminus\left\\{e\right\\}\right)\right\\}.$ (13)

Combining many of the results in this section, we obtain the following
description of inclusion-reversing shade maps:

######  Theorem 4.25.

Let $E$ be a finite set. Then, there is a bijection

$\displaystyle\text{from the set }\left\\{\text{inclusion-reversing shade maps
}\operatorname*{Shade}:\mathcal{P}\left(E\right)\rightarrow\mathcal{P}\left(E\right)\right\\}$
$\displaystyle\text{to the set }\left\\{\text{antimatroidal quasi-closure
operators
}\tau:\mathcal{P}\left(E\right)\rightarrow\mathcal{P}\left(E\right)\right\\}.$

It sends each map $\operatorname*{Shade}$ to the map $\tau$ defined by (12).
Its inverse map sends each map $\tau$ to the map $\operatorname*{Shade}$
defined by (10).

Theorem 4.25 classifies inclusion-reversing shade maps in terms of
antimatroidal quasi-closure operators333In the parlance of matroid theorists,
it shows that inclusion-reversing shade maps are _cryptomorphic_ to
antimatroidal quasi-closure operators.. The latter can in turn be described in
terms of antimatroidal closure operators (by Proposition 4.17), i.e., in terms
of antimatroids. Thus, inclusion-reversing shade maps “boil down” to
antimatroids. The same can be said of inclusion-preserving shade maps (because
Proposition 4.7 establishes a bijection between them and the inclusion-
reversing ones). In the next subsection, we shall classify arbitrary shade
maps in terms of what we will call _Boolean interval partitions_.

###  4.4 Boolean interval partitions and arbitrary shade maps

Let us first define Boolean interval partitions:

######  Definition 4.26.

Let $E$ be a set.

(a) If $U$ and $V$ are two subsets of $E$ satisfying $U\subseteq V$, then
$\left[U,V\right]$ shall denote the subset

$\left\\{I\in\mathcal{P}\left(E\right)\ \mid\ U\subseteq I\subseteq
V\right\\}$

of $\mathcal{P}\left(E\right)$. This is the set of all subsets of $E$ that lie
between $U$ and $V$ (meaning that they contain $U$ as a subset, but in turn
are contained in $V$ as subsets).

(b) A _Boolean interval_ of $\mathcal{P}\left(E\right)$ shall mean a subset of
$\mathcal{P}\left(E\right)$ that has the form $\left[U,V\right]$ for two
subsets $U$ and $V$ of $E$ satisfying $U\subseteq V$. Note that each Boolean
interval $\left[U,V\right]$ of $\mathcal{P}\left(E\right)$ is nonempty (as it
contains $U$ and $V$), and the two subsets $U$ and $V$ can easily be
reconstructed from it (namely, $U$ is the intersection of all
$I\in\left[U,V\right]$, whereas $V$ is the union of all
$I\in\left[U,V\right]$).

(c) A _Boolean interval partition_ of $\mathcal{P}\left(E\right)$ means a set
of pairwise disjoint Boolean intervals of $\mathcal{P}\left(E\right)$ whose
union is $\mathcal{P}\left(E\right)$.

(d) If $\mathbf{P}$ is a Boolean interval partition of
$\mathcal{P}\left(E\right)$, then the elements of $\mathbf{P}$ (that is, the
Boolean intervals that belong to $\mathbf{P}$) are called the _blocks_ of
$\mathbf{P}$.

######  Example 4.27.

For this example, let $E=\left\\{1,2,3\right\\}$. We shall use the shorthand
$i_{1}i_{2}\cdots i_{k}$ for a subset
$\left\\{i_{1},i_{2},\ldots,i_{k}\right\\}$ of $E$. (For example, $13$ means
the subset $\left\\{1,3\right\\}$.)

(a) We have

$\left[1,\ 123\right]=\left\\{I\in\mathcal{P}\left(123\right)\ \mid\
1\subseteq I\subseteq 123\right\\}=\left\\{1,\ 12,\ 13,\ 123\right\\}$

and

$\left[1,\ 13\right]=\left\\{I\in\mathcal{P}\left(123\right)\ \mid\ 1\subseteq
I\subseteq 13\right\\}=\left\\{1,\ 13\right\\}.$

(b) There are $3^{3}=27$ Boolean intervals of $\mathcal{P}\left(E\right)$.
(More generally, if $E$ is an $n$-element set, then there are $3^{n}$ Boolean
intervals of $\mathcal{P}\left(E\right)$.)

(c) Here is one of many Boolean interval partitions of
$\mathcal{P}\left(E\right)$ (where $E$ is still $\left\\{1,2,3\right\\}$):

$\left\\{\underbrace{\left\\{\varnothing\right\\}}_{=\left[\varnothing,\
\varnothing\right]},\ \ \underbrace{\left\\{1,\ 13\right\\}}_{=\left[1,\
13\right]},\ \ \underbrace{\left\\{3\right\\}}_{=\left[3,\ 3\right]},\ \
\underbrace{\left\\{2,\ 12,\ 23,\ 123\right\\}}_{=\left[2,\
123\right]}\right\\}.$

Here is another:

$\left\\{\underbrace{\left\\{\varnothing,\ 1\right\\}}_{=\left[\varnothing,\
1\right]},\ \ \underbrace{\left\\{3,\ 13\right\\}}_{=\left[3,\ 13\right]},\ \
\underbrace{\left\\{2,\ 23\right\\}}_{=\left[2,\ 23\right]},\ \
\underbrace{\left\\{12\right\\}}_{=\left[12,\ 12\right]},\ \
\underbrace{\left\\{123\right\\}}_{=\left[123,\ 123\right]}\right\\}.$

The former has four blocks; the latter has five.

Here are two ways to think of Boolean interval partitions of
$\mathcal{P}\left(E\right)$:

  * •

The following is just a slick restatement of Definition 4.26 (c) using
standard combinatorial lingo: A Boolean interval partition of
$\mathcal{P}\left(E\right)$ is a set partition of the Boolean lattice
$\mathcal{P}\left(E\right)$ into intervals.

  * •

It is well-known that the set partitions of a given set are in a canonical
bijection with the equivalence relations on this set. In light of this, the
Boolean interval partitions of $\mathcal{P}\left(E\right)$ can be viewed as
the equivalence relations on $\mathcal{P}\left(E\right)$ whose equivalence
classes are Boolean intervals. In other words, they can be viewed as the
equivalence relations $\sim$ on $\mathcal{P}\left(E\right)$ satisfying the
axiom “if $U,V,I\in\mathcal{P}\left(E\right)$ satisfy $U\sim V$ and $U\cap
V\subseteq I\subseteq U\cup V$, then $U\sim I\sim V$”. The reader can prove
this alternative characterization as an easy exercise in Boolean algebra.

Boolean interval partitions have come up in combinatorics before (e.g., Brunat
et al. (2009), Dawson (1981), Dedndreaj and Tittmann (2021), Gordon and
McMahon (1997)).

We shall now construct a shade map from any Boolean interval partition:

######  Theorem 4.28.

Let $E$ be a set. Let $\mathbf{P}$ be a Boolean interval partition of
$\mathcal{P}\left(E\right)$.

For any $F\in\mathcal{P}\left(E\right)$, let $\left[\alpha\left(F\right),\
\tau\left(F\right)\right]$ denote the (unique) block of $\mathbf{P}$ that
contains $F$.

We define a map
$\operatorname*{Shade}:\mathcal{P}\left(E\right)\rightarrow\mathcal{P}\left(E\right)$
by setting

$\operatorname*{Shade}F=E\setminus\left(\tau\left(F\right)\setminus\alpha\left(F\right)\right)\
\ \ \ \ \ \ \ \ \ \text{for any }F\in\mathcal{P}\left(E\right).$

Then:

(a) The map $\operatorname*{Shade}$ is a shade map on $E$.

(b) We have $\alpha\left(F\right)=F\cap\operatorname*{Shade}F$ and
$\tau\left(F\right)=F\cup\left(E\setminus\operatorname*{Shade}F\right)$ for
any $F\in\mathcal{P}\left(E\right)$.

(c) We have $\mathbf{P}=\left\\{\left[\alpha\left(F\right),\
\tau\left(F\right)\right]\ \mid\ F\in\mathcal{P}\left(E\right)\right\\}$.

The proof of Theorem 4.28 is rather easy. We lighten our burden somewhat with
a simple lemma (which can be easily checked using Venn diagrams):

######  Lemma 4.29.

Let $X$, $Y$, $Z$ and $E$ be four sets such that $X\subseteq Y\subseteq
Z\subseteq E$. Then:

(a) We have $Y\cup\left(Z\setminus X\right)=Z$.

(b) We have $Y\cap\left(E\setminus\left(Z\setminus X\right)\right)=X$.

###### of Theorem 4.28.

(a) We shall prove the following two statements:

> Statement 1: If $F\in\mathcal{P}\left(E\right)$ and $u\in
> E\setminus\operatorname*{Shade}F$, then
> $\operatorname*{Shade}\left(F\cup\left\\{u\right\\}\right)=\operatorname*{Shade}F$.

> Statement 2: If $F\in\mathcal{P}\left(E\right)$ and $u\in
> E\setminus\operatorname*{Shade}F$, then
> $\operatorname*{Shade}\left(F\setminus\left\\{u\right\\}\right)=\operatorname*{Shade}F$.

[Proof of Statement 1: Let $F\in\mathcal{P}\left(E\right)$ and $u\in
E\setminus\operatorname*{Shade}F$. We must prove that
$\operatorname*{Shade}\left(F\cup\left\\{u\right\\}\right)=\operatorname*{Shade}F$.

The definition of $\alpha\left(F\right)$ and $\tau\left(F\right)$ reveals that
$\left[\alpha\left(F\right),\ \tau\left(F\right)\right]$ is the (unique) block
of $\mathbf{P}$ that contains $F$. Thus, $\left[\alpha\left(F\right),\
\tau\left(F\right)\right]$ is a block of $\mathbf{P}$ and contains $F$.

The definition of $\operatorname*{Shade}$ yields
$\operatorname*{Shade}F=E\setminus\left(\tau\left(F\right)\setminus\alpha\left(F\right)\right)$.
Thus,
$E\setminus\operatorname*{Shade}F=\tau\left(F\right)\setminus\alpha\left(F\right)$
(since $\tau\left(F\right)\setminus\alpha\left(F\right)$ is a subset of $E$).
Now, $u\in
E\setminus\operatorname*{Shade}F=\tau\left(F\right)\setminus\alpha\left(F\right)$.
In other words, $u\in\tau\left(F\right)$ and $u\notin\alpha\left(F\right)$.

On the other hand, the Boolean interval $\left[\alpha\left(F\right),\
\tau\left(F\right)\right]$ contains $F$. In other words,
$\alpha\left(F\right)\subseteq F\subseteq\tau\left(F\right)$.

Now, set $F^{\prime}=F\cup\left\\{u\right\\}$. From
$F\subseteq\tau\left(F\right)$ and $u\in\tau\left(F\right)$, we thus obtain
$F^{\prime}\subseteq\tau\left(F\right)$. Combined with
$\alpha\left(F\right)\subseteq F\subseteq F^{\prime}$, this entails
$F^{\prime}\in\left[\alpha\left(F\right),\ \tau\left(F\right)\right]$. Hence,
$\left[\alpha\left(F\right),\ \tau\left(F\right)\right]$ is a block of
$\mathbf{P}$ that contains $F^{\prime}$ (since we already know that
$\left[\alpha\left(F\right),\ \tau\left(F\right)\right]$ is a block of
$\mathbf{P}$).

However, the definition of $\alpha\left(F^{\prime}\right)$ and
$\tau\left(F^{\prime}\right)$ shows that
$\left[\alpha\left(F^{\prime}\right),\ \tau\left(F^{\prime}\right)\right]$ is
the (unique) block of $\mathbf{P}$ that contains $F^{\prime}$. Since we know
that $\left[\alpha\left(F\right),\ \tau\left(F\right)\right]$ is a block of
$\mathbf{P}$ that contains $F^{\prime}$, we therefore conclude that
$\left[\alpha\left(F^{\prime}\right),\
\tau\left(F^{\prime}\right)\right]=\left[\alpha\left(F\right),\
\tau\left(F\right)\right]$. Hence, we have

$\alpha\left(F^{\prime}\right)=\alpha\left(F\right)\ \ \ \ \ \ \ \ \ \
\text{and}\ \ \ \ \ \ \ \ \ \ \tau\left(F^{\prime}\right)=\tau\left(F\right)$

(because a Boolean interval $\left[U,\ V\right]$ uniquely determines both $U$
and $V$). Now, the definition of $\operatorname*{Shade}$ yields

$\operatorname*{Shade}\left(F^{\prime}\right)=E\setminus\left(\underbrace{\tau\left(F^{\prime}\right)}_{=\tau\left(F\right)}\setminus\underbrace{\alpha\left(F^{\prime}\right)}_{=\alpha\left(F\right)}\right)=E\setminus\left(\tau\left(F\right)\setminus\alpha\left(F\right)\right)=\operatorname*{Shade}F.$

In view of $F^{\prime}=F\cup\left\\{u\right\\}$, this rewrites as
$\operatorname*{Shade}\left(F\cup\left\\{u\right\\}\right)=\operatorname*{Shade}F$.
This proves Statement 1.]

[Proof of Statement 2: Let $F\in\mathcal{P}\left(E\right)$ and $u\in
E\setminus\operatorname*{Shade}F$. We must prove that
$\operatorname*{Shade}\left(F\setminus\left\\{u\right\\}\right)=\operatorname*{Shade}F$.

We proceed exactly as in our above proof of Statement 1 up until the point
where we define $F^{\prime}$. Insead of setting
$F^{\prime}=F\cup\left\\{u\right\\}$, we now set
$F^{\prime}=F\setminus\left\\{u\right\\}$. Combining
$\alpha\left(F\right)\subseteq F$ with $u\notin\alpha\left(F\right)$, we
obtain $\alpha\left(F\right)\subseteq
F\setminus\left\\{u\right\\}=F^{\prime}$. Combining this with
$F^{\prime}=F\setminus\left\\{u\right\\}\subseteq
F\subseteq\tau\left(F\right)$, we see that
$F^{\prime}\in\left[\alpha\left(F\right),\ \tau\left(F\right)\right]$. From
this, we can obtain
$\operatorname*{Shade}\left(F^{\prime}\right)=\operatorname*{Shade}F$ by the
same argument that we used back in the proof of Statement 1. In view of
$F^{\prime}=F\setminus\left\\{u\right\\}$, this rewrites as
$\operatorname*{Shade}\left(F\setminus\left\\{u\right\\}\right)=\operatorname*{Shade}F$.
This proves Statement 2.]

Now, we have proved Statements 1 and 2. Thus, the map
$\operatorname*{Shade}:\mathcal{P}\left(E\right)\rightarrow\mathcal{P}\left(E\right)$
satisfies the two axioms in Definition 4.2. In other words, this map is a
shade map. This proves Theorem 4.28 (a).

(b) Let $F\in\mathcal{P}\left(E\right)$. We must prove that
$\alpha\left(F\right)=F\cap\operatorname*{Shade}F$ and
$\tau\left(F\right)=F\cup\left(E\setminus\operatorname*{Shade}F\right)$.

As in the above proof of Statement 1, we can see that
$\alpha\left(F\right)\subseteq F\subseteq\tau\left(F\right)$ and
$\operatorname*{Shade}F=E\setminus\left(\tau\left(F\right)\setminus\alpha\left(F\right)\right)$
and
$E\setminus\operatorname*{Shade}F=\tau\left(F\right)\setminus\alpha\left(F\right)$.
Hence, Lemma 4.29 (b) (applied to $X=\alpha\left(F\right)$ and $Y=F$ and
$Z=\tau\left(F\right)$) yields that
$F\cap\left(E\setminus\left(\tau\left(F\right)\setminus\alpha\left(F\right)\right)\right)=\alpha\left(F\right)$.
In view of
$\operatorname*{Shade}F=E\setminus\left(\tau\left(F\right)\setminus\alpha\left(F\right)\right)$,
this rewrites as $F\cap\operatorname*{Shade}F=\alpha\left(F\right)$. In other
words, $\alpha\left(F\right)=F\cap\operatorname*{Shade}F$.

Furthermore, Lemma 4.29 (a) (applied to $X=\alpha\left(F\right)$ and $Y=F$ and
$Z=\tau\left(F\right)$) yields that
$F\cup\left(\tau\left(F\right)\setminus\alpha\left(F\right)\right)=\tau\left(F\right)$.
In view of
$E\setminus\operatorname*{Shade}F=\tau\left(F\right)\setminus\alpha\left(F\right)$,
this rewrites as
$F\cup\left(E\setminus\operatorname*{Shade}F\right)=\tau\left(F\right)$. In
other words,
$\tau\left(F\right)=F\cup\left(E\setminus\operatorname*{Shade}F\right)$. Thus,
Theorem 4.28 (b) is proven.

(c) Each block of $\mathbf{P}$ has the form $\left[\alpha\left(F\right),\
\tau\left(F\right)\right]$ for some $F\in\mathcal{P}\left(E\right)$ (since it
is a Boolean interval, thus nonempty, therefore contains some
$F\in\mathcal{P}\left(E\right)$; but then it must be
$\left[\alpha\left(F\right),\ \tau\left(F\right)\right]$ for this $F$).
Conversely, any set of the form $\left[\alpha\left(F\right),\
\tau\left(F\right)\right]$ is a block of $\mathbf{P}$ (by the definition of
$\left[\alpha\left(F\right),\ \tau\left(F\right)\right]$). Combining these two
facts, we conclude that the blocks of $\mathbf{P}$ are precisely the sets of
the form $\left[\alpha\left(F\right),\ \tau\left(F\right)\right]$ with
$F\in\mathcal{P}\left(E\right)$. But this is precisely the claim of Theorem
4.28 (c). ∎

A converse to Theorem 4.28 is provided by the following theorem:

######  Theorem 4.30.

Let $E$ be a finite set. Let
$\operatorname*{Shade}:\mathcal{P}\left(E\right)\rightarrow\mathcal{P}\left(E\right)$
be a shade map on $E$. Define a map
$\alpha:\mathcal{P}\left(E\right)\rightarrow\mathcal{P}\left(E\right)$ by
setting

$\alpha\left(F\right)=F\cap\operatorname*{Shade}F\ \ \ \ \ \ \ \ \ \ \text{for
any }F\in\mathcal{P}\left(E\right).$

Define a map
$\tau:\mathcal{P}\left(E\right)\rightarrow\mathcal{P}\left(E\right)$ by
setting

$\tau\left(F\right)=F\cup\left(E\setminus\operatorname*{Shade}F\right)\ \ \ \
\ \ \ \ \ \ \text{for any }F\in\mathcal{P}\left(E\right).$

Let

$\mathbf{P}=\left\\{\left[\alpha\left(F\right),\ \tau\left(F\right)\right]\
\mid\ F\in\mathcal{P}\left(E\right)\right\\}.$

Then:

(a) We have $F\in\left[\alpha\left(F\right),\ \tau\left(F\right)\right]$ for
any $F\in\mathcal{P}\left(E\right)$.

(b) If $F\in\mathcal{P}\left(E\right)$ and $G\in\left[\alpha\left(F\right),\
\tau\left(F\right)\right]$, then $\left[\alpha\left(F\right),\
\tau\left(F\right)\right]=\left[\alpha\left(G\right),\
\tau\left(G\right)\right]$.

(c) The set $\mathbf{P}$ is a Boolean interval partition of
$\mathcal{P}\left(E\right)$.

(d) We have
$\operatorname*{Shade}F=E\setminus\left(\tau\left(F\right)\setminus\alpha\left(F\right)\right)$
for any $F\in\mathcal{P}\left(E\right)$.

To prove this theorem, we will need the following variant of Lemma 4.23:

######  Lemma 4.31.

Let $E$ be a set. Let
$\operatorname*{Shade}:\mathcal{P}\left(E\right)\rightarrow\mathcal{P}\left(E\right)$
be a shade map. Let $A$ and $B$ be two subsets of $E$ such that $B$ is finite
and $B\cap\operatorname*{Shade}A=\varnothing$. Then,
$\operatorname*{Shade}\left(A\setminus B\right)=\operatorname*{Shade}A$.

###### of Lemma 4.31.

Induction on $\left|B\right|$, using Axiom 2 from Definition 2.6. ∎

We will also use another simple set-theoretical lemma (easily checked using
Venn diagrams):

######  Lemma 4.32.

Let $E$ be a set. Let $X$ and $Y$ be two subsets of $E$. Then,

$E\setminus Y=\left(X\cup\left(E\setminus Y\right)\right)\setminus\left(X\cap
Y\right).$

###### of Theorem 4.30.

(a) Let $F\in\mathcal{P}\left(E\right)$. The definition of $\alpha$ yields
$\alpha\left(F\right)=F\cap\operatorname*{Shade}F\subseteq F$. The definition
of $\tau$ yields
$\tau\left(F\right)=F\cup\left(E\setminus\operatorname*{Shade}F\right)\supseteq
F$, so that $F\subseteq\tau\left(F\right)$. Thus,
$\alpha\left(F\right)\subseteq F\subseteq\tau\left(F\right)$. In other words,
$F\in\left[\alpha\left(F\right),\ \tau\left(F\right)\right]$. This proves
Theorem 4.30 (a).

(b) Let $F\in\mathcal{P}\left(E\right)$ and $G\in\left[\alpha\left(F\right),\
\tau\left(F\right)\right]$. From $G\in\left[\alpha\left(F\right),\
\tau\left(F\right)\right]$, we obtain $\alpha\left(F\right)\subseteq
G\subseteq\tau\left(F\right)$. Thus,
$G\subseteq\tau\left(F\right)=F\cup\left(E\setminus\operatorname*{Shade}F\right)$
(by the definition of $\tau$). From this, straightforward set-theoretical
reasoning leads to

$\left(G\setminus F\right)\cap\operatorname*{Shade}F=\varnothing.$ (14)

Furthermore, the definition of $\alpha$ yields
$F\cap\operatorname*{Shade}F=\alpha\left(F\right)\subseteq G$. From this,
straightforward set-theoretical reasoning leads to

$\left(F\setminus G\right)\cap\operatorname*{Shade}F=\varnothing.$ (15)

Hence, Lemma 4.31 (applied to $A=F$ and $B=F\setminus G$) yields
$\operatorname*{Shade}\left(F\setminus\left(F\setminus
G\right)\right)=\operatorname*{Shade}F$. In view of
$F\setminus\left(F\setminus G\right)=F\cap G$, this rewrites as
$\operatorname*{Shade}\left(F\cap G\right)=\operatorname*{Shade}F$. Hence,
(14) rewrites as

$\left(G\setminus F\right)\cap\operatorname*{Shade}\left(F\cap
G\right)=\varnothing.$

Thus, Lemma 4.23 (applied to $A=F\cap G$ and $B=G\setminus F$) yields
$\operatorname*{Shade}\left(\left(F\cap G\right)\cup\left(G\setminus
F\right)\right)=\operatorname*{Shade}\left(F\cap
G\right)=\operatorname*{Shade}F$. In view of $\left(F\cap
G\right)\cup\left(G\setminus F\right)=G$, this rewrites as

$\operatorname*{Shade}G=\operatorname*{Shade}F.$

By further set-theoretical reasoning, using the equalities (14) and (15) (and
nothing else specific to the sets $F$, $G$ and $\operatorname*{Shade}F$), we
can easily obtain

$F\cap\operatorname*{Shade}F=G\cap\operatorname*{Shade}F\ \ \ \ \ \ \ \ \ \
\text{and}\ \ \ \ \ \ \ \ \ \
F\cup\left(E\setminus\operatorname*{Shade}F\right)=G\cup\left(E\setminus\operatorname*{Shade}F\right).$

In view of

$\displaystyle\alpha\left(F\right)$
$\displaystyle=F\cap\operatorname*{Shade}F\ \ \ \ \ \ \ \ \ \ \text{and}\ \ \
\ \ \ \ \ \ \
\alpha\left(G\right)=G\cap\underbrace{\operatorname*{Shade}G}_{=\operatorname*{Shade}F}=G\cap\operatorname*{Shade}F\
\ \ \ \ \ \ \ \ \ \text{and}$ $\displaystyle\tau\left(F\right)$
$\displaystyle=F\cup\left(E\setminus\operatorname*{Shade}F\right)\ \ \ \ \ \ \
\ \ \ \text{and}\ \ \ \ \ \ \ \ \ \
\tau\left(G\right)=G\cup\left(E\setminus\underbrace{\operatorname*{Shade}G}_{=\operatorname*{Shade}F}\right)=G\cup\left(E\setminus\operatorname*{Shade}F\right),$

we can rewrite these two equalities as
$\alpha\left(F\right)=\alpha\left(G\right)$ and
$\tau\left(F\right)=\tau\left(G\right)$. Thus, $\left[\alpha\left(F\right),\
\tau\left(F\right)\right]=\left[\alpha\left(G\right),\
\tau\left(G\right)\right]$. Theorem 4.30 (b) is thus proven.

(c) Clearly, $\mathbf{P}$ is a set of Boolean intervals of
$\mathcal{P}\left(E\right)$. Moreover, the Boolean intervals
$\left[\alpha\left(F\right),\ \tau\left(F\right)\right]\in\mathbf{P}$ are
pairwise disjoint (because if two of these intervals have some element $G$ in
common, then Theorem 4.30 (b) yields that they must both equal
$\left[\alpha\left(G\right),\ \beta\left(G\right)\right]$), and their union is
$\mathcal{P}\left(E\right)$ (since every $F\in\mathcal{P}\left(E\right)$
satisfies $F\in\left[\alpha\left(F\right),\ \tau\left(F\right)\right]$ by
Theorem 4.30 (a)). Thus, $\mathbf{P}$ is a Boolean interval partition of
$\mathcal{P}\left(E\right)$. This proves Theorem 4.30 (c).

(d) Let $F\in\mathcal{P}\left(E\right)$. Then, Lemma 4.32 (applied to $X=F$
and $Y=\operatorname*{Shade}F$) yields

$E\setminus\operatorname*{Shade}F=\underbrace{\left(F\cup\left(E\setminus\operatorname*{Shade}F\right)\right)}_{\begin{subarray}{c}=\tau\left(F\right)\\\
\text{(since
}\tau\left(F\right)=F\cup\left(E\setminus\operatorname*{Shade}F\right)\text{)}\end{subarray}}\setminus\underbrace{\left(F\cap\operatorname*{Shade}F\right)}_{\begin{subarray}{c}=\alpha\left(F\right)\\\
\text{(since
}\alpha\left(F\right)=F\cap\operatorname*{Shade}F\text{)}\end{subarray}}=\tau\left(F\right)\setminus\alpha\left(F\right).$

However, $\operatorname*{Shade}F$ is a subset of $E$; thus,

$\operatorname*{Shade}F=E\setminus\underbrace{\left(E\setminus\operatorname*{Shade}F\right)}_{=\tau\left(F\right)\setminus\alpha\left(F\right)}=E\setminus\left(\tau\left(F\right)\setminus\alpha\left(F\right)\right).$

This proves Theorem 4.30 (d). ∎

Combining Theorem 4.28 with Theorem 4.30, we obtain the following:

######  Theorem 4.33.

Let $E$ be a finite set. Then, there is a bijection from the set

$\left\\{\text{shade maps
}\operatorname*{Shade}:\mathcal{P}\left(E\right)\rightarrow\mathcal{P}\left(E\right)\right\\}$

to the set

$\left\\{\text{Boolean interval partitions of
}\mathcal{P}\left(E\right)\right\\}.$

It sends each map $\operatorname*{Shade}$ to the Boolean interval partition
$\mathbf{P}$ defined in Theorem 4.30 (c). Its inverse map sends each Boolean
interval partition $\mathbf{P}$ to the map $\operatorname*{Shade}$ defined in
Theorem 4.28.

###### of Theorem 4.33.

This follows easily from Theorem 4.28 and Theorem 4.30. ∎

######  Question 4.34.

According to Theorem 4.18, any antimatroid gives rise to an inclusion-
reversing shade map, which in turn gives rise to a Boolean interval partition
by Theorem 4.30. Is this construction equivalent to the construction of a
Boolean interval partition from an antimatroid described by Gordon and McMahon
in (Gordon and McMahon, 1997, Theorem 2.5)?

##  5 The topological viewpoint

Now we return to the setting of Section 1. We aim to reinterpret Theorem 2.11
in the terms of combinatorial topology (specifically, finite simplicial
complexes) and strengthen it. We recall the definition of a _simplicial
complex_ :444We forget all the conventions we have introduced so far. (Thus,
for example, $E$ no longer means the edge set of a graph $\Gamma$.)

######  Definition 5.1.

Let $E$ be a finite set. A _simplicial complex_ on ground set $E$ means a
subset $\mathcal{A}$ of the power set of $E$ with the following property:

> If $P\in\mathcal{A}$ and $Q\subseteq P$, then $Q\in\mathcal{A}$.

Thus, in terms of posets, a simplicial complex on ground set $E$ means a down-
closed subset of the Boolean lattice on $E$. Note that a simplicial complex
contains the empty set $\varnothing$ unless it is empty itself.

We refer to Kozlov (2020) for context and theory about simplicial complexes.
We shall restrict ourselves to the few definitions relevant to what we will
prove. The following is straightforward to check:

######  Proposition 5.2.

Let us use the notations from Section 1 as well as Definition 2.6. Let $G$ be
any subset of $E$. Let

$\mathcal{A}=\left\\{F\subseteq E\ \mid\
G\not\subseteq\operatorname*{Shade}F\right\\}.$ (16)

Then, $\mathcal{A}$ is a simplicial complex on ground set $E$.

######  Example 5.3.

The following pictures illustrate this simplicial complex on an example.

$v$$c$$b$$f$$d$$a$$e$ $a$$b$$c$$d$$e$$f$

The left picture is a graph $\Gamma$ (with the vertex labelled $v$ playing the
role of $v$), whereas the right picture shows the corresponding simplicial
complex $\mathcal{A}$ for $G=E$ (that is, the simplicial complex whose faces
are the subsets of $E$ that are not pandemic).

To state the main result of this section, we need the following
definition555We continue using the definitions from Subsection 2.1, even
though $E$ is now just an arbitrary finite set.:

######  Definition 5.4.

Let $E$ be a finite set. Let $\mathcal{A}$ be a simplicial complex on ground
set $E$.

(a) A complete matching $\mu$ of $\mathcal{A}$ is said to be _acyclic_ if
there exists no tuple $\left(B_{1},B_{2},\ldots,B_{n}\right)$ of distinct sets
$B_{1},B_{2},\ldots,B_{n}\in\mathcal{A}$ with the property that $n\geq 2$ and
that

$\mu\left(B_{i}\right)\prec B_{i}\ \ \ \ \ \ \ \ \ \ \text{for each
}i\in\left\\{1,2,\ldots,n\right\\}$

and

$\mu\left(B_{i}\right)\prec B_{i+1}\ \ \ \ \ \ \ \ \ \ \text{for each
}i\in\left\\{1,2,\ldots,n-1\right\\}$

and

$\mu\left(B_{n}\right)\prec B_{1}.$

(b) The simplicial complex $\mathcal{A}$ is said to be _collapsible_ if it has
an acyclic complete matching.

Note that our definition of an “acyclic complete matching” is a particular
case of (Kozlov, 2020, Definition 10.7). Our notion of “collapsible” is
equivalent to the classical notion of “collapsible” (even though the latter is
usually defined differently) because of (Kozlov, 2020, Theorem 10.9).

We now claim:

######  Theorem 5.5.

Let us use the notations from Section 1 as well as Definition 2.6. Let $G$ be
any subset of $E$. Define $\mathcal{A}$ as in (16). Then, the simplicial
complex $\mathcal{A}$ is collapsible.

Collapsible simplicial complexes are well-behaved in various ways – in
particular, they are contractible ((Kozlov, 2020, Corollary 9.19)), and thus
have trivial homotopy and homology groups (in positive degrees). Moreover, the
reduced Euler characteristic of any collapsible simplicial complex is $0$ (for
obvious reasons: having a complete matching suffices, even if it is not
acyclic); thus, Theorem 2.11 follows from Theorem 5.5.

Our proof of Theorem 5.5 will rely on the following simple lemma (whose proof
is left as an exercise):

######  Lemma 5.6.

Let $X$ and $Y$ be two sets, and let $u\in X\cap Y$. If
$X\setminus\left\\{u\right\\}\prec Y$, then $X=Y$.

###### of Theorem 5.5.

We know from Proposition 5.2 that $\mathcal{A}$ is a simplicial complex. It
remains to show that $\mathcal{A}$ is collapsible.

Note that our $\mathcal{A}$ is precisely the set $\mathcal{A}$ defined in the
proof of Theorem 2.11 above.

We equip the finite set $E$ with a total order (chosen arbitrarily).

If $F\in\mathcal{A}$, then we define the edge $\varepsilon\left(F\right)\in
G\setminus\operatorname*{Shade}F$ as in the proof of Theorem 2.11.

We define a complete matching $\mu:\mathcal{A}\rightarrow\mathcal{A}$ of
$\mathcal{A}$ as in the proof of Theorem 2.11. We shall now prove that this
complete matching $\mu$ is acyclic.

Indeed, let $\left(B_{1},B_{2},\ldots,B_{n}\right)$ be a tuple of distinct
sets $B_{1},B_{2},\ldots,B_{n}\in\mathcal{A}$ with the property that $n\geq 2$
and that

$\mu\left(B_{i}\right)\prec B_{i}\ \ \ \ \ \ \ \ \ \ \text{for each
}i\in\left\\{1,2,\ldots,n\right\\}$ (17)

and

$\mu\left(B_{i}\right)\prec B_{i+1}\ \ \ \ \ \ \ \ \ \ \text{for each
}i\in\left\\{1,2,\ldots,n-1\right\\}$ (18)

and

$\mu\left(B_{n}\right)\prec B_{1}.$ (19)

We shall derive a contradiction.

Set $B_{n+1}=B_{1}$. Then, combining (18) with (19), we conclude that

$\mu\left(B_{i}\right)\prec B_{i+1}\ \ \ \ \ \ \ \ \ \ \text{for each
}i\in\left\\{1,2,\ldots,n\right\\}.$ (20)

We now claim the following:

> Claim 1: We have
> $\operatorname*{Shade}\left(B_{i}\right)\subseteq\operatorname*{Shade}\left(B_{i+1}\right)$
> for each $i\in\left\\{1,2,\ldots,n\right\\}$.

[Proof of Claim 1: Let $i\in\left\\{1,2,\ldots,n\right\\}$. From (17), we see
that $\mu\left(B_{i}\right)\prec B_{i}$, so that
$\varepsilon\left(B_{i}\right)\in B_{i}$ (by the definition of $\mu$). Set
$u=\varepsilon\left(B_{i}\right)$. Then, the definition of $\mu$ yields
$\mu\left(B_{i}\right)=B_{i}\setminus\left\\{u\right\\}$.

However, $u=\varepsilon\left(B_{i}\right)\in
G\setminus\operatorname*{Shade}\left(B_{i}\right)$ (by the definition of
$\varepsilon\left(B_{i}\right)$). In other words, $u\in G$ and
$u\notin\operatorname*{Shade}\left(B_{i}\right)$. Therefore, (6) (applied to
$F=B_{i}$) yields
$\operatorname*{Shade}\left(B_{i}\setminus\left\\{u\right\\}\right)=\operatorname*{Shade}\left(B_{i}\right)$.
This can be rewritten as
$\operatorname*{Shade}\left(\mu\left(B_{i}\right)\right)=\operatorname*{Shade}\left(B_{i}\right)$
(since $\mu\left(B_{i}\right)=B_{i}\setminus\left\\{u\right\\}$).

But (20) yields $\mu\left(B_{i}\right)\prec B_{i+1}$, so that
$\mu\left(B_{i}\right)\subseteq B_{i+1}$ and thus
$\operatorname*{Shade}\left(\mu\left(B_{i}\right)\right)\subseteq\operatorname*{Shade}\left(B_{i+1}\right)$
(by Lemma 2.8). In view of
$\operatorname*{Shade}\left(\mu\left(B_{i}\right)\right)=\operatorname*{Shade}\left(B_{i}\right)$,
this can be rewritten as
$\operatorname*{Shade}\left(B_{i}\right)\subseteq\operatorname*{Shade}\left(B_{i+1}\right)$.
This proves Claim 1.]

Claim 1 shows that
$\operatorname*{Shade}\left(B_{1}\right)\subseteq\operatorname*{Shade}\left(B_{2}\right)\subseteq\cdots\subseteq\operatorname*{Shade}\left(B_{n}\right)\subseteq\operatorname*{Shade}\left(B_{n+1}\right)$.
This chain of inclusions is circular (since $B_{n+1}=B_{1}$); thus, it must be
a chain of equalities. Hence,
$\operatorname*{Shade}\left(B_{n}\right)=\operatorname*{Shade}\left(B_{1}\right)$.
Thus, $\varepsilon\left(B_{n}\right)=\varepsilon\left(B_{1}\right)$ (since
$\varepsilon\left(F\right)$ depends only on $\operatorname*{Shade}F$, not on
$F$ itself).

Set $u=\varepsilon\left(B_{n}\right)$. Thus,
$u=\varepsilon\left(B_{n}\right)=\varepsilon\left(B_{1}\right)$.

We have $\mu\left(B_{n}\right)\prec B_{n}$ (by (17)); thus, the definition of
$\mu$ yields $\varepsilon\left(B_{n}\right)\in B_{n}$ and
$\mu\left(B_{n}\right)=B_{n}\setminus\left\\{\varepsilon\left(B_{n}\right)\right\\}=B_{n}\setminus\left\\{u\right\\}$
(since $\varepsilon\left(B_{n}\right)=u$).

However, $u=\varepsilon\left(B_{n}\right)\in B_{n}$ and similarly $u\in
B_{1}$. Thus, $u\in B_{n}\cap B_{1}$. Also,
$B_{n}\setminus\left\\{u\right\\}=\mu\left(B_{n}\right)\prec B_{1}$ (by (19)).
Hence, Lemma 5.6 (applied to $X=B_{n}$ and $Y=B_{1}$) yields $B_{n}=B_{1}$.
This contradicts the fact that the sets $B_{1},B_{2},\ldots,B_{n}$ are
distinct (since $n\geq 2$).

Forget that we fixed $\left(B_{1},B_{2},\ldots,B_{n}\right)$. We thus have
found a contradiction whenever $\left(B_{1},B_{2},\ldots,B_{n}\right)$ is a
tuple of distinct sets $B_{1},B_{2},\ldots,B_{n}\in\mathcal{A}$ with the
property that $n\geq 2$ and that (17) and (18) and (19). Hence, there exists
no such tuple. In other words, the complete matching $\mu$ is acyclic.
Therefore, the simplicial complex $\mathcal{A}$ is collapsible (by Definition
5.4 (b)). This finishes the proof of Theorem 5.5. ∎

The analogues of Proposition 5.2 and of Theorem 5.5 for vertex-infection
(instead of usual infection) also hold (with the same proofs). More generally,
Proposition 5.2 and Theorem 5.5 can be generalized to any inclusion-preserving
shade map:

######  Theorem 5.7.

Let $E$ be any set. Let
$\operatorname*{Shade}:\mathcal{P}\left(E\right)\rightarrow\mathcal{P}\left(E\right)$
be an inclusion-preserving shade map on $E$. Let $G$ be any subset of $E$. Let

$\mathcal{A}=\left\\{F\subseteq E\ \mid\
G\not\subseteq\operatorname*{Shade}F\right\\}.$

Then:

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

(b) This simplicial complex $\mathcal{A}$ is collapsible.

###### Proof.

Part (a) is a straightforward generalization of Proposition 5.2, while part
(b) is a straightforward generalization of Theorem 5.5. The proofs we gave
above generalize (mutatis mutandis). ∎

However, Theorem 5.7 cannot be lifted to the full generality of arbitrary
shade maps, since $\mathcal{A}$ will generally not be a simplicial complex
unless the shade map is inclusion-preserving. (However, for inclusion-
reversing shade maps, we can obtain a variant of Theorem 5.7 by applying
Theorem 5.7 to the dual shade map $\operatorname*{Shade}\nolimits^{\prime}$
from Proposition 4.7.)

##  6 Open questions

I shall now comment on two natural directions of research so far unexplored.

###  6.1 The Alexander dual

Any simplicial complex has an _Alexander dual_ , which is defined as follows:

######  Definition 6.1.

Let $E$ be a finite set. Let $\mathcal{A}$ be a simplicial complex on ground
set $E$. Then, we define a new simplicial complex $\mathcal{A}^{\vee}$ on
ground set $E$ by

$\mathcal{A}^{\vee}=\left\\{F\subseteq E\ \mid\ E\setminus
F\notin\mathcal{A}\right\\}.$

(That is, $\mathcal{A}^{\vee}$ consists of those subsets of $E$ whose
complements don’t belong to $\mathcal{A}$.) This simplicial complex
$\mathcal{A}^{\vee}$ is called the _Alexander dual_ of $\mathcal{A}$.

It is well-known that a simplicial complex $\mathcal{A}$ and its Alexander
dual $\mathcal{A}^{\vee}$ share many properties; in particular, the reduced
homology of $\mathcal{A}$ is isomorphic to the reduced cohomology of
$\mathcal{A}^{\vee}$ (see, e.g., (Björner and Tancer, 2009, Theorem 1.1)).
However, the collapsibility and the homotopy types of $\mathcal{A}$ and
$\mathcal{A}^{\vee}$ are not always related. Thus, the following question is
suggested but not answered by Theorem 5.5:

######  Question 6.2.

Let us use the notations from Section 1 as well as Definition 2.6. Let $G$ be
any subset of $E$. Define $\mathcal{A}$ as in (16). Is the simplicial complex

$\mathcal{A}^{\vee}=\left\\{F\subseteq E\ \mid\
G\subseteq\operatorname*{Shade}\left(E\setminus F\right)\right\\}$

collapsible? Is it contractible?

###  6.2 Several vertices $v$

Elser’s nuclei-based viewpoint in Elser (1984) (and (Dorpalen-Barry et al.,
2021, Conjecture 9.1)) suggests yet another question.

Our definition of $\operatorname*{Shade}F$ (Definition 2.6), and the
underlying notion of “infecting” an edge, implicitly relied on the choice of
vertex $v$. It thus is advisable to rename the set $\operatorname*{Shade}F$ as
$\operatorname*{Shade}\nolimits_{v}F$ and combine such sets for different
values of $v$. In particular, we can define

$\mathcal{A}_{U}=\left\\{F\subseteq E\ \mid\
G\not\subseteq\operatorname*{Shade}\nolimits_{v}F\text{ for some }v\in
U\right\\}$

for any subset $U$ of $V$. This $\mathcal{A}_{U}$ is a simplicial complex
(being the union of a family of simplicial complexes), and thus we can ask the
same questions about it as we did about $\mathcal{A}$:

######  Question 6.3.

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

For $G=E$ and $\left|U\right|>0$, this simplicial complex $\mathcal{A}_{U}$ is
the Alexander dual of the “$U$-nucleus complex” $\Delta_{U}^{G}$ from
(Dorpalen-Barry et al., 2021, Definition 3.2) (when $G$ is connected). If
(Dorpalen-Barry et al., 2021, Conjecture 9.1 for $\left|U\right|>1$) is
correct, then the homology of $\mathcal{A}_{U}$ with real coefficients should
be concentrated in a single degree; this suggests the possible existence of an
acyclic partial matching with all critical faces in one degree.

###### Acknowledgements.

I thank Anders Björner, Galen Dorpalen-Barry, Dmitry Feichtner-Kozlov,
Patricia Hersh, Sam Hopkins, Vic Reiner, Tom Roby and Richard Stanley for
insightful conversations. A referee has greatly simplified the proof of
Theorem 5.5. This research was supported through the programme “Oberwolfach
Leibniz Fellows” by the Mathematisches Forschungsinstitut Oberwolfach in 2020.
I am deeply grateful to the Institute for its hospitality during a none-too-
hospitable time.

## References

  * Benjamin and Quinn (2008) A. T. Benjamin and J. J. Quinn.  An alternate approach to alternating sums: A method to DIE for.  _The College Mathematics Journal_ , 39(3):191–202, 2008.  URL https://scholarship.claremont.edu/cgi/viewcontent.cgi?referer=&httpsredir=1&article=1581&context=hmc_fac_pub.
  * Björner and Tancer (2009) A. Björner and M. Tancer.  Combinatorial Alexander duality – a short and elementary proof.  _Discrete Comput Geom_ , 42:586–593, 2009.  10.1007/s00454-008-9102-x.
  * Brunat et al. (2009) J. M. Brunat, A. Guedes de Oliveira, and M. Noy.  Partitions of a finite boolean lattice into intervals.  _European Journal of Combinatorics_ , 30(8):1801–1809, Nov 2009.  ISSN 0195-6698.  10.1016/j.ejc.2008.12.010.  URL http://dx.doi.org/10.1016/j.ejc.2008.12.010.
  * Dawson (1981) J. E. Dawson.  A construction for a family of sets and its application to matroids.  In _L.L. MacAvaney (Ed.), Combinatorial Mathematics VIII (Geelong, 1980)_ , volume 884 of _Lect. Notes Math._ , pages 136–147. Springer, 1981.
  * Dedndreaj and Tittmann (2021) K. Dedndreaj and P. Tittmann.  On the activities and partitions of the vertex subsets of graphs, 2021\.  URL https://arxiv.org/abs/2008.02006v2.
  * Dorpalen-Barry et al. (2021) G. Dorpalen-Barry, C. Hettle, D. C. Livingston, J. L. Martin, G. D. Nasr, J. Vega, and H. Whitlatch.  A positivity phenomenon in Elser’s gaussian-cluster percolation model.  _Journal of Combinatorial Theory, Series A_ , 179:105364, Apr 2021.  ISSN 0097-3165.  10.1016/j.jcta.2020.105364.
  * Edelman and Jamison (1985) P. H. Edelman and R. E. Jamison.  The theory of convex geometries.  _Geometriae Dedicata_ , 19:247–270, 1985.  10.1007/BF00149365.
  * Elser (1984) V. Elser.  Gaussian-cluster models of percolation and self-avoiding walks.  _Journal of Physics A: Mathematical and General_ , 17(7):1515–1523, May 1984.  ISSN 1361-6447.  10.1088/0305-4470/17/7/019.  URL http://dx.doi.org/10.1088/0305-4470/17/7/019.
  * Gordon and McMahon (1997) G. Gordon and E. McMahon.  Interval partitions and activities for the greedoid tutte polynomial.  _Advances in Applied Mathematics_ , 18:33–49, 1997.
  * Grinberg (2021) D. Grinberg.  The Elser nuclei sum revisited (arxiv version v8), 2021.  URL http://arxiv.org/abs/2009.11527v8.
  * Korte et al. (1991) B. Korte, L. Lovász, and R. Schrader.  _Greedoids_.  Algorithms and Combinatorics #4. Springer, 1991.  10.1007/978-3-642-58191-5.
  * Kozlov (2020) D. N. Kozlov.  _Organized Collapse: An Introduction to Discrete Morse Theory_ , volume 207 of _Graduate Studies in Mathematics_.  AMS, 2020.  URL https://bookstore.ams.org/gsm-207.
  * Sagan (2020) B. Sagan.  _Combinatorics: The Art of Counting_ , volume 210 of _Graduate Studies in Mathematics_.  AMS, 2020.  URL https://users.math.msu.edu/users/bsagan/Books/Aoc/final.pdf.