\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{} %TCIDATA{} %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 but not the historical references, so the exact origins of the argument are not entirely clear. -- 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} (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} This is one of the standard extreme-point properties of convex geometries; compare the abstract Krein--Milman characterization in \cite[Theorem~III.1.1]% {KLS91}. 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}. \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}