Thursday, September 28, 2017

Exit paths, part 2

In this post we continue on a previous topic ("Exit paths, part 1," 2017-08-31) and try to define a constructible sheaf via universality. Let $X$ be an $A$-stratified space, that is, a topological space $X$ and a poset $(A,\leqslant)$ with a continuous map $f:X\to A$, where $A$ is given the upset topology relative to its ordering $\leqslant$. Recall the full subcategory $\Sing^A(X)\subseteq \Sing(X)$ of exit paths on an $A$-stratified space $X$.

Proposition: If $X\to A$ is conically stratified, $\Sing^A(X)$ is an $\infty$-category.

Briefly, a stratification $f:X\to A$ is conical if for every stratum there exists a particular embedding from a stratified cone into $X$ (see Lurie for "conical stratification" and Ayala, Francis, Tanaka for "conically smooth stratified space," which seem to be the same). We will leave confirming the described stratification as conical to a later post.

This proposition, given as part of Theorem A.6.4 in Lurie, has a very long proof, so is not repeated here. Lurie actually proves that the natural functor $\Sing^A(X)\to N(A)$ described below is a (inner) fibration, which implies the unique lifting property of $\Sing^A(X)$ via the unique lifting property of $N(A)$ (and we already know nerves are $\infty$-categories).

Example: The nerve of a poset is an $\infty$-category. Being a nerve, it is already immediate, but it is worthwhile to consider the actual construction. For example, if $A = \{a\leqslant b\leqslant c \leqslant d\}$ is the poset with the ordering $\leqslant$, then the pieces $N(A)_i$ are as below.
It is immediate that every 3-horn can only be filled in one unique way (as there is only one element of $N(A)_3$), as well as that every 2-horn can be filled in one unique way (as every sequence of two composable morphisms appears as a horn of exactly one element of $N(A)_2$).

In Appendix A.9 of Higher Algebra, Lurie says that there is an equivalence of categories \[(A\text{-constructible sheaves on }X)   \cong   \left[(A\text{-exit paths on }X),\mathcal S\right],\] given that $X$ is conically stratified, and for $\mathcal S$ the $\infty$-category of spaces (equivalently $N(Kan)$, the nerve of all the simplicial sets that are Kan complexes). So, instead of trying to define  a particular constructible sheaf on $X = \Ran^{\leqslant n}(M)\times \R_{\geqslant 0}$, (as in previous posts "Stratifying correctly," 2017-09-17 and "A constructible sheaf over the Ran space," 2017-06-24) we will try to make a functor that takes an exit path of $X$ and gives back a space.

