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$.
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.
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$.
No comments:
Post a Comment