math.CO — Combinatorics

Collapsibility of Alexander duals for shade maps

Contributed by Darij Grinberg

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ász--Schrader prove the stronger fact that the free convex set system is non-evasive.