In a previous blog post ("A constructible sheaf over the Ran space," 2017-06-24) it was claimed that there was a particular constructible sheaf over $\Ran^{\leqslant n}(M)\times \R_{\geqslant 0}$. However, the proof actually uses finite ordered subsets of $M$ to make the stratification, rather than finite unordered subsets. This means that the sheaf is actually over $M^{\times n}\times \R_{\geqslant 0}$, and in this post we try to fix that problem.
Let $\Delta_n$ be the "fat diagonal" of $M^{\times n}$, that is, the collection of $P\in M^{\times n}$ for which at least two coordinates are the same. For every $k>0$, there is an $S_k$ action on $M^{\times k}\setminus \Delta_k$, quotienting by which we get a map
\[M^{\times k}\setminus \Delta_k \xrightarrow{\ q_k\ }\Ran^k(M)\]
to the Ran space of degree $k$. The stratification of $M^{\times k}\times \R_{\geqslant 0}$ given in the previous post will be pushed forward to a stratification of $\Ran^k(M)\times \R_{\geqslant 0}$, for all $0<k\leqslant n$. A large part of the work already has been done, it remains to put everything in the right order and check openness. The process is given as follows:
As stated in the proof of the Theorem, $\Ran^{\geqslant k}(M)\times \R_{\geqslant 0}$ is open inside $\Ran^{\leqslant n}(M)\times \R_{\geqslant 0}$, allowing us to make a stratification $f:\Ran^{\leqslant n}(M)\times \R_{\geqslant 0}\to A$, where $A$ is the poset
where the tail of an arrow is ordered lower than the head. The map $f$ sends $\Ran^k(M)\times \R_{\geqslant 0}$ to $a_k$, which is a continuous map in the upset topology on $A$.
As stated in Definition 5, we have a stratification $g_k:(M^{\times k}\setminus \Delta_k) \times \R_{\geqslant 0}\to B_k$, where $B_k$ may be viewed as a directed graph $B_k=(V_k,E_k)$. The vertex set is $V_k = \{0,1\}^{k(k+1)/2}$, whose elements are strings of 1 and 0, and the edge set $E_k$ contains $v\to v'$ iff $d_H(v,v')=1$ and $d_H(v,0)<d_H(v',0)$, for $d_H$ the Hamming distance. Let $U_v\subset B_k$ denote the upset based at $v$, that is, all elements $v'\in B_k$ with $v\leqslant v'$.
Order all distinct pairs $(i,j)\in \{1,\dots,k\}^2$, of which there are $k(k+1)/2$. Under the stratifying map $g_k$, each upset $U_v$ based at the vertex $v\in\{0,1\}^{k(k+1)/2}$ receives elements $(P,t)\in (M^{\times k}\setminus \Delta_k)\times \R_{\geqslant 0}$ satisfying $t>d(P_i,P_j)$ whenever the position representing $(i,j)$ in $v$ is 1. For example, when $k=3$,
To check that $g_k$ is continuous in the upset topology, we restate Lemma 2 in a clearer way.
Lemma 1: Let $U\subset X$ be open and $\varphi:X\to A\subset \R_{\geqslant 0}$ continuous, with $|A|<\infty$. Then
\[\bigcup_{x\in U}\{x\}\times (\varphi(x),\infty)\ \subseteq\ X\times (z',\infty)\]
is open, for any $z'\leqslant z:= \min_{x\in U}\{\varphi(x)\}$.
Proof: Consider the function
\[\begin{array}{r c l}
\psi\ :\ X\times (z',\infty) & \to & X\times (-\infty,z), \\
(x,t) & \mapsto & (x,\varphi(x)-t).
\end{array}\]
Since $\varphi$ is continuous and subtraction is continuous, $\psi$ is continuous (in the product topology). Since $U\times (-\infty,0)$ is open in $X\times (-\infty,z)$, the set $\psi^{-1}(U\times (-\infty,0))$ is open in $X\times (z',\infty)$. For any $x\in U$ and $t=\varphi(x)$, we have $\varphi(x)-t =0$. For any $x\in U$ and $t\to \infty$, we have $\varphi(x)-t\to -\infty$. It is immediate that all other $t\in (\varphi(x),\infty)$ give $\varphi(x)-t\in (-\infty,0)$. Hence $\psi^{-1}(U\times (-\infty,0))$ is the collection of points $(x,t)$ with $t\in (\varphi(x),\infty)$, which is then open in $X\times [0,z')$. $\square$
Applying Lemma 1 to $U=X=M^{\times k}\setminus \Delta_k$ and $\varphi(P) = \max_{i\neq j}\{d(P_i,P_j)\}$, which is continuous, gives that $g_k^{-1}(U_{11\cdots1})\subseteq M^{\times k}\setminus \Delta_k$ is open. This also works to show that $g_k^{-1}(U_v)\subseteq g_k^{-1}(U_{v'})$ is open, for any $v'\leqslant v$, by limiting the pairs of indices iterated over by the function $\varphi$. Hence $g_k$ is continuous.
The symmetric group $S_k$ acts on $(M^{\times k}\setminus \Delta_k)\times \R_{\geqslant 0}$ by permuting the order of elements in the first factor. That is, for $\sigma\in S_k$, we have
\[\sigma (P=\{P_1,\dots,P_k\},t) = (\{P_{\sigma(1)},\dots,P_{\sigma(k)}\},t).\]
Note that $((M^{\times k}\setminus \Delta_k)\times \R_{\geqslant 0})/S_k = \Ran^k(M)\times \R_{\geqslant 0}$.
Remark: Graph isomorphism for two graphs with $k$ vertices may also be viewed as the equivalence relation induced by $S_k$ acting on $\Gamma_k = \{$simple vertex-labeled graphs with $k$ vertices$\}$. First, let $G_v$ be the (unique) graph first introduced at element $v\in B_k$ by $g_k$. That is, we have $G_v =VR(P,t)_1$ (the ordered 1-skeleton of the Vietoris--Rips complex on the set $P$ with radius $t$) whenever $g_k((P,t))\in U_v$ and $g_k((P,t))\not\in U_{v'}$ for any $v'\leqslant v$, $v'\neq v$. Then the elements of $B_k$ are in bijection with the elements of $\Gamma_k$ (given by $v\leftrightarrow G_v$), so we have $B_k/S_k = B_k'$. Recall that $v\leqslant v'$ in $B_k$ iff adding an edge to $G_v$ gives $G_{v'}$. In $B_{k'}$, this becomes a partial order on equivalence classes $[w] = \{v\in B_k\ :\ \sigma G_v=G_w\ $for some $\sigma\in S_k\}$. We write $[w]\leqslant [w']$ iff there is a collection of pairs $\{(v_1,v_1'),\dots,(v_\ell,v_\ell')\}$ such that $v_i\leqslant v_i'$ for all $i$, and $\{v_1,\dots,v_\ell\} = [w]$ and $\{v_1',\dots,v_\ell'\} = [w']$ (there may be repetition among the $v_i$ or $v_i'$).
By the universal property of the quotient, there is a unique map $h_k:\Ran^k(M)\times \R_{\geqslant 0}\to B_k'$ that makes the following diagram commute.
This will be our stratifying map. To check that $h_k$ is continuous take $U\subseteq B_k'$ open. As $\pi$ is the projection under a group action, it is an open map, so $\pi^{-1}(U)\subseteq B_k$ is open. Since $g_k$ is continuous in the upset topology, $g_k^{-1}(\pi^{-1}(U))$ is open. Again, $S_k\curvearrowright$ is the projection under a group action, so $(S_k\curvearrowright)(g_k^{-1}(\pi^{-1}(U)))$ is open, giving continuity of $h_k$.
Let $\Delta_n$ be the "fat diagonal" of $M^{\times n}$, that is, the collection of $P\in M^{\times n}$ for which at least two coordinates are the same. For every $k>0$, there is an $S_k$ action on $M^{\times k}\setminus \Delta_k$, quotienting by which we get a map
\[M^{\times k}\setminus \Delta_k \xrightarrow{\ q_k\ }\Ran^k(M)\]
to the Ran space of degree $k$. The stratification of $M^{\times k}\times \R_{\geqslant 0}$ given in the previous post will be pushed forward to a stratification of $\Ran^k(M)\times \R_{\geqslant 0}$, for all $0<k\leqslant n$. A large part of the work already has been done, it remains to put everything in the right order and check openness. The process is given as follows:
- Stratify $\Ran^{\leqslant n}(M)\times \R_{\geqslant 0}$ into $n$ pieces, each being $\Ran^k(M)\times \R_{\geqslant 0}$.
- Stratify $(M^{\times k}\setminus \Delta_k)\times \R_{\geqslant 0}$ as in the previous post.
- Quotient by $S_k$-action to get stratification of $\Ran^k(M)\times \R_{\geqslant 0}$.
Step 1
As stated in the proof of the Theorem, $\Ran^{\geqslant k}(M)\times \R_{\geqslant 0}$ is open inside $\Ran^{\leqslant n}(M)\times \R_{\geqslant 0}$, allowing us to make a stratification $f:\Ran^{\leqslant n}(M)\times \R_{\geqslant 0}\to A$, where $A$ is the poset
Step 2
As stated in Definition 5, we have a stratification $g_k:(M^{\times k}\setminus \Delta_k) \times \R_{\geqslant 0}\to B_k$, where $B_k$ may be viewed as a directed graph $B_k=(V_k,E_k)$. The vertex set is $V_k = \{0,1\}^{k(k+1)/2}$, whose elements are strings of 1 and 0, and the edge set $E_k$ contains $v\to v'$ iff $d_H(v,v')=1$ and $d_H(v,0)<d_H(v',0)$, for $d_H$ the Hamming distance. Let $U_v\subset B_k$ denote the upset based at $v$, that is, all elements $v'\in B_k$ with $v\leqslant v'$.
Order all distinct pairs $(i,j)\in \{1,\dots,k\}^2$, of which there are $k(k+1)/2$. Under the stratifying map $g_k$, each upset $U_v$ based at the vertex $v\in\{0,1\}^{k(k+1)/2}$ receives elements $(P,t)\in (M^{\times k}\setminus \Delta_k)\times \R_{\geqslant 0}$ satisfying $t>d(P_i,P_j)$ whenever the position representing $(i,j)$ in $v$ is 1. For example, when $k=3$,
Lemma 1: Let $U\subset X$ be open and $\varphi:X\to A\subset \R_{\geqslant 0}$ continuous, with $|A|<\infty$. Then
\[\bigcup_{x\in U}\{x\}\times (\varphi(x),\infty)\ \subseteq\ X\times (z',\infty)\]
is open, for any $z'\leqslant z:= \min_{x\in U}\{\varphi(x)\}$.
Proof: Consider the function
\[\begin{array}{r c l}
\psi\ :\ X\times (z',\infty) & \to & X\times (-\infty,z), \\
(x,t) & \mapsto & (x,\varphi(x)-t).
\end{array}\]
Since $\varphi$ is continuous and subtraction is continuous, $\psi$ is continuous (in the product topology). Since $U\times (-\infty,0)$ is open in $X\times (-\infty,z)$, the set $\psi^{-1}(U\times (-\infty,0))$ is open in $X\times (z',\infty)$. For any $x\in U$ and $t=\varphi(x)$, we have $\varphi(x)-t =0$. For any $x\in U$ and $t\to \infty$, we have $\varphi(x)-t\to -\infty$. It is immediate that all other $t\in (\varphi(x),\infty)$ give $\varphi(x)-t\in (-\infty,0)$. Hence $\psi^{-1}(U\times (-\infty,0))$ is the collection of points $(x,t)$ with $t\in (\varphi(x),\infty)$, which is then open in $X\times [0,z')$. $\square$
Applying Lemma 1 to $U=X=M^{\times k}\setminus \Delta_k$ and $\varphi(P) = \max_{i\neq j}\{d(P_i,P_j)\}$, which is continuous, gives that $g_k^{-1}(U_{11\cdots1})\subseteq M^{\times k}\setminus \Delta_k$ is open. This also works to show that $g_k^{-1}(U_v)\subseteq g_k^{-1}(U_{v'})$ is open, for any $v'\leqslant v$, by limiting the pairs of indices iterated over by the function $\varphi$. Hence $g_k$ is continuous.
Step 3
The symmetric group $S_k$ acts on $(M^{\times k}\setminus \Delta_k)\times \R_{\geqslant 0}$ by permuting the order of elements in the first factor. That is, for $\sigma\in S_k$, we have
\[\sigma (P=\{P_1,\dots,P_k\},t) = (\{P_{\sigma(1)},\dots,P_{\sigma(k)}\},t).\]
Note that $((M^{\times k}\setminus \Delta_k)\times \R_{\geqslant 0})/S_k = \Ran^k(M)\times \R_{\geqslant 0}$.
Remark: Graph isomorphism for two graphs with $k$ vertices may also be viewed as the equivalence relation induced by $S_k$ acting on $\Gamma_k = \{$simple vertex-labeled graphs with $k$ vertices$\}$. First, let $G_v$ be the (unique) graph first introduced at element $v\in B_k$ by $g_k$. That is, we have $G_v =VR(P,t)_1$ (the ordered 1-skeleton of the Vietoris--Rips complex on the set $P$ with radius $t$) whenever $g_k((P,t))\in U_v$ and $g_k((P,t))\not\in U_{v'}$ for any $v'\leqslant v$, $v'\neq v$. Then the elements of $B_k$ are in bijection with the elements of $\Gamma_k$ (given by $v\leftrightarrow G_v$), so we have $B_k/S_k = B_k'$. Recall that $v\leqslant v'$ in $B_k$ iff adding an edge to $G_v$ gives $G_{v'}$. In $B_{k'}$, this becomes a partial order on equivalence classes $[w] = \{v\in B_k\ :\ \sigma G_v=G_w\ $for some $\sigma\in S_k\}$. We write $[w]\leqslant [w']$ iff there is a collection of pairs $\{(v_1,v_1'),\dots,(v_\ell,v_\ell')\}$ such that $v_i\leqslant v_i'$ for all $i$, and $\{v_1,\dots,v_\ell\} = [w]$ and $\{v_1',\dots,v_\ell'\} = [w']$ (there may be repetition among the $v_i$ or $v_i'$).
By the universal property of the quotient, there is a unique map $h_k:\Ran^k(M)\times \R_{\geqslant 0}\to B_k'$ that makes the following diagram commute.
No comments:
Post a Comment