Showing posts with label quotient. Show all posts
Showing posts with label quotient. Show all posts

Sunday, December 3, 2017

Ordering simplicial complexes with unlabeled vertices

The goal of this post is to describe a partial order on the collection of simplical complexes with $\leqslant n$ unlabeled vertices that is nice in the context of the space $X=\Ran^{\leqslant n}(M)\times \R_{>0}$.

First note that there is a natural order on (abstract) simplicial complexes, given by set inclusion. Interpreting elements of $X$ as simplicial complexes induces a more restrictive order, as new vertices must "split off" from existing ones rather than just be introduced anywhere. Also note that the category usually denoted by $SC$ of simplicial complexes and simplicial maps contains objects with unordered vertices. Here we assume an order on them and consider the action of the symmetric groups to remove the order.

Definition: Let $SC_k$, for some positive integer $k$, be the collection of simplicial complexes with $k$ uniquely labeled vertices. This collection is a poset, with $S\leqslant T$ iff $\sigma\in T$ for every $\sigma\in S$.

The symmetric group on $k$ elements acts on $SC_k$ by permuting the vertices, and taking the image under this action we get $SC_k/S_k$, the collection of simplicial complexes with $k$ unlabeled vertices. This set also has a partial order, with $S\leqslant T$ in $SC_k/S_k$ iff $S'\leqslant T'$ in $SC_k$, for some $S'\in q_k^{-1}(S)$ and $T'\in q_k^{-1}(T)$, where $q_k:SC_k \twoheadrightarrow SC_k/S_k$ is the quotient map.

Definition: For all $i=1,\dots,k$, let $s_{k,i}$ be the $i$th splitting map, which splits the $i$th vertex in two. That is, if the vertices of $S\in SC_k$ are labeled $v_1,\dots,v_k$, then $s_{k,i}$ is defined by
\[\begin{array}{r c l}
s_{k,i}\ :\ SC_k & \to & SC_{k+1}, \\
S & \mapsto & \left\langle S'\cup \{v_i,v_{i+1}\} \cup \displaystyle \bigcup_{\{v_i,w\}\in S'} \{v_{i+1},w\} \right\rangle ,
\end{array}\]where $S'$ is $S$ with $v_j$ relabeled as $v_{j+1}$ for all $j>i$, and $\langle T\rangle$ is the simplicial complex generated by $T$.

By "generated by $T$" we mean generated in the Vietoris-Rips sense, that is, if $\{v_a,v_b\}\in T$ for all $a,b$ in some indexing set $I$, then $\{v_c\ :\ c\in I\}\in \langle T\rangle$. The $i$th splitting map is essentially the $i$th face map used for simplicial sets.

Let $A = \bigcup_{k=1}^n SC_k/S_k$. The splitting maps induce a partial order on $A$, with $S\leqslant T$, for $S\in SC_k/S_k$ and $T\in SC_{k+1}/S_{k+1}$, iff $s_{k,i}(S')\leqslant T'$ in $SC_k$, for some $S'\in q_k^{-1}(S)$, $T'\in q_{k+1}^{-1}(T)$, and $i\in \{1,\dots,k\}$. This generalizes via composition of the splitting maps to any pair $S,T\in A$, and is visually decribed by the diagram below.

Now, let $M$ be a smooth, compact, connected manifold embedded in $\R^N$, and $X=\Ran^{\leqslant n}(M)\times \R_{>0}$. Let $f:X\to A$ be given by $(P,t)\mapsto VR(P,t)$, the Vietoris-Rips complex around the points of $P$ with radius $t$.

Proposition: The map $f:X\to A$ is continuous.

Proof: Let $S\in A$ and $U_S \subseteq A$ be the open set based at $S$. Take any $(P,t)\in f^{-1}(U_S)\subseteq X$, for which we will show that there is an open ball $B\owns (P,t)$ completely within $f^{-1}(U_S)$.

Case 1: $t\neq d(P_i,P_j)$ for all pairs $P_i,P_j\in P$. Then set
\[\epsilon = \min\left\{t, \min_{i<j} |t-d(P_i,P_j)|, \min_{i<j} d(P_i,P_j) \right\}.\]Set $B = B^{\Ran^{\leqslant n}(M)}_{\epsilon/4}(P) \times B^{\R_{>0}}_{\epsilon/4}(t)$, which is an open neighborhood of $(P,t)$ in $X$. It is immediate that $f(P',t')$, for any other $(P',t')\in B$, has all the simplices of $f(P,t)$, as $\epsilon \leqslant |t-d(P_i,P_j)|$ for all $i<j$. If $P_i$ has split in two in $P'$, then for every simplex containing $P_i$ in $f(P,t)$ there are two simplices in $f(P't')$, with either of the points into which $P_i$ split. That is, there may be new simplices in $f(P',t')$, but $f(P',t')$ will be in the image of the splitting maps. Equivalently, $f(P,t)\leqslant f(P',t')$ in $A$, so $B\subseteq f^{-1}(U_S)$.

Case 2: $t= d(P_i,P_j)$ for some pairs $P_i,P_j\in P$. Then set
\[\epsilon = \min\left\{t, \min_{i<j \atop t\neq d(P_i,P_j)} |t-d(P_i,P_j)|,\ \min_{i<j} d(P_i,P_j) \right\},\]and define $B$ as above. We are using the definition of Vietoris-Rips complex for which we add an edge between $P_i$ and $P_j$ whenever $t>d(P_i,P_j)$. Now take any $(P',t')\in B$ such that its image and the image of $(P,t)$ under $f$ are both in $SC_k/S_k$. Then any points $P_i,P_j \in P$ with $d(P_i,P_j)=t$ that have moved around to get to $P'$, an edge will possibly be added, but never removed, in the image of $f$ (when comparing with the image of $(P,t)$). This means that we have $f(P,t)\leqslant f(P',t')$ in $SC_k/S_k$, so certainly $f(P,t)\leqslant f(P',t')$ in $A$. The same argument as in the first case holds if points of $P$ split. Hence $B\subseteq f^{-1}(U_S)$ in this case as well.  $\square$

This proposition shows in particular that $X$ is poset-stratified by $A$