Fix $n\in \Z_{>0}$ and set $X = \Ran^{\leqslant n}\times \R_{\geqslant 0}$. Let $SC$ be the category of simplicial complexes and simplicial maps, with $SC_n$ the full subcategory of simplicial complexes with at most $n$ vertices. There is a map
\[\begin{array}{r c l}
g\ :\ X & \to & SC_n \\
(P,t) & \mapsto & VR(P,t),
allowing us to say
\[X = \bigcup_{S\in SC_n}g^{-1}(S).\]
Here we consider that two elements $P_i,P_j\in P$ give an edge of $VR(P,t)$ whenever $t>d(P_i,P_j)$ (this is chosen instead of $t\geqslant d(P_i,P_j)$ so that the boundaries of the strata ``facing downward," with respect to the poset ordering, are open). Now we define a stratifying poset $A$ for $X$.

Definition: Let $A = \{a_S\ :\ S\in SC_n\}$ and define a relation $\leqslant$ on $A$ by
\[ \left(a_S\leqslant a_T\right)\ \ \Longleftarrow\ \ \left(
\exists\ \sigma\in \Sing(X)_1\ \text{such that}\\
g(\sigma(0))=S,\ g(\sigma(t>0))=T.
Let $(A,\leqslant)$ be the poset generated by relations of the type given above.

We claim that $f:X\to A$ given by $f(P,t)=a_{g(P,t)}$ is a stratifying map, that is, continuous in the upset topology on $A$. To see this, take the open set $U_S = \{a_T\in A\ :\ a_S\leqslant a_T\}$ in the basis of the upset topology of $A$, for any $S\in SC_n$, and consider $x\in f^{-1}(U_S)$. If for all $\epsilon>0$ we have $B_X(x,\epsilon)\cap f^{-1}(U_S)^C\neq \emptyset$, then there exists $T_\epsilon\in SC_n$ with $B_X(x,\epsilon)\cap f^{-1}(a_{T_\epsilon})\neq\emptyset$, for $S\not\leqslant T_\epsilon$ (as $T_\epsilon\not\in U_S$). This means there exists $\sigma\in \Sing(X)_1$ with $\sigma(0)=x$ and $\sigma(t>0)\in f^{-1}(a_{T_\epsilon})$, which in turn implies $S\leqslant T_\epsilon$, a contradiction. Hence $f$ is continuous, so $f:X\to A$ is a stratification.

As all morphisms in $\Sing(X)$ are compsitions of the face maps $s_i$ and degenracy maps $d_i$, so are all morphisms in $\Sing^A(X)$. There is a natural functor $F:\Sing^A(X)\to N(A)$ defined in the following way:
\[\begin{array}{r r c l}
%% L1
\text{objects} & \left(
\sigma:|\Delta^k|\to X \\
a_0\leqslant \cdots \leqslant a_k\subseteq A \\
f(\sigma(t_0,\dots,t_i\neq 0,0,\dots,0)) = a_i
\right) & \mapsto & \left( a_0\to\cdots\to a_k\in N(A)_k\right) \\[20pt]
%% L2
\text{face maps} & \left(
\sigma:|\Delta^k|\to X \\ a_0\leqslant \cdots \leqslant a_k\subseteq A
\downarrow \\[10pt]
\tau:|\Delta^{k+1}|\to X \\ a_0\leqslant \cdots \leqslant a_i\leqslant a_i\leqslant \cdots a_k\subseteq A
\right) & \mapsto &
\left(a_0\to\cdots \to a_k\right)\\[10pt]
\left(a_0\to\cdots \to a_i\xrightarrow{\text{id}}a_i\to\cdots \to a_k\right)
%% L3
\text{degeneracy maps} & \left(
\sigma:|\Delta^k|\to X \\ a_0\leqslant \cdots \leqslant a_k\subseteq A
\downarrow \\[10pt]
\tau:|\Delta^{k-1}|\to X \\ a_0\leqslant \cdots \leqslant a_{i-1}\leqslant a_{i+1}\leqslant \cdots a_k\subseteq A
\right) & \mapsto &
\left(a_0\to\cdots \to a_k\right)\\[10pt]
\left(a_0\to\cdots \to a_{i-1}\xrightarrow{\circ}a_{i+1}\to\cdots \to a_k\right)
As all maps in $\Sing^A(X)$ are generated by compositions of face and degeneracy maps, this completely defines $F$. Naturality of $F$ follows precisely because of this.

A poset (which can be viewed as a directed simple graph) may be naturally viewed as a 1-dimensional simplicial set, moreover an $\infty$-category (by virtue of being a \emph{simple} graph, with no multi-edges or loops). Hence there is a natural map, the inclusion, that takes $N(A)$ into $N(\mathcal Kan) = \mathcal S$.  Finally, Construction A.9.2 of Lurie describes a map that takes a functor from $A$-exit paths into spaces and gives back an $A$-constructible sheaf over $X$, which Theorem A.9.3 shows to be an equivalence, given the following conditions:
  • $X$ is paracompact,
  • $X$ is locally of singular shape,
  • the $A$-stratification of $X$ is conical, and
  • $A$ satisfies the ascending chain condition.
The first condition is satisfied as both $\Ran^{\leqslant n}(M)$ and $\R_{\geqslant 0}$ are locally compact and second countable. The last condition is satisfied because $A$ is a finite poset. We already mentioned that the conical property will be checked later, as will the singular shape property. Unfortunately, Lurie gives a definition of singular shape only for $\infty$-topoi, so some work must be done to translate this into our simpler setting. However, in the introduction to Appendix A, Lurie says that if $X$ is "sufficiently nice" and we assume some "mild assumptions" about $A$, then the described categorical equivalence follows, so it seems there is hope that everything will work out well in the end.

References: Stacks Project, Lurie (Higher algebra, Appendix A), Ayala, Francis and Tanaka (Local structures on stratified spaces, Sections 2 and 3)

Tuesday, September 26, 2017

Ordering simplicial complexes

In the context of trying to make a constructible sheaf over the Ran space, we have made several attempts to stratify $X=\Ran^{\leqslant n}(M)\times \R_{\geqslant0}$ correctly, the hope being for each stratum to have a unique simplicial complex (the Vietoris-Rips complex of the elements of $X$). In this post we make some observations and examine what it means to move around in $X$.

We use the convention that a Vietoris--Rips complex $VR(P,t)$ of an element $(P,t)\in X$ contains an edge $(P_i,P_j)$ iff $d(P_i,P_j)>t$ (as opposed to $d(P_i,P_j)\geqslant t$).

Observation 1: The VR complex $VR(P,t)$ is completely described by its 1-skeleton $sk_1(VR(P,t))$, as having a complete subgraph $K_\ell\subseteq sk_1(VR(P,t))$ is equivalent to $VR(P,t)$ having an $(\ell-1)$-cell spanning that subgraph. The 1-skeleton is a simple graph $G=(V,E)$ on $k$ vertices, so if we can order simple graphs with $\leqslant n$ vertices, we can order VR complexes of $\leqslant n$ vertices.

Let $\Gamma_k$ be the collection of simple gaphs on $k$ vertices. From now on we talk about an element $(P=\{P_1,\dots,P_k\},t)\in X$, a $k$-vertex VR complex $S=VR(P,t)$, and its 1-skeleton $G=sk_1(VR(P,t))\in \Gamma_k$ interchangeably. Consider the following informal defintion of how the stratification of $X$ should work.

Definition: A VR complex $S$ is ordered lower than another VR complex $T$ if there is a path from the stratum of type $S$ to the stratum of type $T$ that does not pass through strata of type $R$ with $|V(R)|<|V(S)|$ or $|E(R)|<|E(S)|$. If $S$ is ordered lower than $T$ and we can move from the stratum of type $S$ to the stratum of type $T$ without passing through another stratum, then we say that $S$ is directly below $T$.

To gain intuition of what this ordering means, consider the ordering on the posets $B_k'$, as defined in a previous post ("Stratifying correctly," 2017-09-17) and the 1-skeleta of the VR-complexes mapped to their elements. A complete description for $k=1,2,3,4$ and partially for $k=5$ is given below, with arrows $S\to T$ indicating the minimal number of directly below relationships. That is, if $S\to R$ but also $S\to T$ and $T\to R$, then $S\to R$ is not drawn.
The orderings on each $B_k'$ are clear and can be found in an algorithmic manner. However, it is more difficult to see which $S$ at level $k$ are directly below which $T$ at level $k+1$. The green arrows follow no clear pattern.

Observation 2: If $G\in \Gamma_k$ has an isolated vertex and $t>0$, then it can be directly below $H\in \Gamma_{k+1}$ only if $|E(H)|=|E(G)|+1$. In general, if the smallest degree of a vertex of $G\in \Gamma_k$ is $d$ and $t>0$, then $G$ can be directly below $H\in \Gamma_{k+1}$ only if $|E(H)|=|E(G)|+d+1$.

Recall the posets $B_k'$ are made by quotienting the nodes of the hypercube $B_k=\{0,1\}^{k(k-1)/2}$ by the action of $S_k$, where an element of $B_k$ is viewed as a graph $G\in \Gamma_k$ having an edge $(i,j)$ if the coordinate corresponding to the edge $(i,j)$ is 1 (there are $k(k-1)/2$ pairs $(i,j)$ of a $k$-element set).

Observation 3: It is not clear that $G$ not being ordered lower than $H$ in the hypercube context (order increases when increasing in any coordinate) implies that the VR complex of $G$ is not ordered lower than the VR complex of $H$ in $X$. No counterexample exists in the example given above, but this does not seem to exclude the possibility.

If any conclusion can be made from this, it is that this may not be the best approach to take when stratifying $X$.

Sunday, September 17, 2017

Stratifying correctly

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:
  1. Stratify $\Ran^{\leqslant n}(M)\times \R_{\geqslant 0}$ into $n$ pieces, each being $\Ran^k(M)\times \R_{\geqslant 0}$.
  2. Stratify $(M^{\times k}\setminus \Delta_k)\times \R_{\geqslant 0}$ as in the previous post.
  3. 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
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$.

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$,
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).
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.
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$.

Thursday, August 31, 2017

Exit paths, part 1

This post is meant to set up all the necessary ideas to define the category of exit paths.


 Let $X$ be a topological space and $C$ a category. Recall the following terms:
  • $\Delta$: The category whose objects are finite ordered sets $[n]=(1,\dots,n)$ and whose morphisms are non-decreasing maps. It has several full subcategories, including
    • $\Delta_s$, comprising the same objects of $\Delta$ and only injective morphisms, and
    • $\Delta_{\leqslant n}$, comprising only the objects $[0],\dots,[n]$ with the same morphisms.
  • equalizer: An object $E$ and a universal map $e:E\to X$, with respect to two maps $f,g:X\to Y$. It is universal in the sense that all maps into $X$ whose compositions with $f,g$ are equal factor through $e$. Equalizers and coequalizers are described by the diagram below, with universality given by existence of the dotted maps.
  • fibered product or pullback: The universal object $X\times_Z Y$ with maps to $X$ and $Y$, with respect to maps $X\to Z$ and $Y\to Z$.
  • fully faithful: A functor $F$ whose morphism restriction $\Hom(X,Y)\to \Hom(F(X),F(Y))$ is surjective (full) and injective (faithful).
  • locally constant sheaf: A sheaf $\mathcal F$ over $X$ for which every $x\in X$ has a neighborhood $U$ such that $\mathcal F|_U$ is a constant sheaf. For example, constructible sheaves are locally constant on every stratum. 
  • simplicial object: A contravariant functor from $\Delta$ to any other category. When the target category is $\text{Set}$, it is called a simplicial set. They may also be viewed as a collection $S = \{S_n\}_{\geqslant 0}$ for $S_n=S([n])$ the value of the functor on each $[n]$. Simplicial sets come with two natural maps:
    • face maps $d_i:S_n\to S_{n-1}$ induced by the map $[n-1]\to [n]$ which skips the $i$th piece, and
    • degeneracy maps $s_i:S_n\to S_{n+1}$ induced by the map $[n+1]\to[n]$ which repeats the $i$th piece.
  • stratification: A property of a cover $\{U_i\}$ of $X$ for which consecutive differences $U_{i+1}\setminus U_i$ have ``nicer" properties than all of $X$. For example, $E_i\to U_{i+1}\setminus U_i$ is a rank $i$ vector bundle, but there is no vector bundle $E\to X$ that restricts to every $E_i$.

Now we get into new territory.

Definition: The nerve of a category $C$ is the collection $N(C) = \{N(C)_n = Fun([n],C)\}_{n\geqslant 0}$, where $[n]$ is considered as a category with objects $0,\dots,n$ and a single morphism in $\Hom_{[n]}(s,t)$ iff $s\leqslant t$.

Note that the nerve of $C$ is a simplicial set, as it is a functor from $\Delta^{op}\to Fun(\Delta,C)$. Moreover, the pieces $N(C)_0$ are the objects of $C$ and $N(C)_1$ are the morphisms of $C$, so all the information about $C$ is contained in its nerve. There is more in the higher pieces $N(C)_n$, so the nerve (and simplicial sets in general) may be viewed as a generalization of a category.

Kan structures

Let $\text{sSet}$ be the category of simplicial sets. We may consider $\Delta^n = \Hom_\Delta(-,[n])$ as a contravariant functor $\Delta\to \text{Set}$, so it is an object of $\text{sSet}$.

Definition: Fix $n\geqslant 0$ and choose $0\leqslant i\leqslant n$. Then the $i$th $n$-horn of a simplicial set is the functor $\Lambda^n_i\subset \Delta^n$ generated by all the faces $\Delta^n(d_j)$, for $j\neq i$.

We purposefully do not describe what "$\subset$" or "generated by" mean for functors, hoping that intuition fills in the gaps. In some sense the horn feels like a partially defined functor (though it is a true simplicial set), well described by diagrams, for instance with $n=2$ and $i=1$ we have

Definition: A simplicial set $S$ is a Kan complex whenever every map $f:\Lambda^n_i\to S$ factors through $\Delta^n$. That is, when there exists a

The map $\iota$ is the inclusion. Moreover, $S$ is an $\infty$-category, or quasi-category, if the extending map $f'$ is unique.

Example: Some basic examples of $\infty$-categories, for $X$ a topological space, are
  • $Sing(X)$, made up of pieces $Sing(X)_n = \Hom(\Delta^n,X)$, and
  • $LCS(X)$, the category of locally constant sheaves over $X$. Here $LCS(X)_n$ over an object $A$, whose objects are $B\to A$ and morphisms are the appropriate commutative diagrams

Definition: A morphism $p\in \Hom_{\text{sSet}}(S,T)$ is a Kan fibration if for every commutative diagram (of solid arrows)

the dotted arrow exists, making the new diagram commute.

Definition: Let $C,D,A$ be categories with functors $F:C\to D$ and $G:C\to A$.
  • The left Kan extension of $F$ along $G$ is a functor $A\xrightarrow L D$ and a universal natural transformation $F\stackrel \lambda \rightsquigarrow L\circ G$.
  • The right Kan extension of $F$ along $G$ is a functor $A\xrightarrow R D$ and a universal natural transformation $R\circ G \stackrel \rho\rightsquigarrow F$.

Exit paths

The setting for this section is constructible sheaves over a topological space $X$. We begin with a slightly more technical definition of a stratification.

Definition: Let $(A,\leqslant)$ be a partially ordered set with the upset topology. That is, if $x\in U$ is open and $x\leqslant y$, then $y\in A$. An $A$-stratification of $X$ is a continuous function $f:X\to A$.

We now begin with a Treumann's definition of an exit path, combined with Lurie's stratified setting.

Definition: An exit path in an $A$-stratified space $X$ is a continuous map $\gamma:[0,1]\to X$ for which there exists a pair of chains $a_1\leqslant \cdots \leqslant a_n$ in $A$ and $0=t_0\leqslant \cdots \leqslant t_n=1$ in $[0,1]$ such that $f(\gamma(t))=a_i$ whenever $t\in (t_{i-1},t_i]$.

This really is a path, and so gives good intuition for what is happening. Recall that the geometric realization of the functor $\Delta^n$ is $|\Delta^n| = \{(t_0,\dots,t_n)\in \R^{n+1}\ :\ t_0+\cdots+t_n=1\}$. Oserving that $[0,1]\cong|\Delta^1|$, Lurie's definition of an exit path is more general by instead considering maps from $|\Delta^n|$.

Definition: The category of exit paths in an $A$-stratified space $X$ is the simplicial subset $Sing^A(X)\subset Sing(X)$ consisting of those simplices $\gamma:|\Delta^n|\to X$ for which there exists a chain $a_0\leqslant \cdots \leqslant a_n$ in $A$ such that $f(\gamma(t_0,\dots,t_i,0,\dots,0))=a_i$ for $t_i\neq 0$.

Example: As with all new ideas, it is useful to have an example. Consider the space $X=\Ran^{\leqslant 2}(M)\times \R_{\geqslant 0}$ of a closed manifold $M$ (see post "A constructible sheaf over the Ran space" 2017-06-24 for more). With the poset $(A,\leqslant)$ being $(a\leqslant b\leqslant c)$ and stratifying map
\begin{array}{r c l}
f\ :\ X & \to & A, \\
(P,t) & \mapsto & \begin{cases}
a & \text{ if } P\in \Ran^1(M), \\
b & \text{ if } P\in \Ran^2(M), t\leqslant d(P_1,P_2), \\
c & \text{ else,}
we can make a continuous map $\gamma:\Delta^3\to X$ by
\begin{array}{r c l}
(1,0,0) & \mapsto & (P\in \Ran^1(M),0), \\
(t_0,t_1\neq 0,0) & \mapsto & (P\in \Ran^2(M), d(P_1,P_2)), \\
(t_0,t_1,t_2\neq 0) & \mapsto & (P\in \Ran^2(M), t>d(P_1,P_2)).
Then $f(\gamma(t_0\neq 0,0,0))=a$, and $f(\gamma(t_0,t_1\neq 0,0))=b$, and $f(\gamma(t_0,t_1,t_2\neq 0))=c$, as desired. The embedding of such a simplex $\gamma$ is described by the diagram below.

Both the image of $(1,0,0)$ and the 1-simplex from $(1,0,0)$ to $(0,1,0)$ lie in the singularity set of $\Ran^{\leqslant 2}(M)\times \R_{\geqslant 0}$, which is pairs $(P,t)$ where $t=d(P_i,P_j)$ for some $i,j$. The idea that the simplex "exits" a stratum is hopefully made clear by this image.

References: Lurie (Higher algebra, Appendix A), Lurie (What is... an $\infty$-category?), Groth (A short course on $\infty$-categories, Section 1), Joyal (Quasi-categories and Kan complexes), Goerss and Jardine (Simplicial homotopy theory, Chapter 1), Treumann (Exit paths and constructible stacks)

Friday, August 11, 2017

The Ran space and singularity sets

Fix a manifold $M$ along with an embedding of $M$ into $\R^N$ and set $X=\Ran(M)\times \R_{\geqslant 0}$. The goal of this post is to show that every $(P,t)\in X$ has an open neighborhood that contains no points of the type $(Q,d(Q_i,Q_j))$, for some $i\neq j$. The collection of all such elements of $X$ is called the singularity set of $X$, as the Vietoris-Rips complex at $Q$ with such a radius changes at such elements.

Following Lurie, given a collection of open sets $\{U_i\}_{i=1}^k$ in $M$, set
\[\Ran(\{U_i\}_{i=1}^k) = \left\{P\in \Ran(M)\ :\ P\subset \bigcup_{i=1}^k U_i,\ P\cap U_i\neq \emptyset\ \forall\ i\right\}.\]
The topology on $\Ran(M)$ is the smallest topology for which every $\Ran(\{U_i\}_{i=1}^k)$ is open, for any $\{U_i\}_{i=1}^k$, for any $k$. The topology on the product $X$ is the product topology.

Remark: Note that the Ran space $\Ran(M)$ by itself can be split up into the pieces $\Ran^k(M)$, with "singularities" viewed as when a point splits into two (or more) points, or two (or more) combine into one. Then every element of $\Ran(M)$ is on the edge of the singularity set, as any neighborhood of a single point on the manifold contains two points on the manifold.

Fix $(P,t)\in X$ not in the singularity set of $X$, with $P=(P_1,\dots,P_k)$, for $1\leqslant k\leqslant n$. Set
\[\mu = \min\left\{t,\min_{1\leqslant i<j\leqslant k}\left\{|t-d(P_i,P_j)|\right\}\right\},\]
with distance $d$ being Euclidean distance in $\R^N$. The quantity $\mu$ should be thought of as the upper bound on how "far" we may move from $(P,t)$ without hitting the singularity set.

Proposition: Let $(P,t)$ be as above and $t,\alpha,\beta>0$ such that $\alpha+\beta=\mu$. Then
\[U=\Ran\left(\{B(P_i,\alpha/2)\}_{i=1}^k\right) \times \left(t-\beta,t+\beta\right)\]
is an open neighborhood of $(P,t)$ in $X$ and does not contain any points of the singularity set of $X$.

If $t=0$, then having $[0,\beta)$ as the second component of $U$, with $\alpha+\beta=\min_{i,j}d(P_i,P_j)$ works as the open neighborhood of $(P,t)$. The balls $B(x,r)$ are $N$-dimensional in $\R^N$. The proof is mostly applications of the triangle inequality.

Proof: By construction we have that $U$ is open in $X$ and that it contains $(P,t)$. For $(Q,s)\in U$ any other element, we have three cases. We will show that the distance between any two $Q_a,Q_b\in Q$ is never $s$. Fix distinct indices $\ell,m\in \{1,\dots,k\}$.
  1.  Case 1: $Q_a,Q_b\in B(P_\ell,\alpha/2)$. The situation looks as in the diagram below.
    Observe that $d(Q_a,Q_b)\leqslant d((Q_a,P_\ell)+d(Q_b,P_\ell) <\alpha = \mu-\beta \leqslant t-\beta$. Hence $d(Q_a,Q_b)<s$.
  2. Case 2: $Q_a\in B(P_\ell,\alpha/2), Q_b\in B(P_m,\alpha/2), d(P_\ell,P_m)>t$. The situation looks as in the diagram below.
    Observe that $d(P_\ell,P_m)\leqslant d(P_\ell,Q_b)+d(P_m,Q_b)\leqslant d(P_\ell,Q_a)+d(Q_a,Q_b)+d(P_m,Q_b) < \alpha+d(Q_a,Q_b)$. Since $d(P_\ell,P_m)>t$, the definition of $\mu$ gives us that $\mu \leqslant d(P_\ell,P_m)-t$, so combining this with the previous inequality, we get $d(Q_a,Q_b) > d(P_\ell,P_m)-\alpha\geqslant \mu+t-(\mu-\beta)=t+\beta$. Hence $d(Q_a,Q_b)>s$.
  3. Case 3: $Q_a\in B(P_\ell,\alpha/2), Q_b\in B(P_m,\alpha/2), d(P_\ell,P_m)<t$. The situation looks as in the diagram below.
    Observe that $d(Q_a,Q_b)\leqslant d(P_m,Q_b) + d(P_m,Q_a) \leqslant d(P_\ell,Q_a)+d(P_\ell,P_m)+d(P_m,Q_a)<\alpha+d(P_\ell,P_m)$. Since $d(P_\ell,P_m)<t$, the definition of $\mu$ gives us that $\mu\leqslant t-d(P_\ell,P_m)$, so combining this with the previous inequality, we get $d(Q_a,Q_b)<\mu-\beta+t-\mu = t-\beta$. Hence $d(Q_a,Q_b)<s$. $\square$
As an extension, it would be nice to show that the Vietoris--Rips complex of every element in $U$ is homotopy equivalent. This seems to be intuitively true, but a similar case analysis as above seems daunting.

References: Lurie (Higher Algebra, Section 5.5.1)

Thursday, August 3, 2017

New directions in TDA

 Conference topic

This post is informal, meant as a collection of (personally) new things from the workshop "Topological data analysis: Developing abstract foundations" at the Banff International Research Station, July 31 - August 4, 2017. New actual questions:
  1. Does there exist a constructible sheaf valued in persistence modules over $\Ran^{\leqslant n}(M)$?
    • On the stalks it should be the persistence module of $P\in \Ran^{\leqslant n}(M)$. What about arbitrary open sets?
    • Is there such a thing as a colimit of persistence modules?
    • Uli Bauer suggested something to do with ordering the elements of the sample and taking small open sets.
  2. Can framed vector spaces be used to make the TDA pipeline functorial? Does Ezra Miller's work help?
    • Should be a functor from $(\R,\leqslant)$, the reals as a poset, to $\text{Vect}$ or $\text{Vect}_{fr}$, the category of (framed) vector spaces. Filtration function $f:\R^n\to \R$ is assumed to be given.
    • Framed perspective should not be too difficult, just need to find right definitions.
    • Does this give an equivalence of categories (category of persistence modules and category of matchings)? Is that what we want? Do we want to keep only specific properties?
    • Ezra's work is very dense and unpublished. But it seems to have a very precise functoriality (which is not the main thrust of the work, however).
  3. Can the Bubenik-de Silva-Scott interleaving categorification be viewed as a (co)limit? Diagrams are suggestive.
    • Reference is 1707.06288 on the arXiv.
    • Probably not a colimit, because that would be very large, though the arrows suggest a colimit.
    • Have to be careful, because the (co)limit should be in the category of posets, not just interleavings.

New things to learn about:
  1. Algebraic geometry / homotopy theory: the etale space of a sheaf, Kan extensions, model categories, symmetric monoidal categories.
  2. TDA related: Gromov-Hausdorff distance, the universal distance (Michael Lesnick's thesis and papers), merge trees, Reeb graphs, Mapper (the program).

Saturday, June 24, 2017

A constructible sheaf over the Ran space

Let $M$ be a manifold. The goal of this post is to show that the sheaf $\mathcal F_{(P,t)}=\text{Rips}(P,t)$ valued in simplicial complexes over $\Ran^{\geqslant}(M)\times \R_{\geqslant 0}$ is constructible, a goal not quite achieved. This space will be described using filtered diagram of open sets, with the sheaf on consecutive differences of the diagram giving simplicial complexes of the same homotopy type.

Let $P=\{P_1,\dots,P_n\}\in \Ran(M)$. For every collection of open neighborhoods $\{U_i\owns P_i\}_{i=1}^n$ of the $P_i$ in $M$, there is an open neighborhood of $P$ in $\Ran(M)$ given by
\Ran(\{U_i\}_{i=1}^n) = \left\{Q\in \Ran(M)\ :\ Q\subset \bigcup_{i=1}^n U_i,\ Q\cap U_i\neq \emptyset\right\}.\]Moreover, these are a basis for any open neighborhood of $P$ in $\Ran(M)$.


We begin with a few facts about sets. Let $X$ be a topological space.

Lemma 1: Let $A,B\subset X$. Then:
  • (a) If $A\subset B$ is open and $B\subset X$ is open, then $A\subset X$ is open.
  • (b) If $A\subset B$ is closed and $B\subset X$ is open, then $A\subset X$ is locally closed.
  • (c) If $A\subset B$ is open and $B\subset X$ is locally closed, then $A\subset X$ is locally closed.
  • (d) If $A\subset B$ is locally closed and $B\subset X$ is locally closed, then $A\subset X$ is locally closed.
Proof: For part (a), first recall that open sets in $B$ are given by intersections of $B$ with open sets of $A$. Hence there is some $W\subset X$ open such that $A = B\cap W$. Since both $B$ and $W$ are open in $X$, the set $A$ is open in $X$.
     For part (b), since $A\subset B$ is closed, there is some $Z\subset X$ closed such that $A=B\cap Z$. Since $B$ is open in $X$, $A$ is locally closed in $X$.
     For parts (c) and (d), let $B = W_1\cap W_2$, for $W_1\subset X$ open and $W_2\subset X$ closed. For part (c), again there is some $W\subset X$ open such that $A = B\cap W$. Then $A = (W_1\cap W_2)\cap W = (W\cap W_1)\cap W_2$, and since $W\cap W_1$ is open in $X$, the set $A$ is locally closed in $X$.
     For part (d), let $A = Z_1\cap Z_2$, where $Z_1\subset B$ is open and $Z_2\subset B$ is closed. Then there exists $Y_1\subset X$ open such that $Z_1 = B\cap Y_1$ and $Y_2\subset X$ closed such that $Z_2 = B\cap Y_2$. So $A = Z_1\cap Z_2 = (B\cap Y_1) \cap (B\cap Y_2) = (B\cap Y_1)\cap Y_2$, where $(B\cap Y_1)\subset X$ is open and $Y_2\subset X$ is closed. Hence $A\subset X$ is locally closed. $\square$

Lemma 2: Let $U\subset X$ be open and $f:X\to \R$ continuous. Then $\bigcup_{x\in U}\{x\}\times (f(x),\infty)$ is open in $X\times \R$.

Proof: Consider the function
\begin{array}{r c l}
g\ :\ X\times \R & \to & X\times \R, \\
(x,t) & \mapsto & (x,t-f(x)).
\end{array}\]Since $f$ is continuous and subtraction is continuous, $g$ is continuous (in the product topology). Since $U\times (0,\infty)$ is open in $X\times \R$, the set $g^{-1}(U\times (0,\infty))$ is open in $X\times \R$. This is exactly the desired set. $\square$

Filtered diagrams

Definition: A filtered diagram is a directed graph such that
  • for every pair of nodes $u,v$ there is a node $w$ such that there exist paths $u\to w$ and $v\to w$, and
  • for every multi-edge $u\stackrel{1,2}\to v$, there is a node $w$ such that $u\stackrel 1\to v\to w$ is the same as $u\stackrel2\to v\to w$.
For our purposes, the nodes of a filtered diagram will be subsets of $\Ran^n(M)\times \R_{\geqslant 0}$ and a directed edge will be open inclusion of one set into another set (that is, the first is open inside the second). Although we require below that loops $u\to u$ be removed, we consider the first condition above to be satisfied if there exists a path $u\to v$ or a path $v\to u$.

Remark: In the context given,
  • edge loops $U\to U$ and path loops $U\to\cdots\to U$ may be replaced by a single node $U$ ($U\subseteq U$ is the identity),
  • multi-edges $U\stackrel{1,2}\to V$ may be replaced by a single edge $U\to V$ (inclusions are unique), and
  • multi-edges $U\to V\to U$ may be replaced by a single node $U$ (if $U\subseteq V$ and $V\subseteq U$, then $U=V$).
A diagram with all possible replacements of the types above is called a reduced diagram.
Lemma 3: In the context above, a reduced filtered diagram $D$ of open sets of any topological space $X$ gives an increasing sequence of open subsets of $X$, with the same number of nodes.

Proof: Order the nodes of $D$ so that if $U\to V$ is a path, then $U$ has a lower index than $V$ (this is always possible in a reduced diagram). Let $U_1,U_2,\dots,U_N$ be the order of nodes of $D$ (we assume we have finitely many nodes). For every pair of indices $i,j$, set
\delta_{ij} = \begin{cases}
\emptyset & \text{ if }U_i\to U_j\text{ is a path in }D, \\
U_i & \text{ if }U_i\to U_j\text{ is not a path in }D.
\end{cases}\]Then the following sequence is an increasing sequence of nested open subsets of $X$:
U_1 \to \delta_{12} \cup U_2 \to \delta_{13}\cup \delta_{23}\cup U_3 \to \cdots \to \underbrace{\left(\bigcup_{i=1}^{j-1}\delta_{ij} \right)\cup U_j}_{V_j} \to \cdots \to U_N.\]Indeed, if $U_i \to U_j$ is a path in $D$, then $U_i$ is open in $V_j$, as $U_i\subset V_j$. If $U_i\to U_j$ is not a path in $D$, then $U_i$ is still open in $V_j$, as $U_i\subset V_j$. As unions of opens are open, and by Lemma 1(a), $V_{j-1}$ is open in $V_j$ for all $1<j<N$. $\square$

Remark 4: Note that every consecutive difference $V_j\setminus V_{j-1}$ is a (not necessarily proper) subset of $U_j$.

Definition 5: For $k\in \Z_{>0}$, define a filtered diagram $D_k$ over $\Ran^k(M)\times \R_{\geqslant 0}$ by assigning a subset to every corner of the unit $N$-hypercube in the following way: for the ordered set $S=\{(i,j) \ :\ 1\geqslant i<j\geqslant k\}$ (with $|S|=N=k(k-1)/2$), write $P=\{P_1,\dots,P_k\}\in \Ran^k(M)$, and assign
(\delta_1,\dots,\delta_k) \mapsto \left\{
(P,t)\in \Ran^k(M)\times \R_{\geqslant 0}\ :\ t>d(P_{(S_\ell)_1},P_{(S_\ell)_2}) \text{ whenever }\delta_\ell=0,\ \forall\ 1\leqslant \ell\leqslant k
\right\},\]where $\delta_\ell\in \{0,1\}$ for all $\ell$, and $d(x,y)$ is the distance on the manifold $M$ between $x,y\in M$. The edges are directed from smaller to larger sets.

Remark 6: This diagram has $2^{k(k-1)/2}$ nodes, as $k(k-1)/2$ is the number of pairwise distances to consider. Moreover, the difference between the head and tail of every directed edge is elements $(P,t)$ for which $\text{Rips}(P,t)$ is constant. 

Example: For example, if $k=3$, then $2^{3\cdot2/2}=8$, and $D_3$ is the diagram below. For ease of notation, we write $\{t>\cdots\}$ to mean $\{(P,t)\ :\ P=\{P_1,P_2,P_3\}\in \Ran^3(M),\ t>\cdots\}$.

The diagram of corresponding Vietoris-Rips complexes introduced at each node is below. Note that each node contains elements $(P,t)$ whose Vietoris-Rips complex may be of type encountered in any paths leading to the node.

Lemma 7: In the filtered diagram $D_k$, every node is open inside every node following it.

Proof: The left-most node of $D_k$ may be expressed as
\{(P,t)\ :\ P=\{P_1,\dots,P_k\}\in \Ran^k(M), t>d(P_i,P_j)\ \forall\ P_i,P_j\in P\} = \bigcup_{P\in \Ran^k(M)} \{P\}\times \left(\max_{P_i,P_j\in P}\{d(P_i,P_j)\},\infty\right).\] Applying a slight variant of Lemma 2 (replacing $\R$ by an open ray that is bounded below), with the $\max$ function continuous, we get that the left-most node is open in the nodes one directed edge away from it. Repeating this argument, we get that every node is open inside every node following it. $\square$

