\documentclass[12pt]{article}%
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage[margin=1in]{geometry}
\usepackage[hidelinks]{hyperref}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{tikz}%
\setcounter{MaxMatrixCols}{30}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Thursday, August 27, 2026 02:16:48}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{remark}[theorem]{Remark}
\theoremstyle{definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{definition}[theorem]{Definition}
\newcommand{\Pow}{\mathcal P}
\newcommand{\Free}{\operatorname{Free}}
\newcommand{\symdiff}{\mathbin{\triangle}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\begin{document}

\title{Collapsibility of Alexander duals for shade maps}
\author{GPT-5.6 Sol, edited by Darij Grinberg}
\date{\today}
\maketitle

\begin{abstract}
Let $E$ be a nonempty finite set. A shade map on $E$ is a map $T:\mathcal{P}%
(E)\rightarrow\mathcal{P}(E)$ such that toggling an element $u\notin T(F)$ in
the input $F$ does not change $T(F)$. We prove that, if $T$ is an
inclusion-reversing shade map and $G\subseteq E$, then the simplicial complex
\[
\{F\subseteq E\mid G\subseteq T(F)\}
\]
is collapsible. Equivalently, if $S$ is an inclusion-preserving shade map,
then the Alexander dual of
\[
\{F\subseteq E\mid G\not \subseteq S(F)\}
\]
is collapsible. This is an Alexander-dual companion to the shade-map
collapsibility theorem in \emph{The Elser nuclei sum revisited}.

The proof first matches all faces on which $T(F)\neq E$ by a toggle. The
remaining faces, characterized by $T(F)=E$, form the free convex set complex
of an associated antimatroidal quasi-closure operator. We give a
self-contained recursive acyclic matching on this complex. For ordinary convex
geometries, Korte--Lov\'{a}sz--Schrader prove the stronger fact that the free
convex set system is non-evasive. \medskip

\textbf{Manifest.} This note was written by GPT-5.6 Sol and subsequently
edited by myself and GPT over several iterations. I have verified the proof.
-- DG\footnote{This work is in the public domain.}

\end{abstract}

\section{Introduction and main results}

\label{sec:intro}

Shade maps were introduced in \cite{Grinberg21} as an abstraction of a
\textquotedblleft shade\textquotedblright\ operation implicit in a
graph-theoretical result of Elser. One of the main results proved there is
that an inclusion-preserving shade map produces a collapsible simplicial
complex; see \cite[Theorem~5.7]{Grinberg21}. The purpose of this note is to
prove the corresponding statement for the Alexander dual of this complex,
answering \cite[Question~6.2]{Grinberg21} affirmatively (since any collapsible
simplicial complex is contractible).

We recall the definition briefly and informally here; full conventions are
given in Section~\ref{sec:prelim}. We let $E$ be a finite set, and
$\mathcal{P}\left(  E\right)  $ be its power set. A map $T:\mathcal{P}%
(E)\rightarrow\mathcal{P}(E)$ is called a \emph{shade map} if
\[
u\notin T(F)\quad\Longrightarrow\quad T(F\mathbin{\triangle}\{u\})=T(F).
\]
Here the symbol $\mathbin{\triangle}$ denotes symmetric difference of sets;
thus, $F\mathbin{\triangle}\{u\}$ is obtained from $F$ by toggling the element
$u$ in/out.

For a simplicial complex $\Delta\subseteq\mathcal{P}(E)$, its Alexander dual
(relative to $E$) is the simplicial complex
\[
\Delta^{\vee}:=\{F\subseteq E\mid E\setminus F\notin\Delta\}.
\]
A finite complex is \emph{collapsible} if it admits an acyclic complete
matching. A known result in discrete Morse theory \cite[Theorem~10.9]%
{Kozlov20} identifies this with collapsibility by simplicial collapses to the
void complex; see also Definition~\ref{def:matching} below for our matching conventions.

Our main theorem can be stated in the inclusion-preserving form that is most
directly related to \cite{Grinberg21}.

\begin{theorem}
[Inclusion-preserving form]\label{thm:main-preserving} Let $E$ be a nonempty
finite set. Let
\[
S:\mathcal{P}(E)\longrightarrow\mathcal{P}(E)
\]
be an inclusion-preserving shade map, and let $G\subseteq E$ be any subset.
Set
\[
\mathcal{A}_{G}(S):=\{F\subseteq E\mid G\not \subseteq S(F)\}.
\]
Then $\mathcal{A}_{G}(S)$ is a simplicial complex, and its Alexander dual
\[
\mathcal{A}_{G}(S)^{\vee}=\{F\subseteq E\mid G\subseteq S(E\setminus F)\}
\]
is collapsible.
\end{theorem}

For the proof, however, it is cleaner not to carry the complement $E\setminus
F$ through every formula. We therefore prove first the following equivalent
result for inclusion-reversing shade maps.

\begin{theorem}
[Inclusion-reversing form]\label{thm:main-reversing} Let $E$ be a nonempty
finite set. Let%
\[
T:\mathcal{P}(E)\longrightarrow\mathcal{P}(E)
\]
be an inclusion-reversing shade map, and let $G\subseteq E$. Then
\begin{equation}
\mathcal{B}_{G}(T):=\{F\subseteq E\mid G\subseteq T(F)\} \label{eq:BGT}%
\end{equation}
is a collapsible simplicial complex.
\end{theorem}

Theorem~\ref{thm:main-reversing} is proved in
Section~\ref{sec:proof-reversing}. Theorem~\ref{thm:main-preserving} then
follows in a few lines by replacing $T(F)$ with $S(E\setminus F)$; see
Section~\ref{sec:preserving}.

The proof is entirely elementary and self-contained, but it is inspired by
abstract convex geometry and implicitly involves antimatroids and their free
convex sets. Convex geometries and antimatroids are equivalent descriptions of
the same structures: in the feasible-set convention for antimatroids, the
feasible sets are the complements of the closed sets of the convex geometry.
For background, see Edelman--Jamison \cite{EdelmanJamison85} and
Korte--Lov\'{a}sz--Schrader \cite[Chapter~III]{KLS91}.

There is a terminological point that will matter below.
Korte--Lov\'{a}sz--Schrader distinguish \emph{free sets} from \emph{free
convex sets}; our distinguished faces are the latter, not the former. We
verify the equivalence of the two descriptions in
Proposition~\ref{prop:KLS-free-convex}. Later literature often uses the
shorter phrase ``free complex'' for the simplicial complex of free convex
sets. The topology of these complexes and related complexes has been studied
in several places; see Korte--Lov\'{a}sz--Schrader \cite[Chapter~XII]{KLS91},
Edelman--Reiner \cite{EdelmanReiner00}, Kashiwabara--Nakamura
\cite{KashiwabaraNakamura05}, Hachimori--Kashiwabara
\cite{HachimoriKashiwabara07}, and Okamoto \cite{Okamoto08}.
Korte--Lov\'{a}sz--Schrader prove that the free convex set system of an
antimatroid is \emph{non-evasive} \cite[Theorem~XII.2.13]{KLS91}; in
decision-tree language, this means that membership of an unknown subset can be
decided, in the worst case, without querying every ground-set element.
Non-evasiveness implies collapsibility \cite[Chapter~10, Exercise~4(b)]%
{Kozlov20}. We nevertheless give a direct acyclic-matching proof, both to keep
the present argument self-contained and to accommodate the loop-allowing
quasi-closure operators that arise naturally from shade maps.

For background on acyclic matchings and discrete Morse theory, we refer to
Forman \cite{Forman98} and, especially, to Kozlov's book \cite[Chapters~9--11]%
{Kozlov20}, whose matching conventions are close to those used here.

\begin{remark}
[Why the hypothesis $E\neq\varnothing$ appears]If $E=\varnothing$ in Theorem
\ref{thm:main-reversing}, then necessarily $G=\varnothing$ and $\mathcal{B}%
_{G}(T)=\{\varnothing\}$. This one-face complex has no complete matching,
hence is not collapsible. Thus the $E\neq\varnothing$ assumption is needed in
Theorem \ref{thm:main-reversing}.
\end{remark}

\section{Shade maps and acyclic matchings}

\label{sec:prelim}

Throughout the paper, $E$ is a finite set and $\mathcal{P}(E)$ is its power
set. For $F\subseteq E$ and $u\in E$, write
\[
F\mathbin{\triangle}\{u\}=%
\begin{cases}
F\cup\{u\}, & \text{if }u\notin F;\\
F\setminus\{u\}, & \text{if }u\in F.
\end{cases}
\]
Thus, $F\mathbin{\triangle}\{u\}$ is obtained from the set $F$ by
\emph{toggling} the element $u$ (that is, inserting $u$ if $u$ is not in $F$,
and removing $u$ if $u$ is in $F$).

\begin{definition}
[Shade map]\label{def:shade} A map $T:\mathcal{P}(E)\rightarrow\mathcal{P}(E)$
is a \emph{shade map} if, for every $F\subseteq E$ and every $u\in E$, the
implication
\begin{equation}
u\notin T(F)\quad\Longrightarrow\quad T(F\mathbin{\triangle}\{u\})=T(F)
\label{eq:shade-axiom}%
\end{equation}
holds. It is \emph{inclusion-preserving} if
\[
A\subseteq B\quad\Longrightarrow\quad T(A)\subseteq T(B),
\]
and \emph{inclusion-reversing} if
\[
A\subseteq B\quad\Longrightarrow\quad T(A)\supseteq T(B).
\]

\end{definition}

This definition is equivalent to \cite[Definition 4.2]{Grinberg21}, even
though it differs in its wording. Indeed, \cite[Definition 4.2]{Grinberg21}
uses the two axioms%
\begin{equation}
u\notin T(F)\quad\Longrightarrow\quad T(F\cup\{u\})=T(F)
\label{eq:shade-axiom+}%
\end{equation}
and%
\begin{equation}
u\notin T(F)\quad\Longrightarrow\quad T(F\setminus\{u\})=T(F)
\label{eq:shade-axiom-}%
\end{equation}
instead of our axiom \eqref{eq:shade-axiom}. These two axioms (together) are
equivalent to \eqref{eq:shade-axiom}: Indeed, when $u\notin F$, the axiom
\eqref{eq:shade-axiom+} is equivalent to \eqref{eq:shade-axiom} while the
axiom \eqref{eq:shade-axiom-} is a tautology; on the other hand, when $u\in
F$, the axiom \eqref{eq:shade-axiom-} is equivalent to \eqref{eq:shade-axiom}
while the axiom \eqref{eq:shade-axiom+} is a tautology.

We shall repeatedly use the following finite version of toggling several
unshaded elements at once.

\begin{lemma}
\label{lem:add-many} Let $T$ be a shade map, and let $A,B\subseteq E$ satisfy
$B\cap T(A)=\varnothing$. Then
\[
T(A\cup B)=T(A).
\]

\end{lemma}

\begin{proof}
Induct on $|B\setminus A|$. If $B\subseteq A$, there is nothing to prove
(since $A\cup B=A$). Otherwise choose $u\in B\setminus A$. Thus, $u\in B$, so
that $u\notin T(A)$ (since $B\cap T(A)=\varnothing$). Therefore,
\eqref{eq:shade-axiom+} gives $T(A\cup\{u\})=T(A)$. Hence, $B\cap
T(A\cup\{u\})=B\cap T\left(  A\right)  =\varnothing$, so we can apply the
induction hypothesis to $A\cup\left\{  u\right\}  $ instead of $A$; this
results in $T(A\cup\left\{  u\right\}  \cup B)=T(A)$. Since $\left\{
u\right\}  \cup B=B$, this rewrites as $T(A\cup B)=T(A)$, and so the induction
step is complete.
\end{proof}

We refer to the inclusion-reversing and inclusion-preserving conditions as
\emph{monotonicities}. Input complementation exchanges the two monotonicity directions.

\begin{lemma}
[Input complementation]\label{lem:input-complement} Let $S:\mathcal{P}%
(E)\rightarrow\mathcal{P}(E)$ be a shade map, and define a new map
$T:\mathcal{P}\left(  E\right)  \rightarrow\mathcal{P}\left(  E\right)  $ by
\begin{equation}
T(F):=S(E\setminus F)\ \ \ \ \ \ \ \ \ \ \text{for all }F\subseteq E.
\label{eq:T-from-S}%
\end{equation}
Then $T$ is a shade map. Moreover, $T$ is inclusion-reversing if and only if
$S$ is inclusion-preserving.
\end{lemma}

\begin{proof}
If $u\notin T(F)=S(E\setminus F)$, then the shade-map axiom
\eqref{eq:shade-axiom} for $S$ gives
\[
S\bigl((E\setminus F)\mathbin{\triangle}\{u\}\bigr)=S(E\setminus F).
\]
Since
\[
(E\setminus F)\mathbin{\triangle}\{u\}=E\setminus(F\mathbin{\triangle}\{u\}),
\]
this says $T(F\mathbin{\triangle}\{u\})=T(F)$. Thus $T$ is a shade map. The
assertion about monotonicity follows immediately from the fact that
$A\subseteq B$ implies $E\setminus A\supseteq E\setminus B$.
\end{proof}

We next fix our simplicial-complex and matching terminology. Subsets of
$\mathcal{P}\left(  E\right)  $ will be called \emph{families}. A family
$\Delta\subseteq\mathcal{P}(E)$ is \emph{down-closed} if
\[
F\in\Delta,\quad F^{\prime}\subseteq F\quad\Longrightarrow\quad F^{\prime}%
\in\Delta.
\]
A \emph{simplicial complex on $E$} means a down-closed family $\Delta
\subseteq\mathcal{P}(E)$. We allow the empty family, which we call the
\emph{void complex}. The sets $F$ that belong to a simplicial complex $\Delta$
are called the \emph{faces} of $\Delta$. If $A,B\subseteq E$, write $A\lessdot
B$ when $A\subset B$ and $|B|=|A|+1$ (that is, $B=A\cup\left\{  b\right\}  $
for some $b\in B\setminus A$); in this case we say that $B$ \emph{covers} $A$.
(The relation $\lessdot$ is denoted by $\prec$ in \cite{Grinberg21}.)

\begin{definition}
[Acyclic matching]\label{def:matching} Let $\Delta$ be a simplicial complex. A
\emph{partial matching} on $\Delta$ is a map $\mu:M\rightarrow M$ on a subset
$M\subseteq\Delta$ such that every $F\in M$ satisfies
\[
\mu(\mu(F))=F
\]
(that is, $\mu$ is an involution) and%
\[
\text{either }F\lessdot\mu(F)\text{ or }\mu(F)\lessdot F
\]
(that is, $\mu$ affects each face by merely toggling an element). This
matching is \emph{complete} if $M=\Delta$ (so that $\mu$ is a map
$\Delta\rightarrow\Delta$).

An element $B\in M$ is an \emph{upper face} if $\mu(B)\lessdot B$; in this
case write $\mu^{-}(B):=\mu(B)$. The matching is \emph{acyclic} if there is no
sequence of distinct upper faces $B_{1},\ldots,B_{r}$, with $r\geq2$, such
that
\[
\mu^{-}(B_{1})\lessdot B_{2},\quad\mu^{-}(B_{2})\lessdot B_{3},\quad
\ldots,\quad\mu^{-}(B_{r})\lessdot B_{1}.
\]
Such a sequence $B_{1},\ldots,B_{r}$ is called an \emph{alternating cycle} of
upper faces. So a matching is acyclic if and only if it has no alternating
cycle of upper faces.
\end{definition}

Our definition of an acyclic complete matching is the same as that in the
published version of \cite[Definition 5.4]{Grinberg21}.\footnote{The detailed
arXiv version of \cite[Definition 5.4]{Grinberg21} uses a different
definition, in which the complete matching is not a map on all of $\Delta$ but
a bijection from $\left\{  \text{upper faces}\right\}  $ to $\left\{
\text{lower faces}\right\}  $; but this is easily seen to be equivalent, since
combining the latter bijection with its inverse gives a map $\Delta
\rightarrow\Delta$. Neither version of \cite[Definition 5.4]{Grinberg21}
considers non-complete partial matchings.}

We call a finite simplicial complex \emph{collapsible} if it admits an acyclic
complete matching. By a classical result in discrete Morse theory
\cite[Theorem~10.9]{Kozlov20}, this is equivalent to his definition of
collapsibility by a sequence of simplicial collapses to the void complex
\cite[Definition~9.3]{Kozlov20}. Thus all collapsibility statements below are
proved by constructing acyclic complete matchings.

\section{From an inclusion-reversing shade map to an antimatroidal
quasi-closure operator}

\label{sec:shade-convex}

We use a loop-allowing variant of the usual closure-operator definition of a
convex geometry (\cite[Definition 4.12]{Grinberg21}):

\begin{definition}
\label{def:quasiclosure} A map $\tau:\mathcal{P}(E)\rightarrow\mathcal{P}(E)$
is a \emph{quasi-closure operator} if it satisfies the following three
axioms:
\begin{align*}
\text{\emph{Extensivity:}}\qquad &  A\subseteq\tau(A),\\
\text{\emph{Monotonicity:}}\qquad &  A\subseteq B\Longrightarrow
\tau(A)\subseteq\tau(B),\\
\text{\emph{Idempotence:}}\qquad &  \tau(\tau(A))=\tau(A).
\end{align*}
This operator $\tau$ is said to be \emph{antimatroidal} if it also satisfies
the \emph{anti-exchange axiom}: whenever $X\subseteq E$ and $y,z$ are distinct
elements of $E\setminus\tau(X)$, the implication
\begin{equation}
z\in\tau(X\cup\{y\})\quad\Longrightarrow\quad y\notin\tau(X\cup\{z\})
\label{eq:anti-exchange}%
\end{equation}
holds. A subset $C\subseteq E$ is called \emph{closed}\footnote{Some authors
(particularly in the context of convex geometries) also call such subsets
``\emph{convex}''.} (with respect to $\tau
$) if $\tau(C)=C$. If $\tau(\varnothing)=\varnothing$, then the quasi-closure
operator $\tau$ is called a \emph{closure operator}. An antimatroidal closure
operator is the usual closure-operator definition of a finite convex geometry.
\end{definition}

For the standard terminology and its equivalence with antimatroids, see
\cite[Chapter~III, Section~1]{KLS91} and \cite{EdelmanJamison85}. An element
of $\tau(\varnothing)$ will be called a \emph{loop}. Thus, allowing
$\tau(\varnothing)\neq\varnothing$ allows loops; this variant is convenient
because it is closed under the contractions used below.

The next proposition is the shade-map/convex-geometry bridge needed in the
proof. It is a self-contained version of the corresponding construction in
\cite[Section~4]{Grinberg21}.

\begin{proposition}
\label{prop:tau-from-T} Let $T:\mathcal{P}(E)\rightarrow\mathcal{P}(E)$ be an
inclusion-reversing shade map, and define a map $\tau:\mathcal{P}%
(E)\rightarrow\mathcal{P}(E)$ by setting
\begin{equation}
\tau(F):=F\cup\bigl(E\setminus T(F)\bigr)\qquad\text{for each }F\subseteq E.
\label{eq:tau-from-T}%
\end{equation}
Then $\tau$ is an antimatroidal quasi-closure operator. Moreover,
\begin{equation}
T(F)=\bigl\{e\in E\mid e\notin\tau(F\setminus\{e\})\bigr\}\qquad\text{for each
}F\subseteq E. \label{eq:recover-T}%
\end{equation}

\end{proposition}

\begin{proof}
We first show that $\tau$ is a quasi-closure operator. Indeed, extensivity of
$\tau$ is immediate from \eqref{eq:tau-from-T}. If $A\subseteq B$, then
$T(A)\supseteq T(B)$ because $T$ is inclusion-reversing, and hence
\[
E\setminus T(A)\subseteq E\setminus T(B).
\]
Together with $A\subseteq B$, this yields $\tau(A)\subseteq\tau(B)$. Thus
$\tau$ is monotone. To prove idempotence, Lemma~\ref{lem:add-many}, applied
with $B=E\setminus T(A)$, gives
\[
T\bigl(A\cup(E\setminus T(A))\bigr)=T(A).
\]
The set inside $T$ on the left is $\tau(A)$, so $T(\tau(A))=T(A)$. Therefore
\begin{align*}
\tau(\tau(A))  &  =\tau(A)\cup\bigl(E\setminus T(\tau(A))\bigr)\\
&  =\tau(A)\cup\bigl(E\setminus T(A)\bigr)=\tau(A)
\end{align*}
(since $\tau\left(  A\right)  =A\cup\bigl(E\setminus T(A)\bigr)\supseteq
E\setminus T(A)$). Thus $\tau$ is a quasi-closure operator.

We next verify the anti-exchange axiom (\ref{eq:anti-exchange}). Let
$X\subseteq E$, and let $y,z$ be distinct elements of $E\setminus\tau(X)$ such
that $z\in\tau(X\cup\{y\})$. Suppose, for contradiction, that also $y\in
\tau(X\cup\{z\})$. Since $y,z\notin\tau(X)=X\cup(E\setminus T(X))$, we have
\begin{equation}
y,z\notin X\quad\text{and}\quad y,z\in T(X). \label{eq:yz-in-TX}%
\end{equation}
Hence, $z\notin X\cup\{y\}$ (since $z\notin X$ and $z\neq y$), while $z\in
\tau(X\cup\{y\})=(X\cup\{y\})\cup\bigl(E\setminus T(X\cup\{y\})\bigr)$ by
\eqref{eq:tau-from-T}. This forces $z\in E\setminus T(X\cup\{y\})$, so that
\begin{equation}
z\notin T(X\cup\{y\}). \label{eq:z-not-TXy}%
\end{equation}
Since $y$ and $z$ play analogous roles, we similarly find
\begin{equation}
y\notin T(X\cup\{z\}). \label{eq:y-not-TXz}%
\end{equation}
Set $W=X\cup\{y,z\}$. Then, $W=\left(  X\cup\left\{  y\right\}  \right)
\cup\left\{  z\right\}  $; hence,%
\[
T(W)=T((X\cup\left\{  y\right\}  )\cup\left\{  z\right\}  )=T(X\cup
\{y\})\ \ \ \ \ \ \ \ \ \ \left(  \text{by (\ref{eq:shade-axiom+}) and
\eqref{eq:z-not-TXy}}\right)  .
\]
Similarly, using \eqref{eq:y-not-TXz}, we find%
\[
T(W)=T(X\cup\{z\}).
\]
Consequently,
\begin{equation}
T(X\cup\{y\})=T\left(  W\right)  =T(X\cup\{z\}). \label{eq:two-shades-equal}%
\end{equation}
This allows us to rewrite \eqref{eq:z-not-TXy} as $z\notin T(X\cup\{z\})$.
Therefore, \eqref{eq:shade-axiom-} yields $T\left(  (X\cup\{z\})\setminus
\left\{  z\right\}  \right)  =T(X\cup\{z\})$. Since $(X\cup\{z\})\setminus
\left\{  z\right\}  =X$ (because $z\notin X$), this rewrites as
\[
T(X)=T(X\cup\{z\}).
\]
Hence, $z\notin T(X\cup\{z\})$ rewrites further as $z\notin T\left(  X\right)
$. This contradicts \eqref{eq:yz-in-TX}. Hence anti-exchange holds. So we have
shown that the quasi-closure operator $\tau$ is antimatroidal.

It remains to prove \eqref{eq:recover-T}. Fix $F\subseteq E$ and $e\in E$. We
must prove that $e\in T\left(  F\right)  $ if and only if $e\notin%
\tau(F\setminus\{e\})$. We prove the two directions of this equivalence separately:

$\Longrightarrow:$ If $e\in T(F)$, then, since $F\setminus\{e\}\subseteq F$
and $T$ is inclusion-reversing, we also have
\[
e\in T(F\setminus\{e\}).
\]
Also $e\notin F\setminus\{e\}$. Formula \eqref{eq:tau-from-T} therefore shows
that $e\notin\tau(F\setminus\{e\})$.

$\Longleftarrow:$ We prove this implication by contraposition. Suppose that
$e\notin T(F)$. Then, (\ref{eq:shade-axiom-}) yields $T(F\setminus
\{e\})=T(F)$, so that $e\notin T\left(  F\right)  =T(F\setminus\{e\})$. That
is, $e\in E\setminus T(F\setminus\{e\})$. Therefore, $e\in\tau(F\setminus
\{e\})$ by \eqref{eq:tau-from-T}.

Thus, \eqref{eq:recover-T} is proved.
\end{proof}

\section{Free convex set complexes}

\label{sec:free}

The following definition is visibly inspired by the geometry of convex sets:

\begin{definition}
[Free convex set]\label{def:free} Let $\tau$ be a quasi-closure operator on
$E$. An element $u\in F$ is \emph{extreme in $F$} if
\[
u\notin\tau(F\setminus\{u\}).
\]
A subset $F\subseteq E$ is a \emph{free convex set} (with respect to $\tau$)
if it is closed, i.e.
\begin{equation}
\tau(F)=F, \label{eq:free-closed}%
\end{equation}
and every $u\in F$ is extreme in $F$, i.e.
\begin{equation}
u\notin\tau(F\setminus\{u\}) \qquad\text{for all }u\in F.
\label{eq:free-independent}%
\end{equation}
We write $\operatorname{Free}(\tau)$ for the family of all free convex sets.
\end{definition}

\begin{lemma}
\label{lem:free-complex} Let $\tau$ be a quasi-closure operator on $E$. Then,
the family $\operatorname{Free}(\tau)$ is a simplicial complex, possibly void.
\end{lemma}

\begin{proof}
Let $F$ be a free convex set and let $A\subseteq F$. We must show that $A$ is
free convex as well.

First, if $a\in A$, then $A\setminus\{a\}\subseteq F\setminus\{a\}$, so
monotonicity gives
\[
\tau(A\setminus\{a\})\subseteq\tau(F\setminus\{a\}).
\]
Since $a\notin\tau(F\setminus\{a\})$ by the freeness of $F$, we thus have
$a\notin\tau(A\setminus\{a\})$.

It remains to show that $A$ is closed. Since $A\subseteq\tau\left(  A\right)
$ is automatic, we must only show that $\tau\left(  A\right)  \subseteq A$.
Assume the contrary. Thus, there exists an $x\in\tau\left(  A\right)  $ such
that $x\notin A$. By monotonicity, $\tau(A)\subseteq\tau(F)=F$ (since $F$ is
free convex). Hence, $x\in\tau\left(  A\right)  \subseteq F$. Since $F$ is
free convex, this entails $x\notin\tau\left(  F\setminus\left\{  x\right\}
\right)  $. But $A\subseteq F$ and thus $A\subseteq F\setminus\{x\}$ (since
$x\notin A$). Monotonicity then gives $x\in\tau(A)\subseteq\tau(F\setminus
\{x\})$, contradicting $x\notin\tau\left(  F\setminus\left\{  x\right\}
\right)  $.

Thus we have shown that $\tau\left(  A\right)  \subseteq A$. Hence $\tau
(A)=A$, and $A$ is a free convex set.
\end{proof}

By Lemma~\ref{lem:free-complex}, we know that $\operatorname{Free}(\tau)$ is a
simplicial complex; we call it the \emph{free convex set complex} of $\tau$.

\begin{example}
[A two-dimensional free convex set complex]\label{exa:four-points} Let
$a,b,c,p$ be four points in the plane, where $a,b,c$ are the vertices of a
nondegenerate triangle and $p$ lies strictly inside this triangle. Set
$E=\{a,b,c,p\}$ and
\[
\tau(F):=E\cap\operatorname{conv}(F)\qquad\text{for all }F\subseteq E,
\]
where $\operatorname{conv}(\varnothing)=\varnothing$. This is the standard
point-convexity example of a convex geometry; see, e.g.,
\cite{EdelmanJamison85}.

The only proper subset of $E$ that is not closed is $\{a,b,c\}$, since its
convex hull contains $p$. The whole set $E$ is closed, but it is not free
convex because $p$ is not extreme in $E$. All other subsets of $E$ are free
convex. Consequently, the free convex set complex is
\[
\operatorname{Free}(\tau)=\mathcal{P}(E)\setminus\bigl\{\{a,b,c\},E\bigr\},
\]
and its facets are
\[
\{a,b,p\},\qquad\{b,c,p\},\qquad\{c,a,p\}.
\]
Thus the free convex set complex is the two-dimensional simplicial disk shown
in Figure~\ref{fig:four-points-free}. In particular, it gives a small visual
example of Theorem~\ref{thm:free-collapsible}.

\begin{figure}[th]
\centering\begin{tikzpicture}[scale=1.05]
\coordinate (a) at (0,0);
\coordinate (b) at (4,0);
\coordinate (c) at (1.3,3);
\coordinate (p) at (1.8,1.15);
\fill[black!8] (a)--(b)--(p)--cycle;
\fill[black!8] (b)--(c)--(p)--cycle;
\fill[black!8] (c)--(a)--(p)--cycle;
\draw (a)--(b)--(c)--cycle;
\draw (a)--(p)--(b);
\draw (p)--(c);
\fill (a) circle (1.5pt) node[below left] {$a$};
\fill (b) circle (1.5pt) node[below right] {$b$};
\fill (c) circle (1.5pt) node[above] {$c$};
\fill (p) circle (1.5pt) node[above right] {$p$};
\end{tikzpicture}\caption{The free convex set complex in
Example~\ref{exa:four-points}. Its three two-dimensional faces are $abp$,
$bcp$, and $cap$.}%
\label{fig:four-points-free}%
\end{figure}
\end{example}

Our definition of a free convex set complex agrees with
Korte--Lov\'{a}sz--Schrader when $\tau$ is an ordinary convex geometry (i.e.,
antimatroidal closure operator), but this is not entirely obvious because
their term \emph{free set} by itself means something weaker. The following
proposition (which will not be used in what follows and thus can be skipped by
the uninterested reader) codifies this equivalence:

\begin{proposition}
[Comparison with Korte--Lov\'{a}sz--Schrader]\label{prop:KLS-free-convex}
Assume that $\tau$ is an antimatroidal closure operator on $E$, and let
\[
\mathcal{F}_{\tau}:=\{E\setminus C\mid C\subseteq E\text{ is closed}\}.
\]
Thus $\mathcal{F}_{\tau}$ is the feasible-set antimatroid associated with
$\tau$ (see \cite[proof of Theorem III.1.3]{KLS91}). For any subset
$X\subseteq E$, define its \emph{trace} by
\[
\mathcal{F}_{\tau}:X:=\{A\cap X\mid A\in\mathcal{F}_{\tau}\}.
\]
Following Korte--Lov\'{a}sz--Schrader \cite[\S III.3]{KLS91}, call the set $X$
\emph{free} if $\mathcal{F}_{\tau}:X=\mathcal{P}(X)$, and call it \emph{free
convex} if it is both free and closed. Then the free convex sets in this sense
are exactly the sets in $\operatorname{Free}(\tau)$ from
Definition~\ref{def:free}.
\end{proposition}

\begin{proof}
Let $F\in\operatorname{Free}(\tau)$. Lemma~\ref{lem:free-complex} shows that
every subset of $F$ is closed. Fix $Y\subseteq F$. Then $F\setminus Y$ is
closed, so
\[
A:=E\setminus(F\setminus Y)
\]
belongs to $\mathcal{F}_{\tau}$, and
\[
A\cap F=Y.
\]
Thus $\mathcal{F}_{\tau}:F=\mathcal{P}(F)$, so $F$ is free in the sense of
Korte--Lov\'{a}sz--Schrader. It is closed by Definition~\ref{def:free}, and
therefore it is free convex.

Conversely, let $F$ be free convex in the sense of
Korte--Lov\'{a}sz--Schrader. Thus $F$ is closed, so that $\tau(F)=F$. Fix
$u\in F$. Since $\mathcal{F}_{\tau}:F=\mathcal{P}(F)$, there exists
$A\in\mathcal{F}_{\tau}$ such that
\[
A\cap F=\{u\}.
\]
Write $A=E\setminus C$ with $C$ closed. Then $C=E\setminus A$, so that
$F\setminus\{u\}\subseteq C$ (since $\left(  F\setminus\left\{  u\right\}
\right)  \cap A=\left(  A\cap F\right)  \setminus\left\{  u\right\}  =\left\{
u\right\}  \setminus\left\{  u\right\}  =\varnothing$) and $u\notin C$ (since
$u\in\left\{  u\right\}  =A\cap F\subseteq A=E\setminus C$). Hence
monotonicity gives
\[
\tau(F\setminus\{u\})\subseteq\tau(C)=C,
\]
so $u\notin\tau(F\setminus\{u\})$ (since $u\notin C$). Since this holds for
every $u\in F$, the set $F$ belongs to $\operatorname{Free}(\tau)$.
\end{proof}

This matches the terminology of \cite[Chapter~III, Section~3]{KLS91}; their
\emph{free convex set system} is the complex considered in \cite[Chapter~XII,
Section~2]{KLS91}. Later papers commonly call it the \emph{free complex} of
the convex geometry.

For the quasi-closure arising from an inclusion-reversing shade map, the free
convex set complex is exactly the locus on which the shade is all of $E$.

\begin{lemma}
\label{lem:full-shade-free} Let $T$ and $\tau$ be as in
Proposition~\ref{prop:tau-from-T}. Then
\begin{equation}
\operatorname{Free}(\tau) =\{F\subseteq E\mid T(F)=E\}.
\label{eq:full-shade-free}%
\end{equation}

\end{lemma}

\begin{proof}
Let $F\subseteq E$. We must show that $F\in\operatorname{Free}(\tau)$ if and
only if $T\left(  F\right)  =E$.

$\Longleftarrow:$ Suppose that $T(F)=E$. Then \eqref{eq:tau-from-T} gives
$\tau(F)=F\cup\varnothing=F$. Moreover, for every $u\in F$, we have $u\in
E=T\left(  F\right)  $ and therefore $u\notin\tau(F\setminus\{u\})$ by
\eqref{eq:recover-T}. Thus $F$ is a free convex set. That is, $F\in
\operatorname{Free}(\tau)$.

$\Longrightarrow:$ Conversely, suppose that $F\in\operatorname*{Free}\left(
\tau\right)  $. That is, $F$ is a free convex set; hence $\tau\left(
F\right)  =F$. We must prove that $T\left(  F\right)  =E$. Obviously it
suffices to show that each $e\in E$ belongs to $T\left(  F\right)  $. We can
show this case by case: If $e\in F$, then $e\notin\tau(F\setminus\{e\})$ by
freeness, so \eqref{eq:recover-T} gives $e\in T(F)$. If $e\notin F$, then
$F\setminus\{e\}=F$ and $e\notin F=\tau\left(  F\right)  $, so again
$e\notin\tau(F\setminus\{e\})$, and \eqref{eq:recover-T} gives $e\in T(F)$.
Thus every $e\in E$ belongs to $T(F)$. Therefore, $T(F)=E$.
\end{proof}

We now construct a complete acyclic matching on the free convex set complex of
any antimatroidal quasi-closure operator (on a nonempty set $E$). For ordinary
convex geometries, this collapsibility conclusion is already implied by the
stronger theorem of Korte--Lov\'{a}sz--Schrader that the free convex set
system is non-evasive \cite[Theorem~XII.2.13]{KLS91}; the implication from
non-evasiveness to collapsibility is also discussed in \cite[Chapter~10,
Exercise~4(b)]{Kozlov20}. The proof below is included because its matching
will fit directly into the proof of Theorem~\ref{thm:main-reversing}.

\begin{definition}
\label{def:coloop} Let $\tau$ be a quasi-closure operator on $E$. We call
$x\in E$ a \emph{coloop} (of $\tau$) if
\begin{equation}
x\notin\tau(E\setminus\{x\}). \label{eq:coloop}%
\end{equation}

\end{definition}

Thus, a coloop is an extreme point of the whole ground set $E$.

\begin{lemma}
[Existence of a coloop]\label{lem:coloop-exists} Let $E$ be nonempty, and let
$\tau$ be an antimatroidal quasi-closure operator with $\tau(\varnothing
)=\varnothing$. Then $\tau$ has a coloop.
\end{lemma}

\begin{proof}
Choose a maximal closed proper subset $C\subsetneq E$. Such a set exists,
since $\varnothing$ is closed (since $\tau\left(  \varnothing\right)
=\varnothing$) and $E$ is finite. Of course, $\tau\left(  C\right)  =C$.

We claim that $|E\setminus C|=1$. Indeed, assume the contrary; thus,
$\left\vert E\setminus C\right\vert \geq2$ since $C$ is a proper subset of
$E$. So choose distinct $x,y\in E\setminus C$. Then, $x,y\in E\setminus
C=E\setminus\tau\left(  C\right)  $ (since $C=\tau\left(  C\right)  $). The
set $\tau\left(  C\cup\left\{  x\right\}  \right)  $ is closed (indeed,
idempotence of $\tau$ shows that $\tau\left(  A\right)  $ is closed for any
$A\in\mathcal{P}\left(  E\right)  $) and strictly contains $C$ (since
$C\subsetneq C\cup\left\{  x\right\}  \subseteq\tau\left(  C\cup\left\{
x\right\}  \right)  $ by extensivity of $\tau$); hence, it cannot be a proper
subset of $E$ (since $C$ is maximal among the closed proper subsets). That is,%
\[
\tau(C\cup\{x\})=E.
\]
Therefore,%
\begin{equation}
y\in\tau(C\cup\{x\}). \label{pf.lem:coloop-exists.4}%
\end{equation}
Similarly, $x\in\tau(C\cup\{y\})$. Hence, the anti-exchange axiom for $\tau$
yields $y\notin\tau(C\cup\{x\})$ (since $x,y\in E\setminus\tau\left(
C\right)  $ and $x\neq y$), in contradiction with
(\ref{pf.lem:coloop-exists.4}).

So our assumption was false, and $|E\setminus C|=1$ is proved. Hence, there is
an $x\in E$ such that $E\setminus C=\{x\}$ (and therefore $C=E\setminus
\left\{  x\right\}  $). This $x$ then satisfies%
\[
x\notin C=\tau(C)=\tau(E\setminus\{x\})\ \ \ \ \ \ \ \ \ \ \left(  \text{since
}C=E\setminus\left\{  x\right\}  \right)  ,
\]
so $x$ is a coloop.
\end{proof}

Let us remark that Lemma~\ref{lem:coloop-exists}
is also an easy consequence of the abstract Krein--Milman characterization
of extreme points of convex geometries, as stated in
\cite[Theorem~III.1.1]{KLS91}%
\footnote{This is the following fact: Let $E$ and $\tau$ be as in
Lemma~\ref{lem:coloop-exists}, and let $X$ be a subset of $E$ satisfying
$\tau(X) = X$. Let $\operatorname{ex}(X)$ denote the set of all $x \in X$
satisfying $x \notin \tau(X\setminus\{x\})$.
Then, $\tau(\operatorname{ex}(X)) = X$.
\par
Applying this result to $X = E$ yields
$\tau(\{\text{coloops}\}) = E$
(since we can easily see that $\tau(E) = E$ and
$\operatorname{ex}(E) = \{\text{coloops}\}$).
From this, it follows that $\{\text{coloops}\} \neq \varnothing$
(since $\tau(\varnothing) = \varnothing \neq E$), and thus
Lemma~\ref{lem:coloop-exists} follows.
}.

Coloops can be used to break up antimatroids recusively.
Let $x$ be a coloop and set $E^{\prime}:=E\setminus\{x\}$. Define maps
$\tau_{-},\tau_{+}:\mathcal{P}(E^{\prime})\rightarrow\mathcal{P}(E^{\prime})$
by
\begin{align}
\tau_{-}(A)  &  :=\tau(A)\ \ \ \ \ \ \ \ \ \ \text{for all }A\in
\mathcal{P}\left(  E^{\prime}\right)  ,\ \ \ \ \ \ \ \ \ \ \text{and}%
\label{eq:tau-minus}\\
\tau_{+}(A)  &  :=\tau(A\cup\{x\})\setminus\{x\}\ \ \ \ \ \ \ \ \ \ \text{for
all }A\in\mathcal{P}\left(  E^{\prime}\right)  . \label{eq:tau-plus}%
\end{align}
These are called \emph{deletion} and \emph{contraction} of $\tau$ at $x$.

\begin{lemma}
[Deletion and contraction]\label{lem:del-con} Let $\tau$ be an antimatroidal
quasi-closure operator on $E$, and let $x$ be a coloop. Then:

\begin{enumerate}
\item[\textbf{(a)}] The maps $\tau_{-}$ and $\tau_{+}$ are antimatroidal
quasi-closure operators on $E^{\prime}$.

\item[\textbf{(b)}] For every $A\subseteq E^{\prime}$, we have the
equivalences
\begin{equation}
A\in\operatorname{Free}(\tau_{-})\Longleftrightarrow A\in\operatorname{Free}%
(\tau), \label{eq:free-minus}%
\end{equation}
and
\begin{equation}
A\in\operatorname{Free}(\tau_{+})\Longleftrightarrow A\cup\{x\}\in
\operatorname{Free}(\tau). \label{eq:free-plus}%
\end{equation}
Consequently,
\begin{equation}
\operatorname{Free}(\tau)=\operatorname{Free}(\tau_{-})\sqcup\{A\cup\{x\}\mid
A\in\operatorname{Free}(\tau_{+})\}. \label{eq:free-decomposition}%
\end{equation}

\end{enumerate}
\end{lemma}

\begin{proof}
\textbf{(a)} Since $x$ is a coloop, we have $x\notin\tau\left(  E\setminus
\left\{  x\right\}  \right)  =\tau\left(  E^{\prime}\right)  $ and therefore%
\begin{equation}
x\notin\tau(A)\qquad\text{for every }A\subseteq E^{\prime}
\label{eq:x-not-closure-A}%
\end{equation}
(since $A\subseteq E^{\prime}$ implies $\tau\left(  A\right)  \subseteq
\tau\left(  E^{\prime}\right)  $ by monotonicity). Thus $\tau(A)\subseteq
E^{\prime}$, so $\tau_{-}$ is well-defined. Extensivity, monotonicity,
idempotence, and anti-exchange for $\tau_{-}$ are immediate from the
corresponding properties of $\tau$. For $\tau_{+}$, well-definedness,
extensivity and monotonicity are immediate. Since $x\in A\cup\{x\}\subseteq
\tau(A\cup\{x\})$ by extensivity,
\begin{align*}
\tau_{+}(\tau_{+}(A))  &  =\tau\bigl((\tau(A\cup\{x\})\setminus\{x\})\cup
\{x\}\bigr)\setminus\{x\}\\
&  =\tau(\tau(A\cup\{x\}))\setminus\{x\}\\
&  =\tau(A\cup\{x\})\setminus\{x\}=\tau_{+}(A).
\end{align*}
Thus $\tau_{+}$ is idempotent. To check anti-exchange for $\tau_{+}$, let
$A\subseteq E^{\prime}$ and let $y,z$ be distinct elements of $E^{\prime
}\setminus\tau_{+}(A)$ such that $z\in\tau_{+}(A\cup\{y\})$. Thus,%
\begin{align*}
y,z  &  \notin\tau(A\cup\{x\})\ \ \ \ \ \ \ \ \ \ \left(  \text{since
}y,z\notin\tau_{+}\left(  A\right)  =\tau(A\cup\{x\})\setminus\{x\}\text{ and
}y,z\neq x\right) \\
\text{and}\ \ \ \ \ \ \ \ \ \ z  &  \in\tau(A\cup
\{x,y\})\ \ \ \ \ \ \ \ \ \ \left(  \text{since }z\in\tau_{+}(A\cup
\{y\})=\tau(A\cup\{x,y\})\setminus\{x\}\right)  .
\end{align*}
Anti-exchange for $\tau$, with $A\cup\{x\}$ in place of $A$, therefore yields
$y\notin\tau(A\cup\{x,z\})$, whence $y\notin\tau_{+}(A\cup\{z\})$. Hence
$\tau_{+}$ is antimatroidal. \medskip

\textbf{(b)} Let $A\subseteq E^{\prime}$. The equivalence
\eqref{eq:free-minus} follows directly from $\tau_{-}(A)=\tau(A)$. For
\eqref{eq:free-plus}, first observe the equivalence%
\begin{equation}
\tau_{+}(A)=A\quad\Longleftrightarrow\quad\tau(A\cup\{x\})=A\cup\{x\},
\label{eq:closed-contraction}%
\end{equation}
because $x\in A\cup\{x\}\subseteq\tau(A\cup\{x\})$. Next, for each $a\in A$,
we have the equivalence%
\begin{equation}
a\notin\tau_{+}(A\setminus\{a\})\quad\Longleftrightarrow\quad a\notin%
\tau\bigl((A\cup\{x\})\setminus\{a\}\bigr), \label{eq:extreme-contraction}%
\end{equation}
since $a\in A\subseteq E^{\prime}$ entails $a\neq x$. Thus, we find the
equivalence%
\begin{align*}
&  \ \left(  a\notin\tau_{+}\left(  A\setminus\left\{  a\right\}  \right)
\text{ for all }a\in A\right) \\
&  \Longleftrightarrow\ \left(  a\notin\tau\bigl((A\cup\{x\})\setminus
\{a\}\bigr)\text{ for all }a\in A\right) \\
&  \Longleftrightarrow\ \left(  a\notin\tau\bigl((A\cup\{x\})\setminus
\{a\}\bigr)\text{ for all }a\in A\cup\left\{  x\right\}  \right)
\end{align*}
(the latter is because (\ref{eq:x-not-closure-A}) yields $x\notin\tau\left(
A\right)  =\tau\bigl((A\cup\{x\})\setminus\{x\}\bigr)$, so that $a\notin%
\tau\bigl((A\cup\{x\})\setminus\{a\}\bigr)$ always holds for $a=x$). Combining
this with \eqref{eq:closed-contraction} proves \eqref{eq:free-plus}. The
decomposition \eqref{eq:free-decomposition} now follows by separating free
convex sets according to whether they contain $x$: namely,%
\begin{align*}
\operatorname{Free}(\tau)  &  =\underbrace{\left\{  A\in\operatorname{Free}%
(\tau)\mid x\notin A\right\}  }_{\substack{=\operatorname{Free}(\tau
_{-})\\\text{(by (\ref{eq:free-minus}))}}}\sqcup\underbrace{\left\{
A\in\operatorname{Free}(\tau)\mid x\in A\right\}  }_{\substack{=\{A\cup
\{x\}\mid A\subseteq E^{\prime}\text{ and }A\cup\left\{  x\right\}
\in\operatorname*{Free}\left(  \tau\right)  \}\\=\{A\cup\{x\}\mid
A\in\operatorname{Free}(\tau_{+})\}\\\text{(by (\ref{eq:free-plus}))}}}\\
&  =\operatorname{Free}(\tau_{-})\sqcup\{A\cup\{x\}\mid A\in
\operatorname{Free}(\tau_{+})\}.\qedhere
\end{align*}

\end{proof}

\begin{lemma}
[Loops destroy free convex sets]\label{lem:loops-no-free} Let $\tau$ be a
quasi-closure operator on $E$. If $\tau(\varnothing)\neq\varnothing$, then
\[
\operatorname{Free}(\tau)=\varnothing.
\]

\end{lemma}

\begin{proof}
Assume that $\tau(\varnothing)\neq\varnothing$, and suppose, for
contradiction, that $F$ is a free convex set. Since $\varnothing\subseteq F$,
monotonicity gives
\[
\tau(\varnothing)\subseteq\tau(F)=F\ \ \ \ \ \ \ \ \ \ \left(  \text{since
}F\text{ is closed}\right)  .
\]
Choose $u\in\tau(\varnothing)$ (this exists since $\tau\left(  \varnothing
\right)  \neq\varnothing$). Then $u\in\tau\left(  \varnothing\right)
\subseteq F$. Moreover,%
\[
u\in\tau(\varnothing)\subseteq\tau(F\setminus\{u\})\ \ \ \ \ \ \ \ \ \ \left(
\text{by monotonicity, since }\varnothing\subseteq F\setminus\left\{
u\right\}  \right)  .
\]
This contradicts (\ref{eq:free-independent}). Hence no free convex set exists,
and $\operatorname{Free}(\tau)=\varnothing$.
\end{proof}

The decomposition \eqref{eq:free-decomposition} is closely related to standard
deletion--contraction recursions for free convex set complexes; compare
Kashiwabara--Nakamura \cite{KashiwabaraNakamura05}.

We can now easily prove a (quite straightforward) generalization of
\cite[Lemma 4.2]{EdelmanReiner00}:

\begin{theorem}
[Free convex set complexes are collapsible]\label{thm:free-collapsible} Let
$E$ be a nonempty finite set, and let $\tau:\mathcal{P}(E)\to\mathcal{P}(E)$
be an antimatroidal quasi-closure operator. Then $\operatorname{Free}(\tau)$
admits an acyclic complete matching. Hence $\operatorname{Free}(\tau)$ is collapsible.
\end{theorem}

\begin{proof}
We induct on $|E|$. First suppose that $\tau(\varnothing)\neq\varnothing$.
Then $\operatorname{Free}(\tau)=\varnothing$ by Lemma~\ref{lem:loops-no-free}.
Thus the empty matching is a complete acyclic matching. We may henceforth
assume $\tau(\varnothing)=\varnothing$. If $|E|=1$, then $\operatorname{Free}%
(\tau)=\mathcal{P}(E)$: the empty set and the unique singleton are both free
convex sets. Toggling the unique element gives an acyclic complete matching.
Now suppose $|E|>1$. By Lemma~\ref{lem:coloop-exists}, choose a coloop $x\in
E$, and define $\tau_{-}$ and $\tau_{+}$ as above on the power set of the
nonempty ground set $E^{\prime}=E\setminus\{x\}$. By induction,
$\operatorname{Free}(\tau_{-})$ and $\operatorname{Free}(\tau_{+})$ admit
acyclic complete matchings $\mu_{-}$ and $\mu_{+}$, respectively (since Lemma
\ref{lem:del-con} \textbf{(a)} shows that $\tau_{-}$ and $\tau_{+}$ are
antimatroidal quasi-closure operators). By \eqref{eq:free-decomposition}, the
complex $\operatorname{Free}(\tau)$ consists of the faces of
$\operatorname{Free}(\tau_{-})$ as well as the faces of $\operatorname{Free}%
(\tau_{+})$ with $x$ inserted into them. Now, define a map $\mu
:\operatorname{Free}(\tau)\rightarrow\operatorname{Free}(\tau)$ as follows:

\begin{itemize}
\item Use $\mu_{-}$ on the faces of $\operatorname{Free}(\tau)$ not containing
$x$.

\item On the faces of $\operatorname{Free}(\tau)$ containing $x$, use the
lifted matching
\[
A\cup\{x\}\longleftrightarrow\mu_{+}(A)\cup\{x\}.
\]

\end{itemize}

\noindent By \eqref{eq:free-decomposition}, the union $\mu$ of these two
matchings is a complete matching of the free convex set complex
$\operatorname{Free}(\tau)$. It remains to prove acyclicity. Suppose that
$B_{1},\ldots,B_{r}$ is an alternating cycle of upper faces for $\mu$. In each
matched pair $B_{i}\leftrightarrow\mu^{-}\left(  B_{i}\right)  $, either both
faces contain $x$ or neither does. Thus, when we pass from $B_{i}$ to $\mu
^{-}(B_{i})$, the truth value of \textquotedblleft contains $x$%
\textquotedblright\ does not change (i.e., if $B_{i}$ contains $x$, then so
does $\mu^{-}\left(  B_{i}\right)  $; and if $B_{i}$ does not contain $x$,
then $\mu^{-}\left(  B_{i}\right)  $ does neither). When we then pass from
$\mu^{-}\left(  B_{i}\right)  $ to $B_{i+1}$ through the covering relation
\[
\mu^{-}(B_{i})\lessdot B_{i+1}%
\]
(where we understand $B_{r+1}$ to mean $B_{1}$), that truth value can stay the
same or change from false to true, but it cannot change from true to false
(since we are only adding an element, not removing any elements). Thus, as we
step from $B_{i}$ to $B_{i+1}$ (via $\mu^{-}\left(  B_{i}\right)  $), this
truth value cannot change from true to false; the same holds when we step from
$B_{r}$ to $B_{1}$. Going around an alternating cycle%
\[
B_{1}\rightarrow B_{2}\rightarrow\cdots\rightarrow B_{r}\rightarrow B_{1},
\]
this truth value must therefore be constant. That is, either no $B_{i}$
contains $x$, or every $B_{i}$ contains $x$. If no $B_{i}$ contains $x$, the
alleged cycle lies entirely in $\mu_{-}$, contradicting the acyclicity of
$\mu_{-}$. If every $B_{i}$ contains $x$, remove $x$ from every face in the
cycle. The resulting cycle%
\[
B_{1}\setminus\left\{  x\right\}  \rightarrow B_{2}\setminus\left\{
x\right\}  \rightarrow\cdots\rightarrow B_{r}\setminus\left\{  x\right\}
\rightarrow B_{1}\setminus\left\{  x\right\}
\]
must then be an alternating cycle for $\mu_{+}$, again a contradiction. Hence
$\mu$ is acyclic.
\end{proof}

\section{Proof in the inclusion-reversing form}

\label{sec:proof-reversing}

We now prove Theorem~\ref{thm:main-reversing}. Fix once and for all a total
order on $E$.

\begin{proof}
[Proof of Theorem~\ref{thm:main-reversing}]Since $T$ is inclusion-reversing,
the family $\mathcal{B}_{G}(T)$ from \eqref{eq:BGT} is down-closed: if
$F^{\prime}\subseteq F$ and $G\subseteq T(F)$, then
\[
T(F^{\prime})\supseteq T(F)\supseteq G.
\]
Thus $\mathcal{B}_{G}(T)$ is a simplicial complex. Set
\begin{equation}
\mathcal{K}:=\{F\subseteq E\mid T(F)=E\}. \label{eq:K}%
\end{equation}
Since $G\subseteq E$, every face in $\mathcal{K}$ belongs to $\mathcal{B}%
_{G}(T)$. We shall now construct an acyclic complete matching on
$\mathcal{B}_{G}(T)$, in three steps.

\medskip\noindent\textit{Step 1: match all faces outside $\mathcal{K}$.} For
$F\in\mathcal{B}_{G}(T)\setminus\mathcal{K}$, define
\begin{equation}
\varepsilon(F):=\min(E\setminus T(F)) \label{eq:epsilon}%
\end{equation}
(this is well-defined since $F\notin\mathcal{K}$ yields $T\left(  F\right)
\neq E$, so that $E\setminus T\left(  F\right)  $ is nonempty, and of course a
nonempty finite subset of $E$ must have a minimum). Then $\varepsilon(F)\notin
T(F)$, so the shade-map axiom (\ref{eq:shade-axiom}) gives
\begin{equation}
T\bigl(F\mathbin{\triangle}\{\varepsilon(F)\}\bigr)=T(F). \label{eq:toggle-T}%
\end{equation}
In particular, $F\mathbin{\triangle}\{\varepsilon(F)\}$ still lies in
$\mathcal{B}_{G}(T)\setminus\mathcal{K}$, and its $\varepsilon$-value
$\varepsilon\left(  F\mathbin{\triangle}\{\varepsilon(F)\}\right)  $ is again
$\varepsilon(F)$ (since the definition of $\varepsilon\left(  F\right)  $
depends only on $T\left(  F\right)  $). Hence, we can define an involution
$\mu_{0}$ on $\mathcal{B}_{G}(T)\setminus\mathcal{K}$ by setting%
\begin{equation}
\mu_{0}(F):=F\mathbin{\triangle}\{\varepsilon(F)\}. \label{eq:mu0}%
\end{equation}
(This is an involution because -- as we just said -- the $\varepsilon$-value
$\varepsilon\left(  F\mathbin{\triangle}\{\varepsilon(F)\}\right)  $ is again
$\varepsilon(F)$, so that computing $\mu_{0}\left(  \mu_{0}\left(  F\right)
\right)  $ will toggle the same element twice.) Also, the faces $F$ and
$\mu_{0}(F)$ differ by exactly one element, so one covers the other. Thus
$\mu_{0}$ is a partial matching on $\mathcal{B}_{G}(T)$ whose domain is
$\mathcal{B}_{G}(T)\setminus\mathcal{K}$. We claim that this partial matching
is acyclic. Suppose otherwise, and let $B_{1},\ldots,B_{r}$ be an alternating
cycle of distinct upper faces. Thus
\[
\mu_{0}^{-}(B_{i})\lessdot B_{i+1}%
\]
for all $i$ (where $B_{r+1}$ means $B_{1}$). Equation \eqref{eq:toggle-T}
gives $T(\mu_{0}^{-}(B_{i}))=T(B_{i})$. Since $\mu_{0}^{-}(B_{i})\subseteq
B_{i+1}$ and $T$ is inclusion-reversing, $T(\mu_{0}^{-}(B_{i}))\supseteq
T(B_{i+1})$, and therefore
\[
T(B_{i})=T(\mu_{0}^{-}(B_{i}))\supseteq T(B_{i+1}).
\]
Applying this to each $i$ yields%
\[
T\left(  B_{1}\right)  \supseteq T\left(  B_{2}\right)  \supseteq
\cdots\supseteq T\left(  B_{r}\right)  \supseteq T\left(  B_{r+1}\right)
=T\left(  B_{1}\right)  ,
\]
which forces%
\begin{equation}
T(B_{1})=T(B_{2})=\cdots=T(B_{r}). \label{eq:T-constant-cycle}%
\end{equation}
Consequently all $\varepsilon(B_{i})$ are the same element (since
$\varepsilon(F)=\min(E\setminus T(F))$ depends only on $T(F)$); call this
element $\varepsilon$. Thus, for each $i$, we have $\mu_{0}^{-}(B_{i}%
)=B_{i}\setminus\{\varepsilon\}$ by the definition of $\mu_{0}^{-}$. This
yields $B_{i}=\mu_{0}^{-}(B_{i})\cup\left\{  \varepsilon\right\}  $ and
$\varepsilon\notin\mu_{0}^{-}(B_{i})$. Also $\varepsilon\in B_{i+1}$ since
$B_{i+1}$ is an upper face. But we also have $\mu_{0}^{-}(B_{i})\lessdot
B_{i+1}$ by the definition of an alternating cycle; hence, $B_{i+1}$ is
obtained from $\mu_{0}^{-}(B_{i})$ by adding a single element. This single
element must be $\varepsilon$ (since $\varepsilon\in B_{i+1}$ but
$\varepsilon\notin\mu_{0}^{-}(B_{i})$). Hence, $B_{i+1}=\mu_{0}^{-}(B_{i}%
)\cup\left\{  \varepsilon\right\}  =B_{i}$, contradicting the distinctness of
the upper faces. Thus $\mu_{0}$ is acyclic.

\medskip\noindent\textit{Step 2: match $\mathcal{K}$.} Define a map
$\tau:\mathcal{P}\left(  E\right)  \rightarrow\mathcal{P}\left(  E\right)  $
by setting
\[
\tau(F)=F\cup(E\setminus T(F))\ \ \ \ \ \ \ \ \ \ \text{for all }F\subseteq
E.
\]
By Proposition~\ref{prop:tau-from-T}, $\tau$ is an antimatroidal quasi-closure
operator. By Lemma~\ref{lem:full-shade-free}, we have%
\[
\operatorname{Free}(\tau)=\{F\subseteq E\mid T(F)=E\}=\mathcal{K}.
\]
Since $E$ is nonempty, Theorem~\ref{thm:free-collapsible} thus gives an
acyclic complete matching $\mu_{1}$ on $\mathcal{K}$.

\medskip\noindent\textit{Step 3: glue the two matchings.} The domains of the
two matchings $\mu_{0}$ and $\mu_{1}$ are disjoint and together cover
$\mathcal{B}_{G}(T)$. Hence, their union $\mu$ is a complete matching on
$\mathcal{B}_{G}\left(  T\right)  $. We now show that this matching is
acyclic. Suppose, for contradiction, that $B_{1},\ldots,B_{r}$ is an
alternating cycle of upper faces for $\mu$. Every matched pair $B_{i}%
\leftrightarrow\mu^{-}\left(  B_{i}\right)  $ has a common $T$-value (i.e., we
have $T\left(  B_{i}\right)  =T\left(  \mu^{-}\left(  B_{i}\right)  \right)
$): this follows from \eqref{eq:toggle-T} for a $\mu_{0}$-pair, while for a
$\mu_{1}$-pair both values are $E$ (since both $B_{i}$ and $\mu^{-}\left(
B_{i}\right)  $ belong to $\mathcal{K}$ in this case). Hence
\[
T(\mu^{-}(B_{i}))=T(B_{i}).
\]
As before, the covering relation $\mu^{-}(B_{i})\lessdot B_{i+1}$ and the
inclusion-reversal of $T$ give
\[
T(\mu^{-}(B_{i}))\supseteq T(B_{i+1}).
\]
Together with the preceding equality, this yields
\[
T(B_{i})=T(\mu^{-}(B_{i}))\supseteq T(B_{i+1}).
\]
Applying this for all $i$ yields%
\[
T\left(  B_{1}\right)  \supseteq T\left(  B_{2}\right)  \supseteq
\cdots\supseteq T\left(  B_{r}\right)  \supseteq T\left(  B_{r+1}\right)
=T\left(  B_{1}\right)  ,
\]
thus showing that all the sets $T(B_{i})$ are equal. Hence, either all these
sets $T\left(  B_{i}\right)  $ are $E$, or all of them are proper subsets of
$E$. If they are all $E$, then every $B_{i}$ lies in $\mathcal{K}$, so the
cycle $B_{1},\ldots,B_{r}$ lies entirely in $\mu_{1}$, contradicting the
acyclicity of $\mu_{1}$. If the sets $T\left(  B_{i}\right)  $ are proper
subsets of $E$, then every $B_{i}$ lies outside $\mathcal{K}$, so the cycle
lies entirely in $\mu_{0}$, again a contradiction. Thus $\mu$ is acyclic. We
have constructed an acyclic complete matching on $\mathcal{B}_{G}(T)$. By the
definition of collapsibility, this complex is collapsible.
\end{proof}

\section{The inclusion-preserving form and Alexander duals}

\label{sec:preserving}

We can now obtain Theorem~\ref{thm:main-preserving} by replacing the input set
with its complement.

\begin{proof}
[Proof of Theorem~\ref{thm:main-preserving}]The family $\mathcal{A}_{G}(S)$ is
down-closed because $S$ is inclusion-preserving, so it is a simplicial
complex. Define a map $T:\mathcal{P}\left(  E\right)  \rightarrow
\mathcal{P}\left(  E\right)  $ by
\[
T(F):=S(E\setminus F)\ \ \ \ \ \ \ \ \ \ \text{for all }F\subseteq E.
\]
By Lemma~\ref{lem:input-complement}, this $T$ is an inclusion-reversing shade
map. Theorem~\ref{thm:main-reversing} therefore shows that the simplicial
complex
\[
\{F\subseteq E\mid G\subseteq T(F)\}=\{F\subseteq E\mid G\subseteq
S(E\setminus F)\}
\]
is collapsible. By the definition of Alexander dual, this family is exactly
$\mathcal{A}_{G}(S)^{\vee}$.
\end{proof}

\section{The graph-theoretic shade}

For completeness, let us indicate the original example motivating the
definition of shade maps. Let $\Gamma$ be a finite undirected graph with a
nonempty edge set $E$. Fix a vertex $v$ of $\Gamma$. For any $F\subseteq E$,
let $C_{v}(F)$ be the connected component of $v$ in the spanning subgraph with
edge set $F$. Define $\operatorname{Shade}_{v}(F)$ to be the set of all edges
of $\Gamma$ having at least one endpoint in $C_{v}(F)$. This is the map called
$\operatorname{Shade}$ in \cite[Definition 2.6 (Definition~2.1 in the detailed
version)]{Grinberg21}. Its inclusion-preserving property is \cite[Lemma 2.8
(Lemma~2.3 in the detailed version)]{Grinberg21}, while the two shade-map
axioms (\ref{eq:shade-axiom+}) and (\ref{eq:shade-axiom-}) are \cite[Lemma 2.9
(Lemma~2.4 in the detailed version)]{Grinberg21}. Hence it is an
inclusion-preserving shade map. For every target set $G\subseteq E$, the
complex
\[
\{F\subseteq E\mid G\not \subseteq \operatorname{Shade}_{v}(F)\}
\]
is shown to be a simplicial complex in \cite[Proposition~5.2]{Grinberg21} and
collapsible in \cite[Theorem~5.5]{Grinberg21}; \cite[Theorem~5.7]{Grinberg21}
is the abstract shade-map generalization of these two results. By
Theorem~\ref{thm:main-preserving}, its Alexander dual
\[
\{F\subseteq E\mid G\subseteq\operatorname{Shade}_{v}(E\setminus F)\}
\]
is collapsible as well.

\begin{example}
[A four-cycle]\label{exa:C4} Let $\Gamma$ be the $4$-cycle with vertices
$v_{0},v_{1},v_{2},v_{3}$ and edges
\[
e_{0}=v_{0}v_{1},\qquad e_{1}=v_{1}v_{2},\qquad e_{2}=v_{2}v_{3},\qquad
e_{3}=v_{3}v_{0}.
\]
Take $v=v_{0}$ as the distinguished vertex and take the one-edge target
$G=\{e_{1}\}$. Write $S=\operatorname{Shade}_{v_{0}}$.

The target edge $e_{1}$ is shaded by $F$ exactly when the $v_{0}$-component of
$F$ reaches at least one of $v_{1},v_{2}$. Hence
\[
\mathcal{A}_{G}(S)=\bigl\langle\{e_{1},e_{2}\},\{e_{1},e_{3}\}\bigr\rangle,
\]
where $\langle H_{1},\ldots,H_{m}\rangle$ denotes the simplicial complex with
facets $H_{1},\ldots,H_{m}$. Its Alexander dual is
\begin{equation}
\mathcal{A}_{G}(S)^{\vee}=\bigl\langle\{e_{0},e_{1}\},\{e_{1},e_{2}%
,e_{3}\}\bigr\rangle.\label{eq:C4-dual}%
\end{equation}
So $\mathcal{A}_{G}(S)^{\vee}$ is a two-dimensional complex: it consists of a
filled triangle on $e_{1},e_{2},e_{3}$ with an extra edge $e_{0}e_{1}$
attached; see Figure~\ref{fig:C4-dual}.

This example also makes the two stages of the proof of
Theorem~\ref{thm:main-reversing} visible. Put $T(F)=S(E\setminus F)$. Then
\[
\mathcal{K}=\{F\subseteq E\mid T(F)=E\}=\bigl\langle\{e_{0},e_{1}%
\},\{e_{1},e_{2}\},\{e_{2},e_{3}\}\bigr\rangle,
\]
so $\mathcal{K}$ is the path $e_{0}-e_{1}-e_{2}-e_{3}$ drawn with thick edges
in the right-hand picture. If we order $e_{0}<e_{1}<e_{2}<e_{3}$, then the
toggle matching $\mu_{0}$ from Step~1 matches precisely
\[
\{e_{1},e_{3}\}\longleftrightarrow\{e_{1},e_{2},e_{3}\};
\]
the remaining path $\mathcal{K}$ is then matched by the free-convex-set
matching $\mu_{1}$ from Step~2. For example, one possible complete matching on
this path is
\[
\varnothing\leftrightarrow\{e_{2}\},\quad\{e_{0}\}\leftrightarrow\{e_{0}%
,e_{1}\},\quad\{e_{1}\}\leftrightarrow\{e_{1},e_{2}\},\quad\{e_{3}%
\}\leftrightarrow\{e_{2},e_{3}\}.
\]


\begin{figure}[th]
\centering
\begin{tikzpicture}[scale=1.0]
% The graph.
\begin{scope}[xshift=-3.7cm]
\coordinate (v0) at (0,0);
\coordinate (v1) at (2.1,0);
\coordinate (v2) at (2.1,2.1);
\coordinate (v3) at (0,2.1);
\draw (v0)--node[below] {$e_0$} (v1);
\draw[very thick] (v1)--node[right] {$e_1$} (v2);
\draw (v2)--node[above] {$e_2$} (v3);
\draw (v3)--node[left] {$e_3$} (v0);
\fill (v0) circle (1.6pt) node[below left] {$v_0$};
\fill (v1) circle (1.6pt) node[below right] {$v_1$};
\fill (v2) circle (1.6pt) node[above right] {$v_2$};
\fill (v3) circle (1.6pt) node[above left] {$v_3$};
\node at (1.05,-0.72) {$G=\{e_1\}$};
\end{scope}
% The dual complex.
\begin{scope}[xshift=3.1cm]
\coordinate (e0) at (-2.0,0);
\coordinate (e1) at (0,0);
\coordinate (e2) at (1.15,1.9);
\coordinate (e3) at (2.3,0);
\fill[black!8] (e1)--(e2)--(e3)--cycle;
\draw (e1)--(e3);
\draw[very thick] (e0)--(e1)--(e2)--(e3);
\fill (e0) circle (1.6pt) node[below] {$e_0$};
\fill (e1) circle (1.6pt) node[below] {$e_1$};
\fill (e2) circle (1.6pt) node[above] {$e_2$};
\fill (e3) circle (1.6pt) node[below] {$e_3$};
\end{scope}
\end{tikzpicture}
\caption{Left: the four-cycle in Example~\ref{exa:C4}; the target edge is
thick. Right: the two-dimensional complex $\mathcal{A}_{G}(S)^{\vee}$ from
\eqref{eq:C4-dual}; the thick path is the subcomplex $\mathcal{K}$ from
Step~2.}%
\label{fig:C4-dual}%
\end{figure}
\end{example}

\begin{thebibliography}{9}                                                                                                %


\bibitem {EdelmanJamison85}Paul H. Edelman and Robert E. Jamison, \textit{The
theory of convex geometries}, Geometriae Dedicata \textbf{19} (1985), no.~3,
247--270, \href{https://doi.org/10.1007/BF00149365}{doi:10.1007/BF00149365}.

\bibitem {EdelmanReiner00}Paul H. Edelman and Victor Reiner, \textit{Counting
the interior points of a point configuration}, Discrete \& Computational
Geometry \textbf{23} (2000), no.~1, 1--13,
\href{https://doi.org/10.1007/PL00009483}{doi:10.1007/PL00009483}.

\bibitem {Forman98}Robin Forman, \textit{Morse theory for cell complexes},
Advances in Mathematics \textbf{134} (1998), no.~1, 90--145,
\href{https://doi.org/10.1006/aima.1997.1650}{doi:10.1006/aima.1997.1650}.

\bibitem {Grinberg21}Darij Grinberg, \textit{The Elser nuclei sum revisited},
Discrete Mathematics \& Theoretical Computer Science \textbf{23} (2021),
no.~1, \href{https://doi.org/10.46298/dmtcs.7012}{doi:10.46298/dmtcs.7012};
more detailed version available as
\href{https://arxiv.org/abs/2009.11527}{arXiv:2009.11527}.

\bibitem {HachimoriKashiwabara07}Masahiro Hachimori and Kenji Kashiwabara,
\textit{On the topology of the free complexes of convex geometries}, Discrete
Mathematics \textbf{307} (2007), no.~2, 274--279,
\href{https://doi.org/10.1016/j.disc.2006.06.020}{doi:10.1016/j.disc.2006.06.020}%
.

\bibitem {KashiwabaraNakamura05}Kenji Kashiwabara and Masataka Nakamura,
\textit{NBC complexes of convex geometries}, Discrete Mathematics \&
Theoretical Computer Science Proceedings, vol.~AE (EuroComb 2005), 207--212,
\href{https://doi.org/10.46298/dmtcs.3412}{doi:10.46298/dmtcs.3412}.

\bibitem {KLS91}Bernhard Korte, L\'aszl\'o Lov\'asz, and Rainer Schrader,
\textit{Greedoids}, Algorithms and Combinatorics, vol.~4, Springer-Verlag,
Berlin, 1991,
\href{https://doi.org/10.1007/978-3-642-58191-5}{doi:10.1007/978-3-642-58191-5}%
.

\bibitem {Kozlov20}Dmitry N. Kozlov, \textit{Organized Collapse: An
Introduction to Discrete Morse Theory}, Graduate Studies in Mathematics,
vol.~207, American Mathematical Society, Providence, RI, 2020,
\href{https://doi.org/10.1090/gsm/207}{doi:10.1090/gsm/207}.

\bibitem {Okamoto08}Yoshio Okamoto, \textit{Local topology of the free complex
of a two-dimensional generalized convex shelling}, Discrete Mathematics
\textbf{308} (2008), no.~17, 3836--3846,
\href{https://doi.org/10.1016/j.disc.2007.07.078}{doi:10.1016/j.disc.2007.07.078}%
.
\end{thebibliography}


\end{document}