On the Topology of Weakly and Strongly Separated Set Complexes

Abstract

We examine the topology of the clique complexes of the graphs of weakly and strongly separated subsets of the set $[n]=\{1,2,...,n\}$, which, after deleting all cone points, we denote by ${\hat{\Delta }}_{ws}(n)$ and ${\hat{\Delta }}_{ss}(n)$, respectively. In particular, we find that ${\hat{\Delta }}_{ws}(n)$ is contractible for $n\ge 4$, while ${\hat{\Delta }}_{ss}(n)$ is homotopy equivalent to a sphere of dimension $n-3$. We also show that our homotopy equivalences are equivariant with respect to the group generated by two particular symmetries of ${\hat{\Delta }}_{ws}(n)$ and ${\hat{\Delta }}_{ss}(n)$: one induced by the set complementation action on subsets of $[n]$ and another induced by the action on subsets of $[n]$ which replaces each $k\in [n]$ by $n+1-k$.