The constructible sheaf

Recall that a constructible sheaf can be given in terms of a nested cover of opens or a cover of locally closed sets (see post "Constructible sheaves," 2017-06-13). The approach we take is more the latter, and illustrates the relation between the two. Let $n\in \Z_{>0}$ be fixed.

Definition: Define a sheaf $\mathcal F$ over $X=\Ran^{\leqslant n}(M)\times \R_{\geqslant 0}$ valued in simplicial complexes, where the stalk $\mathcal F_{(P,t)}$ is the Vietoris--Rips complex of radius $t$ on the set $P$. For any subset $U\subset X$ such that $\mathcal F_{(P,t)}$ is constant for all $(P,t)\in U$, let $\mathcal F(U)=\mathcal F_{(P,t)}$.

Note that we have not described what $\mathcal F(U)$ is when $U$ contains stalks with different homotopy types. Omitting this (admittedly large) detail, we have the following:

Theorem: The sheaf $\mathcal F$ is constructible.

Proof: First, by Remark in Lurie, we have that $\Ran^{n}(M)$ is open in $\Ran^{\leqslant n}(M)$. Hence $\Ran^{\leqslant n-1}(M)$ is closed in $\Ran^{\leqslant n}(M)$. Similarly, $\Ran^{\leqslant n-2}(M)$ is closed in $\Ran^{\leqslant n-1}(M)$, and so closed in $\Ran^{\leqslant n}(M)$, meaning that $\Ran^{\leqslant k}(M)$ is closed in $\Ran^{\leqslant n}(M)$ for all $1\leqslant k\leqslant n$. This implies that $\Ran^{\geqslant k}(M)$ is open in $\Ran^{\leqslant n}(M)$ for all $1\leqslant k\leqslant n$, meaning that $\Ran^k(M)$ is locally closed in $\Ran^{\leqslant n}(M)$, for all $1\leqslant k\leqslant n$.
     Next, for every $1\leqslant k\leqslant n$, let $V_{k,1}\to \cdots \to V_{k,N_k}$ be a sequence of nested opens covering $\Ran^k(M)\times \R_{\geqslant 0}$, as given in Definition 5 and flattened by Lemma 3. The sets are open by Lemma 7. This gives a cover $\mathcal V_k = \{V_{k,1},V_{k,2},\setminus V_{k,1},\dots,V_{k,N_k}\setminus V_{k,N_k-1}\}$ of $\Ran^k(M)\times \R_{\geqslant 0}=V_{k,N_k}$ by consecutive differences, with $V_{k,1}$ open in $V_{k,N_k}$ and all other elements of $\mathcal V_k$ locally closed in $V_{k,N_k}$, by Lemma 1(b). By Lemma 1 parts (c) and (d), every element of $\mathcal V_k$ is locally closed in $\Ran^{\leqslant n}(M)\times \R_{\geqslant 0}$, and so $\mathcal V = \bigcup_{k=1}^n \mathcal V_k$ covers $\Ran^{\leqslant n}(M)\times \R_{\geqslant 0}$ by locally closed subsets.
     Finally, by Remarks 4 and 6, over every $V\in\mathcal V$ the function $\text{Rips}(P,t)$ is constant. Hence $\mathcal F|_V$ is a locally constant sheaf, for every $V\in \mathcal V$. As the $V$ are locally closed and cover $X$, $\mathcal F$ is constructible. $\square$

References: Lurie (Higher algebra, Section 5.5.1)