---
bibliography:
- 'persistence\_fp.bib'
---

[**Contractibility of a persistence map preimage**]{}

0.5cm [Jacek Cyranka$^{*,\dag}$ and Konstantin Mischaikow$^{*}$ ]{} 0.5cm [$^*$ Department of Mathematics, Rutgers, The State University of New Jersey,\
110 Frelinghusen Rd, Piscataway, NJ 08854-8019, USA]{}\
0.5cm [$^\dag$ Department of Computer Science and Engineering, University California, San Diego,\
9500 Gilman Drive, La Jolla, CA 92093-0404, USA]{} 0.5cm [jcyranka@gmail.com, mischaik@math.rutgers.edu]{} 0.5cm

[**Abstract.**]{} This work is motivated by the following question in data-driven study of dynamical systems: given a dynamical system that is observed via time series of persistence diagrams that encode topological features of solutions snapshots, what conclusions can be drawn about solutions of the original dynamical system? In this paper we provide a definition of a persistence diagram for a point in ${\mathbb{R}}^N$ modeled on piecewise monotone functions. We then provide conditions under which time series of persistence diagrams can be used to guarantee the existence of a fixed point of the flow on ${\mathbb{R}}^N$ that generates the time series. To obtain this result requires an understanding of the preimage of the persistence map. The main theorem of this paper gives conditions under which these preimages are contractible simplicial complexes.

#### Keywords:

[ Topological data analysis, persistent homology, dynamical systems, fixed point theorem.]{}

Introduction {#secintro}
============

*Topological data analysis* (TDA), especially in the form of persistent homology, is rapidly developing into a widely used tool for the analysis of high dimensional data associated with nonlinear structures. That topological tools can play a role in this subject should not be unexpected given the central role of nonlinear functional analysis in the study of geometry, analysis, and differential equations. What is perhaps surprising is that, to the best of our knowledge, there has been no systematic attempt to make use of nonlinear functional analysis as a tool to process information obtained via persistent homology.

Persistent homology is often used as a means of data reduction. A typical example takes the form of a complicated scalar function defined over a fixed domain, where the geometry of the sub-(super)-level sets is encoded via homology. Of particular interest to us are settings in which the scalar function arises as a solution to a partial differential equation, we are interested in tracking the evolution of the function, but experimental data only provides information on the level of digital images of the process. Furthermore, for many problems capturing the dynamics requires a long time series of rather large digital images. Thus, rather than storing the full images, one can hope to work with a time series of persistence diagrams.

The simplest mathematical analogy is that of attempting to describe the evolution of a partial differential equation via observations of the evolution of finite dimensional vectors obtained through a Galerkin projection. Obviously, since this is a central problem in numerical analysis this problem has been addressed in a variety of ways, including functional analysis. However, we are interested in going a step further. One can imagine that a piecewise linear function is associated with each finite dimensional vector, and to continue the analogy, the sublevel set persistence diagram for this function is computed. We would like to draw conclusions about the dynamics of the original partial differential equation from the time series of the persistence diagrams. This is an extremely ambitious goal and far beyond our capabilities at the moment. A much simpler question is the following: if there is an attracting region in the space of persistence diagrams, under what conditions can we conclude that there is a fixed point for the partial differential equation.

This paper represents a first step towards answering the simpler question. Theorem \[thmmaindyn\] shows that given a flow with a global compact attractor ${{\mathcal{A}}}\subset{\mathbb{R}}^N$ and a neighborhood of a particular form in the space of persistence diagrams, if under the dynamics the neighborhood is mapped into itself, then there exists a fixed point for the flow. Returning to the partial differential equation analogy, one could consider a system defined over an interval where the dynamics on the global attractor is obtained via a finite difference approximation.

The challenge, even in the simplified finite dimensional setting, is that to obtain results one must understand the topology of pre-images of sets under persistent homology, a topic for which there are only limited results. That the structure of pre-images is complicated follows directly from the fact that persistent homology can provide tremendous data reduction, but in a highly nonlinear fashion. We emphasize that simple examples show that the preimage set of a straight line path in a persistence diagram is nonconvex, see Figure \[figpre\].

With this in mind the primary goal of this paper is to show that for a reasonable class of bounded piecewise monotone continuous functions on a bounded interval the pre-image of a persistence diagram is composed of contractible, simplicial sets. The importance of this result is that it opens the possibility of applying standard algebraic topological tools, e.g. Lefschetz fixed point theorem, Conley index, to dynamics that is observed through the lens of persistent homology.

To state our goal precisely requires the introduction of notation. Throughout this paper ${{\mathcal{S}_N}}$ denotes a simplicial complex composed out of $N$ vertices and $N-1$ edges. More specifically, ${{\mathcal{S}_N}}= {{\mathcal{S}_N^{(0)}}}\cup {{\mathcal{S}_N^{(1)}}}$ where ${{\mathcal{S}_N^{(0)}}}$ denotes the $0$-skeleton of ${{\mathcal{S}_N}}$, i.e. the set of vertices $${{\mathcal{S}_N^{(0)}}}=\left\{ <i>\ |\ i=1,\dots,N \right\},$$ and ${{\mathcal{S}_N^{(1)}}}$ denotes the set of edges $${{\mathcal{S}_N^{(1)}}} = \left\{ <i,i+1>\ |\ i=1,\dots,N-1\right\}.$$ Observe that ${{\mathcal{S}_N}}$ can be viewed as a simplicial decomposition of a bounded interval $I\subset{\mathbb{R}}$. We are interested in sublevel set filtrations associated with piecewise monotone continuous functions on $I$, and thus we are interested in the following filtration on ${{\mathcal{S}_N}}$.

\[def:Sfiltration\] Let $z\in {\mathbb{R}}^N$. For $\theta\in {\mathbb{R}}$, define $${{\mathcal{S}_N}}(z,\theta) := {\left\{ {\sigma\in{{\mathcal{S}_N}}: f(z,\sigma)\leq \theta}\right\}}$$ where $f\colon {\mathbb{R}}^N\times{{\mathcal{S}_N}}\to {\mathbb{R}}$, is given by $$f(z,\sigma) := \begin{cases}
    z_j &\text{if $\sigma=<j>$,}\\
    \max{\left\{ {z_j, z_{j+1}}\right\}}&\text{if $\sigma=<j,j+1>$.}
    \end{cases}$$

\[defn:sublevelset\] Given $z=(z_1,\ldots,z_N)\in {\mathbb{R}}^N$, we can reorder the coordinates of $z$ such that $$z_{j_1} \leq z_{j_2} \leq \cdots \leq z_{j_N}.$$ The *sublevel-set filtration of ${{\mathcal{S}_N}}$ at $z$* is given by $${{\mathcal{S}_N}}(z,z_{j_1}) \subseteq  {{\mathcal{S}_N}}(z,z_{j_2}) \subseteq \cdots \subseteq {{\mathcal{S}_N}}(z,z_{j_N}).$$ and denoted by ${{\mathcal{S}_N^{{{\mathsf F}}}}}(z)$.

Since ${{\mathcal{S}_N^{{{\mathsf F}}}}}(z)$ is a finite filtration of simplicial complexes we can use the classical results from persistent homology [@ZC; @comptop] to compute the persistent homology of ${{\mathcal{S}_N^{{{\mathsf F}}}}}(z)$. Since for fixed $N$, ${{\mathcal{S}_N^{{{\mathsf F}}}}}(z)$ is completely determined by $z$, we treat this as a map $${\mathsf{Dgm}}\colon {\mathbb{R}}^N\to {\mathsf{Per}}$$ where ${\mathsf{Per}}$ denotes the space of all persistence diagrams. Furthermore, there are a variety of topologies that can be put on ${\mathsf{Per}}$ such that ${\mathsf{Dgm}}$ becomes a continuous map [@chazal; @stability].

If we replace $\max{\left\{ {z_j,z_{j+1}}\right\}}$ by $\min{\left\{ {z_j,z_{j+1}}\right\}}$ in the definition of $f$ and set\
${{\mathcal{S}_N}}(z,\theta) := {\left\{ {\sigma\in{{\mathcal{S}_N}}: f(z,\sigma)\geq \theta}\right\}}$, then the appropriate modification of Definition \[defn:sublevelset\] leads to a superlevel-set filtration of ${{\mathcal{S}_N}}$. The results of this paper are equally applicable in this setting, but the proofs must be modified appropriately.

Since ${\mathsf{Per}}$ is not a linear space, ${\mathsf{Dgm}}$ is far from a linear function. However, some restrictions of its image can be obtained from the values of the coordinates of $z$. For this reason it is useful to think of $z$ as a real valued function defined over its coordinate indices, i.e. $z\colon {\left\{ {1,\ldots,N}\right\}}\to {\mathbb{R}}$ where $z(i):=z_i$, $i=1,\ldots,N$.

\[defextr\] Let $z\in{\mathbb{R}}^N$. A *local minimum* of $z$ is a sequence of indices $\left\{i,{i+1},\dots,{i+n}\right\}$ such that $z(i) = z(i+1) = \dots = z(i+n)$, where $0 \leq n < N-1$, and it holds that

-   if $i-1\geq 1$, then $z(i-1) > m$,

-   if $i+n+1\leq N$, then $z(i+n+1) > m$.

A *local maximum* of $z$ is a sequence of indices $\left\{i,{i+1},\dots,{i+n}\right\}$ such that $z(i) = z(i+1) = \dots = z(i+n)$, where $0 \leq n < N-1$, and it holds that

-   if $i-1\geq 1$, then $z(i-1) < m$,

-   if $i+n+1\leq N$, then $z(i+n+1) < m$.

A *local extremum* of $z$ is either a local minimum of $z$ or a local maximum of $z$. A *boundary extremum* is a *local extremum* where $i=1$ or $i+n=N$. A local extremum that is not a boundary extremum is an *interior extremum*.

We say that $z$ is *monotone increasing* (*monotone decreasing*) over the set of indices ${\left\{ {k,k+1,\ldots, k+j}\right\}}$ if $z(k)\leq z(k+1) \leq \cdots \leq z(k+j)$ ($z(k)\geq z(k+1) \geq \cdots \geq z(k+j))$.

We make the following assumption for the remainder of this paper

A

:   The values of all local extrema of $z$ are distinct.

The important consequence of assumption [**A**]{} is the following proposition that is proven in Section \[sec:background\].

\[prop:singlePoints\] If $z\in{\mathbb{R}}^n$ satisfies assumption [**A**]{}, then each persistence point in ${\mathsf{Dgm}}(z)$ is unique.

As indicated above, given $A\subset {\mathsf{Per}}$ we are interested in the topology of ${\mathsf{Dgm}}^{-1}(A)$. For the moment we focus on the pre-image of a single persistence diagram for which it is useful to catalog the order of the local extrema.

The *critical value set* is given by $$\label{def:E+}
{{\mathcal{E}}}_+ := {\left\{ { h= (h_1,\ldots,h_n)\in {\mathbb{R}}^n : \text{$n$ is odd, and $h_{2k\pm 1} < h_{2k}$ for all $k$} }\right\}}.$$ Set ${{\mathcal{E}}}^n_+:= {\left\{ {h\in \mathcal{E}_+ : h\in{\mathbb{R}}^n}\right\}}$. We will also use the simpler notation ${{\mathcal{E}}}^n = {{\mathcal{E}}}^n_+$.

To obtain results concerning superlevel set persistence one requires the use of $$\label{def:E-}
{{\mathcal{E}}}_- := {\left\{ { h= (h_1,\ldots,h_n)\in {\mathbb{R}}^n : \text{$n$ is odd, and $h_{2k\pm 1} > h_{2k}$ for all $k$} }\right\}}$$

\[defcv\] We define a map $\operatorname{cv}\colon {\mathbb{R}}^N \to {{\mathcal{E}}}_+^n$ as follows. Assume $z\in {\mathbb{R}}^N$ has $n$ local extrema that are either interior extrema or boundary minima. Observe that this implies that $n$ is odd. Let ${i_j}$ be an index associated with the $j$-th extremum ordered such that $i_j < i_{j+1}$. Observe that $$\operatorname{cv}(z) := (z_{i_1},\ldots, z_{i_n})\in {{\mathcal{E}}}^n_+\subset{{\mathcal{E}}}_+.$$

\[ex:cv(z)\] Let $z=(1.5,-0.9,-0.9,1.1,2.1,1.4)\in {\mathbb{R}}^6$. The interior extrema are ${\left\{ {2,3}\right\}}$ and ${\left\{ {5}\right\}}$. The boundary extrema are ${\left\{ {1}\right\}}$ and ${\left\{ {6}\right\}}$. Thus $\operatorname{cv}(z)\in {{\mathcal{E}}}^3_+$ and $(i_1,i_2,i_3) = (2,5,6)$ or $(i_1,i_2,i_3) = (3,5,6)$. Finally, $h=\operatorname{cv}(z) = (-0.9,2.1,1.4)\in{{\mathcal{E}}}^3_+$.

As is discussed in Section \[sec:background\], if $\operatorname{cv}(z) = \operatorname{cv}(z')$, then ${\mathsf{Dgm}}(z) = {\mathsf{Dgm}}(z')$. Given $h\in{{\mathcal{E}}}_+$, set $$\label{eqCh}
C(h) := {\left\{ {z\in{\mathbb{R}}^N : \operatorname{cv}(z) = h}\right\}}.$$ Then, ${\mathsf{Dgm}}$ is constant on $C(h)$.

Using results of [@curry] in Section \[sec:background\] we prove the following result.

Let ${\mathsf{diag}}\in{\mathsf{Per}}$. Then the preimage of ${\mathsf{diag}}$ is composed of a finite number of mutually disjoint components $${\mathsf{Dgm}}^{-1}({\mathsf{diag}}) = \bigcup_{i=1}^{I({\mathsf{diag}})} C(h^i)$$ where $h^i\in {{\mathcal{E}}}_+$ and all the $h^i$, $i=1,\ldots, I({\mathsf{diag}})$ are related by permutations of the coordinates.

The main result of this paper is as follows.

\[thm:main\] Assume $z\in{\mathbb{R}}^N$ satisfies assumption [**A**]{}. Let $${\mathsf{Dgm}}^{-1}({\mathsf{Dgm}}(z)) = \bigcup_{i=1}^{I({\mathsf{Dgm}}(z))} C(\operatorname{cv}(z)^i).$$ Then for each $i$, $C(\operatorname{cv}(z)^i)$ is an union of a finite *contractible* set of *polytopes*.

Moreover, let ${\mathcal{B}}= \left\{z\in{\mathbb{R}}^N\colon z_1\in[-\bar{a},\bar{a}],\ z_N\in[-\bar{b},\bar{b}]\right\}$ for some $\bar{a},\bar{b} > 0$, and $z\in{\mathcal{B}}$ satisfies assumption [**A**]{}, then $C(\operatorname{cv}(z)^i)\subset{\mathcal{B}}$ is a *compact simplicial set*.

As is described below the proof of Theorem \[thm:main\] occupies the majority of this paper (Sections \[sec:background\] through \[seccontr\]). In Section \[preimageregions\] we prove Theorem \[thm:mainNdelta\]. This is an extension of Theorem \[thm:main\] to regions in ${\mathsf{Per}}$ of a particular form and is obtained by providing an explicit homotopy contracting the preimage of the region to the preimage of a single diagram that lies in the region. Theorem \[thmmaindyn\], described above, follows almost directly from Theorem \[thm:mainNdelta\], and is presented in Section \[secapplication\].

The proof of Theorem \[thm:main\] is extremely technical, involving an induction proof based on the number of persistence points or equivalently the number of local extrema pairs and requires substantial bookkeeping of subsets of ${\mathbb{R}}^N$.

We begin in Section \[sec:background\] with the necessary background information on sub-level set filtrations and persistence diagrams. We also recall the Nerve Theorem, which is the main tool that we use for our eventual proof of contractbility of the preimage set. The new content is a basic form of bookkeeping provided by convex polytopes covering the preimage set. By doing so we provide an easy proof that the preimage set $C(\operatorname{cv}(z)^i)$ is a finite union of polytopes (Proposition \[prop:Cpolytope\]).

Unfortunately, we are unable to prove contractibility using the representation presented in Section \[sec:background\]. Thus, in Section \[secindexing\] we introduce more complicated class of coverings of $C(\operatorname{cv}(z)^i)$. Fortunately, this class of coverings has the structure of a meet semi-lattice that we use extensively as a new form of bookkeeping.

Section \[secsubsets\] describes the preimage set in terms of star-shaped sets, generated by semi-lattice morphisms on the set of multi-indices. However, analyzing the topology of the nerve complex defined using those star-shaped sets directly turns out to be hard, and its intersection structure is unclear. Instead, we introduce a covering using more coarse sets.

Section \[secfirststep\] provides an argument for the initial step of the induction argument. To provide the reader with some intuition we illustrate the results with an example for a particular case.

Section \[secmotiv\] provides a motivating example for the contractibility inductive argument. We carry out formally the inductive argument for contractibility of the coarse covering in Section \[seccontr\].

Acknowledgements
----------------

The work of JC and KM was partially supported by grants NSF-DMS-1125174, 1248071, 1521771 and a DARPA contracts HR0011-16-2-0033.

In addition KM was partially supported by DARPA contract FA8750-17-C-0054 and NIH grant R01 GM126555-01.

Preliminaries {#sec:background}
=============

#### Notation

Throughout this paper $n$ and $N$ denote natural numbers where $n\leq N$.

Sublevel-set filtrations and persistence diagrams
-------------------------------------------------

Before we introduce finite dimensional dynamical systems we study in this paper, let us first introduce the crucial tool that we use to describe graphs determined by a finite number of points. We compute *persistent homology* of *sublevel-set filtrations* of one dimensional simplicial complexes. The vertices of the simplicial complex have associated values, determined by a graph. We define the *persistence map* as the a map assigning to each sublevel-set filtration its *persistence diagram* or (equivalently) *barcode*. Existing literature about persistent homology is very rich, see e.g. [@chazal; @comptop; @ZC] and references provided there. Here we briefly recall persistent homology theory to the extent it is required by our theory. We also prove some preliminary results about the preimage (fiber) of the persistence map.

Let $z\in{\mathbb{R}}^N$ be fixed. We define the persistence map as the map associating the filtered complex ${{\mathcal{S}_N^{{{\mathsf F}}}}}(z)$ its persistence diagram, or sometimes referred to as the *barcode* [@ghrist; @ZC].

Observe that ${{\mathcal{S}_N^{{{\mathsf F}}}}}(z)$ is an one dimensional filtered *cell complex*. The persistent homology of cell complexes is computed using by now standard *persistent homology* algorithms provided in [@comptop].

By *persistence diagram* we mean a set of points of the extended plane $$\mathbb{E} = {\mathbb{R}}\times {\mathbb{R}}\cup\{\infty\}.$$ We denote the space of persistence diagrams by $${\mathsf{Per}}\subset \mathbb{E},$$ For any diagram ${\mathsf{diag}}\in{\mathsf{Per}}$, and for each point $(b,d)\in{\mathsf{diag}}$, it holds that $b\leq d$. Moreover, in the one-dimensional setting there is necessarily one point having the coordinates $(b',\infty)$.

Here we do not study in detail the structure and decomposition of the persistence map. We define the *persistence map*, as the map which takes a function $f\colon{\mathbb{R}}^N\times{{\mathcal{S}_N}}\to{\mathbb{R}}$ and a vector $z\in{\mathbb{R}}^N$ to the persistence diagram encoding $0$-th order persistence homology of ${{\mathcal{S}_N^{{{\mathsf F}}}}}(z)$. Also, note that in our setting we deal only with the persistence map of degree $0$, associated with connected components.

It is known that the persistence map is $1$-Lipschitz, after equipping the category of persistent vector spaces with the *interleaving distance* [@chazal].

There exists a vast literature on algorithms computing the persistence diagram for general simplicial inputs, see e.g. [@comptop; @ZC] and references cited there. But, in the literature regarding computational homology the space of admissible functions is chosen in a way admitting a notion of *discrete Morse functions*, which in turn provides the standard notion of critical points. As a consequence, the cells where components of the sub-level set filtration are born/die can be indicated uniquely by algorithms computing the persistent homology. However, the algorithm can be easily altered to make it work in the setting of plateaus.

In our setting motivated by dynamical systems we do not make any assumption that would provide the standard notion of critical points. A function $f$ can include ’*plateaus*’, i.e. pieces of constant value. As a consequence the local extrema, where the components of the sublevel-set filtration are born or die are not necessary unique.

Let $${\mathsf{diag}}\in{\mathsf{Per}}$$ be a persistence diagram composed out of a finite number of points $\{p_1,p_2,\dots,p_n\}$.

Where the first point $p_1$ corresponds to the component of infinite persistence, we have $$\label{finpts}
    {\mathsf{diag}}= \left\{p_1 = (p_1,\infty),\ p_2 = (p_2^b,p_2^d),\ \dots,\ p_n = (p_n^b,p_n^d)\right\},$$ where it holds that $n < \infty$, and $$p_i^b\neq p_j^b\text{ for }i\neq j\text{, and }p_j^d > p^d_{j+1}.$$ Due to the Elder Rule [@curry; @comptop] property of the persistence map it must hold that $$\label{p1less}
  p_1 < p_j^b,\text{ for all }j>1.$$

The diagram ${\mathsf{diag}}$ has its associated *barcode*, which we denote by $B({\mathsf{diag}})$, and which is composed out of the following intervals $$\label{barcode}
  I_1 = [p_1,\infty),\quad I_2 = [p_2^b,p_2^d),\ \quad\dots,\quad I_n = [p_n^b,p_n^d).$$ Observe that from the following inclusion on barcodes must hold $$I_j \subset I_1.$$

We say that a function $f(z,\cdot)$ realizes the barcode $B({\mathsf{diag}})$ if it holds that ${\mathsf{Dgm}}(f,z) = {\mathsf{diag}}$. It was shown in [@curry] that there is at least one piecewise linear function realizing the barcode, and this argument can be transferred directly to our setting.

To distinguish functions realizing the barcode $B({\mathsf{diag}})$, we group them into equivalence classes. We remark that to characterize equivalence classes we can use the notion of *chiral merge tree* as defined in [@curry].

It was shown in \[Corollary 5.5, [@curry]\] that the number of chiral merge trees realizing a barcode $B$ is equal to $2^{N-1}\prod_{j=2}^N{\mu_B(I_j)}$, where $\mu_B(I_j)$ denotes the number of intervals in $B$ containing $I_j$.

Now we recall the known result saying that ${\mathsf{Per}}^{-1}({\mathsf{diag}})$ is composed out of a finite number of components. For the moment we use an abstract notion $C(\operatorname{cv}(z)^i)$, which we will make precise later. Each component is represented by a *chiral merge tree*, which was proved in [@curry] in the case of *Morse* functions. The functions we consider in our setting are not necessarily Morse, below we provide a suitable lemma fitted to our setting.

\[lempreim\] Let ${\mathsf{diag}}\in{\mathsf{Per}}$. Then the preimage ${\mathsf{Dgm}}^{-1}({\mathsf{diag}})\subset {\mathbb{R}}^N$ is composed out of a finite number of components $${\mathsf{Dgm}}^{-1}({\mathsf{diag}}) = \bigcup_{i=1}^{I({\mathsf{Dgm}}(z))}{C(\operatorname{cv}(z)^i)},$$ where ${\mathsf{diag}}= {\mathsf{Dgm}}(z)$. $C(\operatorname{cv}(z)^i)\subset {\mathbb{R}}^N$ is such that for $i\neq j$ it holds that

-   $C(\operatorname{cv}(z)^i)$, $C(\operatorname{cv}(z)^j)$ are not path connected, i.e. that for any $z\in C(\operatorname{cv}(z)^i)$ and $z'\in C(\operatorname{cv}(z)^j)$, there is no continuous path connecting $z$ with $z'$ in ${\mathsf{Dgm}}^{-1}({\mathsf{diag}})$.

-   each $C(\operatorname{cv}(z)^i)$ is characterized by the equivalence class of the associated chiral merge tree.

The proof follows naturally from the results in [@curry]. If two vectors in ${\mathsf{Dgm}}^{-1}({\mathsf{diag}})$ are such that the *chiral merge trees* associated with filtration functions $f(z,\cdot)$, $f(z',\cdot)$ are different. It follows that $z, z'$ have the same number of extrema, whose heights are determined by the persistence diagram ${\mathsf{diag}}$, but appearing in different permutations. Hance any continuous path modifying $z$ into $z'$ must change the heights of the local minima, and hence, the persistence diagram along this path must not be constant. Therefore, there is no continuous path in ${\mathsf{Dgm}}^{-1}({\mathsf{diag}})$, which connects $z$ with $z'$.

The case of super-level set filtrations is completely analogous, and we leave redoing the super-level case as an exercise for the reader.

Topology of $C(h)$ {#sec:C(h)}
------------------

Let us fix example $h\in {{\mathcal{E}}}^n_+$. In this subsection we show that $C(h)$ defined in is the union of a finite set of polytopes.

The set of *strictly ordered multi-indices* is given by $$L_m^N := \left\{(y_1,\dots,y_m)\in\{1,2,\dots,N\}^m\colon y_j < y_{j+1}\text{ for }1 \leq j < m\right\}.$$

\[defmonotone\] Let $h\in {{\mathcal{E}}}^n_+$ and $y\in L_n^N$. A point $z\in{\mathbb{R}}^N$ is *$(y,h)$-monotone* if the following conditions are satisfied.

1.  $z(y_k)=h_k$ for $k=1,\ldots,n$.

2.  $z$ is monotone increasing on ${\left\{ {1,\ldots,y_1}\right\}}$ and monotone decreasing on ${\left\{ {y_n,\ldots,N}\right\}}$.

3.  If $m$ is odd, then $z$ is monotone increasing on ${\left\{ {y_m,y_{m+1}}\right\}}$.

4.  If $m$ is even, $z$ is monotone decreasing on ${\left\{ {y_m,y_{m+1}}\right\}}$.

Observe that if $z$ is $(y,h)$-monotone, then $\operatorname{cv}(z) = h$.

If $z$ is as in Example \[ex:cv(z)\], then $z$ is $(y,\operatorname{cv}(z))$-monotone for $y=(2,5,6)$ or $y = (3,5,6)$.

Given $h\in {{\mathcal{E}}}^n_+$ define $S_h = S_{h,N,n}\colon L_n^N \to 2^{{\mathbb{R}}^{N}}$ by $$\label{slprop}
S_h(y) = S_{h,N,n} (y) := \left\{ z\in{\mathbb{R}}^{N}\colon \text{$z$ is $(y,h)$-monotone} \right\}.$$ Let $$\bar{a},\bar{b}>0$$ denote global bounds imposed on the first and the last components respectively and denote the subset of ${\mathbb{R}}^N$ having boundary elements bounded by $$\label{compactB}
{\mathcal{B}}= {\mathcal{B}}(\bar{a},\bar{b}) = \left\{z\in{\mathbb{R}}^N\colon z_1\in[-\bar{a},\bar{a}],\ z_N\in[-\bar{b},\bar{b}]\right\}.$$ Let $h\in {{\mathcal{E}}}^n_+$, define the compact version of $S_h = S_{h,N,n}\colon L_n^N \to 2^{{\mathcal{B}}}$ by $$\label{slpropcompact}
S_h(y) = S_{h,N,n} (y) := \left\{ z\in{\mathcal{B}}\colon \text{$z$ is $(y,h)$-monotone} \right\}.$$ Because most of the arguments are precisely the same regardless if we consider a compact or noncompact version of $S_h$ (the application in Section \[secapplication\] is the sole exception), we do not provide distinct symbols for these two objects.

Let $n=3$, $N=7$, $h = (0.5,3.5,2)$, and $y=(2,4,6)$. The possible coordinate values of $z\in S_{h,N,n}(y)\subset {\mathbb{R}}^7$ are shown in Figure \[fig:Sh\]. Observe that $S_{h,N,n}(y)$ is an unbounded convex set.

Let us relate a preimage component $C(h)$ with the definition of $(y,h)$-monotonicity. First, observe that

\[eqCh2\] $$\begin{aligned}
  C(h) &= \left\{ z\in{\mathbb{R}}^{N}\colon \text{$z$ is $(y,h)$-monotone for any $y\in L_n^N$} \right\},\text{ and}\\
  C(h) &= \bigcup_{y\in L_n^N}{S_h(y)}.\label{Chsum}\end{aligned}$$ We define analogously the compact version of $C(h)\colon L_n^N \to 2^{{\mathcal{B}}}$, using compact $S_h$’s.

\[prop:Spolytope\] Given $h\in {{\mathcal{E}}}^n_+$, and $y\in L_n^N$. The set $S_h(y) = S_{h,N,n}(y)$ defined by is a *closed convex polytope*. $S_h(y)\subset{\mathcal{B}}$ defined as is additionally *compact*.

From the definition $S_h(y) = S_{h,N,n}(y)$ is the intersection of a finite number of half-spaces $z_1\geq z_2$, $z_2 \geq z_3,\dots,z_{y_1-1}\geq z_{y_1}=h_1$ etc.. Therefore $S_{h,N,n}(y)$ is a closed convex polytope. In case $z\in{\mathcal{B}}$ it is additionally compact, as the boundary points $z_1,z_N$ have restricted values.

\[prop:Cpolytope\] Given $h\in {{\mathcal{E}}}^n_+$. The set $C(h)$ is a finite union of polytopes. $C(h)\subset {\mathcal{B}}$ is a compact simplicial set.

Follows directly from Prop \[prop:Spolytope\] showing that for each $y$ $S_h(y)$ is a closed convex polytope (and in case $S_h(y)\subset{\mathcal{B}}$, $S_h(y)$ is compact), and the identity .

\[remcompact\] $S_h(y)$ defined by is also a *unbounded convex set*, where only the boundary points take the unbounded values, see Figure \[fig:Sh\]. However, $S_h(y)\subset{\mathcal{B}}$ defined as $S_h(y) := \left\{ z\in{\mathcal{B}}\colon \text{$z$ is $(y,h)$-monotone} \right\}$ is obviously a compact convex set. Analogously, in the unbounded case $C(h)\subset{\mathbb{R}}^N$ is a finite union of polytopes, and $C(h)\subset{\mathcal{B}}$ is additionally compact, hence a simplicial set.

All elements of the proof of Theorem \[thm:main\] are the same regardless if we consider the polytope sets $S_h(y)$ being unbounded (over ${\mathbb{R}}^N$) or compact (over ${\mathcal{B}}$).

(0,0) – (0,5); (0,0) – (8,0);

(-0.1,0.5) – (0,0.5); (-0.1,1) – (0,1); (-0.1,1.5) – (0,1.5); (-0.1,2) – (0,2); (-0.1,2.5) – (0,2.5); (-0.1,3) – (0,3); (-0.1,3.5) – (0,3.5);

(1,-0.1) – (1,0.1); (2,-0.1) – (2,0.1); (3,-0.1) – (3,0.1); (4,-0.1) – (4,0.1); (5,-0.1) – (5,0.1); (6,-0.1) – (6,0.1); (7,-0.1) – (7,0.1);

(2,0.5) circle (2pt); (4,3.5) circle (2pt); (6,2) circle (2pt);

(1,0.5) – (1,5.5); (3,0.5) – (3,3.5); (5,2) – (5,3.5); (7,2) – (7,5.5);

(1,-0.3) node [$z_1$]{}; (2,-0.3) node [$z_2$]{}; (3,-0.3) node [$z_3$]{}; (4,-0.3) node [$z_4$]{}; (5,-0.3) node [$z_5$]{}; (6,-0.3) node [$z_6$]{}; (7,-0.3) node [$z_7$]{};

(-0.3,1) node [$1$]{}; (-0.3,2) node [$2$]{}; (-0.3,3) node [$3$]{};

Nerve Theorem {#secnerve}
-------------

The fundamental tool in our study of the topology of the persistence map preimage is the Nerve Theorem, below we recall it as Theorem \[thmnerve\]. It is elementary to observe that any preimage set of interest ($C(h)$) is a finite union of polytopes, see Proposition \[prop:Cpolytope\]. However, the polytopes constructing $C(h)$ can have arbitrary topology. By finding an appropriate family of sets that covering $C(h)$ (denoted in the sequel by $\Lambda_h$’s), we show that the nerve of that covering is the full simplex, and hence, $C(h)$ is homotopy equivalent to a point (contractible). See also Example \[exn5\]. Let $\|\cdot\|$ denote the support of a simplicial complex, let $[n]=\{1,2,\dots,n\}$. Let ${{\mathcal{A}}}= \{A_1, A_2,\dots, A_n\}$ be a family of sets. The *nerve* records the “intersection pattern” of ${{\mathcal{A}}}$. It is the simplicial complex denoted by ${{\mathcal{N}}}({{\mathcal{A}}})$, with vertex set $[n]$ and with simplices given by $${{\mathcal{N}}}({{\mathcal{A}}}) = \left\{ {{\mathcal{J}}}\subset[n]\colon\,\bigcap_{i\in{{\mathcal{J}}}}{A_i}\neq\emptyset\right\}.$$

\[thmnerve\] Let $K_1, K_2,\dots, K_n$ be subcomplexes of a finite simplicial complex $K$ that together cover $K$ (each simplex of $K$ is in at least one $K_i$), and let $A_i:=\|K_i\|$. Suppose that the intersection $\cap_{i\in {{\mathcal{J}}}}{A_i}$ is empty or contractible for each nonempty ${{\mathcal{J}}}\subset [n]$. Then $$\|{{\mathcal{N}}}(\{A_1,A_2,\dots,A_n\})\| \simeq \|K\|;$$ i.e., the nerve is homotopy equivalent to $K$.

Meet semi-lattices {#secmeet}
------------------

*A *meet-semilattice* $(L,\wedge)$ is a set $L$ with a binary operation $\wedge\colon L\times L\to L$ satisfying*

1.  (associativity) $w\wedge (x \wedge y) = (w\wedge x)\wedge y$,

2.  (symmetry) $w\wedge x = x\wedge w$, and

3.  (idempotency) $w\wedge w = w$.

A classical example of a meet-semilattice comes from set theory. Given a set $X$, let $2^X$ denote its power set. Then, $(2^X,\cap)$ is a meet-semilattice.

Indexing sets {#secindexing}
=============

As indicated in the Introduction the proof of Theorem \[thm:main\] makes use of a complicated class of coverings. The remainder of this section introduces the notation used to index these coverings.

\[def:calL\]

*For $n\leq N$, we denote the set of [*multi-indices*]{} by $\mathbb{L}_{2n}^N\subset \{1,\dots,N\}^{2n}$ and define it to consist of the vectors $w=( w_1,\dots,w_{2n} )$ that satisfy the following four conditions for all $k=1,\ldots, n-1$.*

1.  $w_{2k-1}\leq w_{2k}$

2.  $w_{2k-1}< w_{2k+1}$

3.  $w_{2k} < w_{2k+2}$

4.  $w_{2k+1} \leq w_{2k+2}$.

The order relation in $\mathbb{L}_{2n}^N$ is summarized in Figure \[fig:Lorder\]. Condition (ii) implies that the assumption that $n\leq N$ is necessary. Observe that if $n=N$, then $\mathbb{L}_{2n}^N = \{(1,1,2,2,\ldots,N,N)\}$ consists of a single element.

\(1) at (1,0) [$w_1$]{}; (2) at (0,1) [$w_2$]{}; (3) at (2,1) [$w_3$]{}; (4) at (1,2) [$w_4$]{}; (5) at (3,2) [$w_5$]{}; (6) at (2,3) [$w_6$]{}; (7) at (4,3) [$w_7$]{}; (8) at (3,4) [$w_8$]{};

\(1) edge\[-, dashed, shorten &lt;= 2pt, shorten &gt;= 2pt\] (2) (1) edge\[-,shorten &lt;= 2pt, shorten &gt;= 2pt\] (3) (2) edge\[-,shorten &lt;= 2pt, shorten &gt;= 2pt\] (4) (3) edge\[-,dashed,shorten &lt;= 2pt, shorten &gt;= 2pt\] (4) (3) edge\[-,shorten &lt;= 2pt, shorten &gt;= 2pt\] (5) (4) edge\[-,shorten &lt;= 2pt, shorten &gt;= 2pt\] (6) (5) edge\[-,dashed,shorten &lt;= 2pt, shorten &gt;= 2pt\] (6) (5) edge\[-,shorten &lt;= 2pt, shorten &gt;= 2pt\] (7) (6) edge\[-,shorten &lt;= 2pt, shorten &gt;= 2pt\] (8) (7) edge\[-,dashed,shorten &lt;= 2pt, shorten &gt;= 2pt\] (8) ;

\[ex:bbL34\] The simplest nontrivial example of a set of multi-indices is $$\begin{aligned}
\mathbb{L}_{4}^3 & = {\left\{ {(w_1,w_2,w_3,w_4) : w_1\leq w_2, w_3\leq w_4, w_1 < w_3, w_2 < w_4}\right\}} \\
& = {\left\{ {(1122),(1123),(1133),(1223),(1233),(2233)}\right\}}\end{aligned}$$

Define $\wedge \colon \mathbb{L}_{2n}^N\times \mathbb{L}_{2n}^N \to \mathbb{L}_{2n}^N$ by $w\wedge w' = ((w\wedge w')_1, \ldots ,(w\wedge w')_{2n})$ where $$(w\wedge w') _ k = \begin{cases}
\min\{ w_k,w'_k\} & \text{if $k$ odd,} \\
\max\{ w_k,w'_k\} & \text{if $k$ even.} 
\end{cases}$$

\[thm:Lsemilattice\] $(\mathbb{L}_{2n}^N ,\wedge)$ is a meet-semilattice.

We begin by showing that if $w,w'\in\mathbb{L}_{2n}^N$, then $w'' = w\wedge w'\in \mathbb{L}_{2n}^N$. We need to show that $w'' = (w''_1,\ldots,w''_{2n})$ satisfies conditions (i)-(iv) of Definition \[def:calL\]. Since $w_{2k-1} \leq w_{2k}$ and $w'_{2k-1} \leq w'_{2k}$ $$w''_{2k-1}:= \min\{w_{2k-1},w'_{2k-1}\} \leq \max\{w_{2k},w'_{2k}\} = w''_{2k}$$ and thus (i) is satisfied. To see that (ii) is satisfied we note that $w_{2k-1} < w_{2k+1}$ and $w'_{2k-1} < w'_{2k+1}$ implies that $$w''_{2k-1}:= \min\{w_{2k-1},w'_{2k-1}\} < \min\{w_{2k+1},w'_{2k+1}\} = w''_{2k+1}.$$ Similar arguments apply to (iii) and (iv).

Checking that $\wedge$ is associative, symmetric, and idempotent is straightforward.

We denote the set of *ordered multi-indices* by $$\label{ordmultind}
\mathcal{L}_{2n}^N := \left\{ ( x_1,\dots,x_{2n} ) \in \{ 1,\dots,N\}^{2n}\colon x_{2k-1}\leq x_{2k}\text{ for $1\leq k \leq n$ and }x_{2k}<x_{2k+1}\text{ for $1\leq k \leq n-1$} \right\}$$ Observe that $\mathcal{L}_{2n}^N\subset \mathbb{L}_{2n}^N$. However, $\mathcal{L}_{2n}^N$ is not a sub meet-semilattice of $\mathbb{L}_{2n}^N$. To see this assume that $x,x'\in \mathcal{L}_{2n}^N$ and that $x'_{2k} < x'_{2k+1} < x_{2k} < x_{2k+1}$. Let $x'' = x'\wedge x$. Then $x''_{2k} = x_{2k} \not< x'_{2k+1} = x''_{2k+1}$, which implies that $x''\not\in\mathcal{L}_{2n}^N$.

\[ex:calL34\] The simplest nontrivial example of a set of ordered multi-indices is $$\begin{aligned}
\mathcal{L}_{4}^3 & = {\left\{ {(x_1,x_2,x_3,x_4) : x_1\leq x_2 < x_3\leq x_4}\right\}} \\
& = {\left\{ {(1122),(1123),(1133),(1233),(2233)}\right\}}\end{aligned}$$

Recall the strictly ordered multi-indices $L_{2n}^N$ defined in Section \[sec:C(h)\] and observe that $$L_{2n}^N\subset\mathcal{L}_{2n}^N\subset \mathbb{L}_{2n}^N.$$ Again, $L_{2n}^N$ is not a sub meet-semilattice of $\mathbb{L}_{2n}^N$.

We now define functions that takes arbitrary multi-indices and produces sets of pairs of strictly ordered multi-indices, i.e., maps $\varphi_i\colon \mathbb{L}^{N-1}_{2(n-1)}\to 2^{L^N_{n}\times L^N_{n}}$, $i=1,\ldots, n-2$. Set $$\label{varphik1}
\varphi_1(w) =
\begin{cases}
\left\{ (y,y)\in L^N_n\times L^N_n : y_1 \leq w_{1},\ w_{2} < y_{2} \leq w_{3}\right\} & \text{if $w_{2} < w_{3}$,} \\
\Big\{ (y,y')\in L^N_n\times L^N_n : y_1 \leq w_{1},\ y_{2} = w_{3},\ y'_{2} = w_{2}+1,\ \text{$y_j=y'_j$ for $j\neq 2$}\Big\} & \text{if $w_{3}\leq w_{2}$.}
\end{cases}$$ For $k=2,\dots,n-3$, define $\varphi_k= \varphi_{k,N,n}\colon \mathbb{L}_{2(n-1)}^{N-1} \to 2^{L_{n}^N}\times 2^{L_{n}^N}$ by $$\label{varphi}
\varphi_k(w) =
\begin{cases}
\left\{ (y,y)\in L^N_n\times L^N_n : w_{2k} < y_{k+1} \leq w_{2k+1}\right\} & \text{if $w_{2k}<w_{2k+1}$,} \\
\Big\{ (y,y')\in L^N_n\times L^N_n : y_{k+1} = w_{2k+1},\ y'_{k+1} = w_{2k}+1,\  \text{$y_j=y'_j$ for $j\neq k+1$}\  \Big\} & \text{if $w_{2k+1}\leq w_{2k}$.}
\end{cases}$$ And $$\label{varphiknm2}
\varphi_{n-2}(w) =
\begin{cases}
\left\{ (y,y)\in L^N_n\times L^N_n : w_{2(n-2)} < y_{n-1} \leq w_{2(n-2)+1},\ w_{2(n-1)} < y_{n} \right\} & \text{if $w_{2(n-2)}<w_{2(n-2)+1}$,} \\
\Big\{ (y,y')\in L^N_n\times L^N_n : y_{n-1} = w_{2(n-2)+1},\ y'_{n-1} = w_{2(n-2)}+1,\ w_{2(n-1)} < y_{n}\\
\qquad\qquad\qquad\qquad\qquad\qquad\quad\quad\quad\quad\quad\quad\text{$y_j=y'_j$ for $j\neq n-1$}\  \Big\} & \text{if $w_{2(n-2)+1}\leq w_{2(n-2)}$.}
\end{cases}$$

[ *If $n=3$ and $N=7$, then $\varphi_1\colon \mathbb{L}_{4}^{6} \to 2^{L_{3}^7}\times 2^{L_{3}^7}$. Furthermore, if $w=(2,4,3,6)$, then $$\varphi_1(w) = \big\{\big((1,3,7),(1,5,7) \big),\big( (2,3,7),(2,5,7) \big) \big\}.$$* ]{}

[ *If $n=4$ and $N=6$, then $\varphi_k\colon \mathbb{L}_{6}^{5} \to 2^{L_{4}^6}\times 2^{L_{4}^6}$, for $k =1,2$. Furthermore, if $w=(1,2,2,3,3,4)$, then $$\begin{aligned}
\varphi_1(w) & = \big\{\big((1,2,4,5),(1,3,4,5) \big),\big( (1,2,4,6),(1,3,4,6) \big),\big( (1,2,5,6),(1,3,5,6) \big) \big\} \\
\varphi_2(w) & = \big\{\big((1,2,3,5),(1,2,4,5) \big),\big( (1,2,3,6),(1,2,4,6) \big)  \big\}\end{aligned}$$* ]{}

The action of all the $\varphi_k$ restricted to ordered multi-indices $\mathcal{L}_{2(n-1)}^{N-1}$ is relatively easy to describe. Define $\rho = \rho_{N,n} \colon \mathcal{L}_{2(n-1)}^{N-1} \to 2^{L_{n}^N}$ by $$\label{rhoo}
\rho(x) = \left\{ y \in L_{n}^N  : y_1 \leq x_1,\ x_{2(k-1)} <  y_k \leq x_{2(k-1)+1},\ x_{2(n-1)} < y_n,\  k=2,\ldots, n-1 \right\}$$

Let $n=4$, $N=6$. Then $\rho\colon {{\mathcal{L}}}_6^5 \to L_4^6$,

$$\rho(112244) = \left\{y\in L_4^6\colon y_1\leq 1,\ 1<y_2\leq 2,\ 2<y_3\leq 4,\ 4<y_4\right\} = \left\{ 1235, 1236, 1245, 1246 \right\}.$$

\[lem:rho\] Let $x\in \mathcal{L}_{2(n-1)}^{N-1}$. If $(y,y')\in \varphi_k(x)$, then $y'=y$ and $$\{(y,y) : y\in \rho(x)\} = \bigcap_{k=1}^{n-2} \varphi_k(x).$$

If $x\in \mathcal{L}_{2(n-1)}^{N-1}$, then $x_{2k}<x_{2k+1}$ and hence $$\varphi_k(x) = \{(y,y) : y_k\leq x_{2k-1},\ x_{2k}<y_{k+1} \leq x_{2k+1},\ x_{2(k+1)}< y_{k+2}\}.$$ Therefore, $$\bigcap_{k=1}^{n-2} \varphi_k(x) = \{(y,y) : y_1\leq x_{1},\ x_{2(k-1)} <  y_k \leq x_{2(k-1)+1},\ x_{2(n-1)} < y_n,\  k=2,\ldots, n-1\}$$ which by definition of $\rho(x)$ is equal to the set $\{(y,y): y\in\rho(x)\}$.

For $n < N$, set $$\mathcal{P}_{2n}^{N}:={\left\{ { (x_1,\dots,x_{2n} ) \in \{1,\dots,N\}^{2n} : x_{2k-1}=x_{2k} < x_{2k+1}=x_{2k+2},\ k= 1,\ldots, n-1}\right\}} \subset \mathcal{L}_{2n}^{N}.$$ Observe that $\mathcal{P}_{2n}^{N}\subset \mathcal{L}_{2n}^{N}\subset \mathbb{L}_{2n}^{N}$, but it is not a sub-lattice of $\mathbb{L}_{2n}^N$.

\[ex:calP34\] The simplest nontrivial example is $$\begin{aligned}
\mathcal{P}_{4}^3 & = {\left\{ {(x_1,x_2,x_3,x_4) : x_1 = x_2 < x_3 = x_4}\right\}} \\
& = {\left\{ {(1122),(1133),(2233)}\right\}}\end{aligned}$$

We make use of ordered multi-indices (pairs) on the restricted domain, i.e. $$\mathcal{L}_2^{n-3,N-3} := \left\{ ( x_1,x_2 ) \in \{ n-3,\ldots,N-3\}^{2} : x_1\leq x_2 \right\}.$$ in conjunction with a map $\theta\colon \mathcal{L}_2^{n-3,N-3} \to 2^{\mathcal{P}^{N-1}_{2(n-1)}}$ given by $$\label{thetadef}
\theta((p_1,p_2)) := \left\{ (y_1,\dots, y_{2(n-1)}) : \ y_{2(n-3)}\leq p_1\leq p_2<y_{2(n-3)+1}\right\}.$$

Let $N=6$ and $n=5$. Then, $$\mathcal{L}_2^{n-3,N-3} = \mathcal{L}_2^{2,3} = \left\{ ( x_1,x_2 ) \in \{ 2,3\}^{2} : x_1\leq x_2\right\} =\left\{ ( 22 ), (23), (33) \right\}$$ Then $$\theta\colon \mathcal{L}_2^{2,3} \to 2^{\mathcal{P}^{5}_{8}},$$ and hence we have $$\begin{aligned}
\theta(22) &= \left\{ 11223344, 11223355, 11224455\right\},\\
\theta(23) &= \left\{ 11224455 \right\},\\
\theta(33) &= \left\{ 11224455, 11334455, 22334455\right\}.\end{aligned}$$

\[propthetap\] It holds that $$\label{eqpx}
\bigcup_{\substack{p\in\mathcal{L}_2^{n-3,N-3}\\p=(p_1,p_1)}}{ \theta(p_1,p_2) } = \mathcal{P}_{2(n-1)}^{N-1}.$$

Let $x\in\mathcal{P}_{2(n-1)}^{N-1}$. Let $p\in\mathcal{L}_2^{n-3,N-3}$ be such that $$p_1 = p_2 = x_{2(n-3)},$$ then from the definition it holds that $x\in\theta(p_1,p_2)$. Hence, as $x$ is arbitrary, we showed that it holds that $\bigcup_{\substack{p\in\mathcal{L}_2^{n-3,N-3}\\p = (p_1,p_2) }}{ \theta(p_1,p_1) } = \mathcal{P}_{2(n-1)}^{N-1}$.

\[propKwedgeM\] For any $p,q\in \mathcal{L}_2^{n-3,N-3}$ it holds that $$\theta((p_1,p_2))\cap\theta((q_1,q_2)) = \theta( (p_1, p_2) \wedge (q_1, q_2) ).$$

We need to show that $$\theta\left( (p_1,p_2)\wedge (q_1,q_2) \right) = \theta\left(\min\{p_1,q_1\},\max\{p_2,q_2\}\right) =
\theta\left((p_1,p_2)\right)\cap\theta\left((q_1,q_2)\right).$$ First, observe that from $(p_1, p_2),\,(q_1, q_2)\in \mathcal{L}_2^{n-3,N-3}$ it follows that $$(p_1, p_2) \wedge (q_1, q_2) = (\min\{p_1,q_1\},\max\{p_2,q_2\})\in \mathcal{L}_2^{n-3,N-3},$$ as if $p_1\leq p_2$ and $q_1\leq q_2$, then $\min\{p_1,q_1\}\leq \max\{p_2,q_2\}$.

From the definition of map $\theta$ , we have $$\theta\left((p_1,p_2)\right)\cap\theta\left((q_1,q_2)\right)=
\left\{ (y_1,\dots, y_{2(n-1)}) : \ y_{2(n-3)}\leq \min\{p_1,q_1\}\leq \max\{p_2,q_2\}<y_{2(n-3)+1}\right\}.$$ Therefore, we obtain the claim.

\[lemtheta\] Let $p=(p_1,p_2), q=(q_1,q_2) \in \mathcal{L}_2^{n-3,N-3}$. For any $w\in\theta((p_1,p_2))$, and $z\in\theta((q_1,q_2))$. It holds that $$w\wedge z < y,$$ for some $$y \in \theta((p_1, p_2)) \cap \theta((q_1, q_2)).$$

We have that $$w\wedge z = \left(\min\{ w_1 , z_1 \}, \max\{ w_2, z_2 \}, \min\{ w_3, z_3 \}, \max\{ w_4, z_4 \},\dots, \min\{ w_{2(n-1)-1}, z_{2(n-1)-1} \}, \max\{ w_{2(n-1)}, z_{2(n-1)} \}\right).$$ Let us take $$y = \left(\min\{ w_1 , z_1 \}, \min\{ w_2, z_2 \}, \max\{ w_3, z_3 \}, \max\{ w_4, z_4 \},\dots, \max\{ w_{2(n-1)-1}, z_{2(n-1)-1} \}, \max\{ w_{2(n-1)}, z_{2(n-1)} \}\right).$$

As $$\min\{w_{2(n-3)-1},z_{2(n-3)-1}\},\,\min\{ w_{2(n-3)}, z_{2(n-3)} \} \leq \min\{p_1,q_1\},$$ and $$\max\{p_2,q_2\} < \max\{ w_{2(n-3)+1}, z_{2(n-3)+1} \},\,\max\{ w_{2(n-2)}, z_{2(n-2)} \}.$$ It holds that $$y \in \theta((p_1,p_2)) \cap \theta((q_1,q_2)) = \theta((p_1,p_2)\wedge(q_1,q_2)).$$ And from the definition $$(w\wedge z)\wedge y = w\wedge z.$$ Hence $$w\wedge z < y.$$

Let $p=(p_1,p_2), q=(q_1,q_2) \in \mathcal{L}_2^{n-3,N-3}$. For any $w\in\theta((p_1,p_2))$, and $z\in\theta((q_1, q_2))$ it holds that $$A_h(w\wedge z) \subset A_h(y),$$ for some $$y \in \theta((p_1, p_2)) \cap \theta((q_1, q_2)).$$

Follows from Corollary \[corineq\] and Lemma \[lemtheta\].

Semilattice representation of Euclidean space {#secsubsets}
=============================================

In Section \[sec:C(h)\] it is shown that $C(h)$ is the union of a finite set of polytopes of the form $S_{h,N,n}(y)$. However, to prove Theorem \[thm:main\] we also need to show that $C(h)$ is contractible. We do this by describing $C(h)$ in terms of star-shaped sets, generated by semi-lattice morphisms $A_h$ defined on set of multi-indices $\mathbb{L}$. The focus of this section is on obtaining and characterizing this description.

\[defn:Ah\] Given $h\in {{\mathcal{E}}}^n_+$ define $A_h = A_{h,N,n}\colon \mathbb{L}_{2(n-1)}^{N-1} \to 2^{{\mathbb{R}}^{N}}$ by $$\label{aprop}
A_h(w) = A_{h,N,n}(w) = \bigcap_{k=1}^{n-2} \left( \bigcup_{(y,y')\in \varphi_k(w)} S_h(y)\cap S_h(y')  \right)$$

Exactly the same arguments presented in this section are also true in the compact case, i.e. when the presented construction is based on the compact polytopes $S_h\subset{\mathcal{B}}$ defined using . This will ultimately allow for proving Theorem \[thm:main\] in the compact case.

We begin by analyzing how $A_h$ acts on $\mathcal{L}_{2(n-1)}^{N-1}$.

\[lemSintersect\] If $x\in \mathcal{L}_{2(n-1)}^{N-1}$, then $$\bigcap_{k=1}^{n-2}\bigcup_{(y,y)\in\varphi_k(x)}{S_h(y)} = \bigcup_{(y,y)\in\bigcap_{k=1}^{n-2}\varphi_k(x)}{S_h(y)}$$

Since $$\bigcup_{(y,y)\in\bigcap_{k=1}^{n-2}\varphi_k(x)}{S_h(y)}\subset\bigcap_{k=1}^{n-2}\bigcup_{(y,y)\in\varphi_k(x)}{S_h(y)}$$ is trivial, we focus on the opposite inclusion.

Assume $z\in \bigcap_{k=1}^{n-2}\bigcup_{(y,y)\in\varphi_k(x)}{S_h(y)}$. This implies that for each $k=1,\ldots, n-2$ there exists $y^k$ such that $(y^k,y^k)\in \varphi_k(x)$ and $$z\in \bigcap_{k=1}^{n-2} S_h(y^k).$$ Therefore $z$ is $(y^k,h)$ monotone for $k=1,\ldots, n-2$. Define $y\in L^N_n$ by $$y_1 := y_1^1,\quad  y_j := y_j^{j-1},\quad y_n := y_n^{n-2}, \quad \text{for $j=2,\ldots,n-1$.}$$ Observe that $y\in \rho(x)$, and therefore, by Lemma \[lem:rho\], $(y,y)\in \bigcap_{k=1}^{n-2}\varphi_k(x)$. From the fact that $z$ is $y^j$ monotone for all $j$, $z$ is also $(y,h)$ monotone, and $$z\in \bigcup_{(y,y)\in\bigcap_{k=1}^{n-2}\varphi_k(x)}{S_h(y)}.$$

\[prop:restrdom\] If $x\in \mathcal{L}_{2(n-1)}^{N-1}$, then $$\label{acall}
A_h(x) = \bigcup_{y\in \rho(x)} S_h (y).$$

By Lemma \[lem:rho\](i) the definition of $A_h(x)$ reduces to $$\begin{aligned}
A_h(x) & = \bigcap_{k=1}^{n-2} \left( \bigcup_{(y,y)\in \varphi_k(x)} S_h(y)  \right)  \\
& = \bigcup_{(y,y)\in \bigcap_{k=1}^{n-2}\varphi_k(x)} S_h(y) \\
& = \bigcup_{y\in \rho(x)} S_h (y),\end{aligned}$$ where the second equality follows from Lemma \[lemSintersect\] and the final inequality from Lemma \[lem:rho\](ii).

From $\rho(112244) = \left\{ 1235, 1236, 1245, 1246 \right\}$, it follows $$A_h(112244) = S_h(1235)\cup S_h(1236)\cup S_h(1245)\cup S_h(1246).$$

The following proposition relates the sets defined by $A_h$ to $C(h)$.

\[prop:C(h)Ah\] Let $h\in \mathcal{E}_+^n$. Then, $$C(h) = \bigcup_{x\in\mathcal{L}_{2(n-1)}^{N-1}}{A_h(x)}.$$

By Proposition \[prop:restrdom\], if $x\in\mathcal{L}_{2(n-1)}^{N-1}$, then $A_h(x) = \bigcup_{y\in \rho(x)} S_h (y)$. Observe that for any $y\in L_n^N$ we can find some $x\in{{\mathcal{L}}}_{2(n-1)}^{N-1}$, such that $y\in\rho(x)$ (for instance, $x$ satisfies $x_1=y_1$, and $x_{2(k-1)}=y_{k}-1$, and $x_{2(k-1)+1}=y_k$ for $1\leq k < n$). Hence, it holds that $$\bigcup_{x\in\mathcal{L}_{2(n-1)}^{N-1}}{\bigcup_{y\in \rho(x)} S_h (y)}=\bigcup_{y\in L^N_n}{S_h(y)} = C(h),$$ where the latter equality follows from .

\[lemwflat\] Let $w\in \mathbb{L}_{2(n-1)}^{N-1}/\mathcal{L}_{2(n-1)}^{N-1}$ and assume that for some $k$, $w_{2k+1}\leq w_{2k}$. If $(y,y')\in \varphi_k(w)$ and $z\in S_h(y)\cap S_h(y')$, then $$z_i = h_{k+1},\quad \text{for $i = w_{2k+1},\dots, w_{2k}+1$.}$$

By definition of $\varphi_k$ $$y_{k+1} = w_{2k+1}\quad\text{and}\quad y'_{k+1} = w_{2k}+1.$$ By definition of $S_h$, $z$ is $(y,h)$ and $(y',h)$ monotone. Therefore, $z_{y_{k+1}} = h_{k+1} = z_{y'_{k+1}}$. Again invoking monotonicity, $z_j = h_{k+1}$ for all $j=w_{2k+1},\ldots,w_{2k}+1$.

We now turn our attention to the semilattice structure of $A_h$.

\[thmlatmorph\] For all $h\in {{\mathcal{E}}}^n_+$, $A_h\colon \mathbb{L}_{2(n-1)}^{N-1} \to 2^{{\mathbb{R}}^{N}}$ is a semi-lattice morphism.

Before presenting the proof we give an example and two corollaries.

\[ex:ALatticeMorph\] Let $w,w',w''\in\mathbb{L}_8^5$ where $w = 11223344$, $w' = 22334455$, and $w'' = 11223345$. Then the semi-lattice morphism for $A_h$ states that $$A_h(11223344)\cap A_h(22334455) = A_h(11223344\wedge 22334455) = A_h(12233445)$$ and $$A_h(11223344)\cap A_h(11223345) = A_h(11223344\wedge 11223345) = A_h(11223345).$$

The latter equality of Example \[ex:ALatticeMorph\] motivates the following two corollaries.

\[corineq\] Let $w,w'\in\mathbb{L}_{2n}^{N-1}$. If $w\wedge w' = w$, then $$A_h(w) \subseteq A_h(w').$$

From Theorem \[thmlatmorph\] $$A_h(w) = A_h(w\wedge w') = A_h(w)\cap A_h(w') \subseteq A_h(w').$$

\[cor:C(h)Ah2\] Let $h\in{{\mathcal{E}}}_+^n$ where $n\leq N$. Then $$C(h) = \bigcup_{x\in {{\mathcal{P}}}^{N-1}_{2(n-1)}} A_h(x).$$

By Proposition \[prop:C(h)Ah\], $C(h) = \bigcup_{x\in {{\mathcal{L}}}^{N-1}_{2(n-1)}} A_h(x)$. Since ${{\mathcal{P}}}^{N-1}_{2(n-1)}\subset {{\mathcal{L}}}^{N-1}_{2(n-1)}$, $$\bigcup_{x\in {{\mathcal{P}}}^{N-1}_{2(n-1)}} A_h(x) \subset \bigcup_{x\in {{\mathcal{L}}}^{N-1}_{2(n-1)}} A_h(x).$$

To prove the opposite inequality, consider $x\in {{\mathcal{L}}}^{N-1}_{2(n-1)}$. Define $x'\in {{\mathcal{P}}}^{N-1}_{2(n-1)}$, by $x'_{2k-1} = x'_{2k} = x_{2k}$ for $k=1,\ldots, n-1$. By definition $x_{2k-1}\leq x'_{2k-1} = x_{2k}$. Let $x'' := x'\wedge x$ and observe that $x''_{2k}=x'_{2k}$ and $x''_{2k-1}=x_{2k-1}$. Thus $x'\wedge x =x$. Therefore, $A_h(x)\subset A_h(x')$. Since this is true for every $x\in {{\mathcal{L}}}^{N-1}_{2(n-1)}$ $$\bigcup_{x\in {{\mathcal{L}}}^{N-1}_{2(n-1)}} A_h(x) \subset \bigcup_{x\in {{\mathcal{P}}}^{N-1}_{2(n-1)}} A_h(x).$$

The remainder of this section focuses on the proof of Theorem \[thmlatmorph\]. The following result characterizes the kernel of $A_h$.

\[thmemptyint\] Let $w\in \mathbb{L}_{2(n-1)}^{N-1}$, $n>3$. Then, $$A_h(w) = \emptyset\quad\text{if and only if}\quad  w_{2k} + 1 \geq w_{2k+3}$$ for some $k=1,2,\dots, n-3$.

In case $n=3$, it holds that $$A_h(w)\neq\emptyset\text{ for all }w\in \mathbb{L}_4^{N-1}.$$

Let $n>3$. Let us pick $k\in\{1,2,\dots,n-3\}$. First, we show (by contradiction) that if $w_{2k}+1 \geq w_{2k+3}$, then $A_h(w) = \emptyset$.

Let us take $z\in S_h(y)\cap S_h(y')\cap S_h(v)\cap S_h(v')$ for some $(y,y')\in\varphi_k(w)$, and $(v,v')\in\varphi_{k+1}(w)$. It holds that

$$\begin{gathered}
\left\{\begin{array}{ll}
z_i = h_{k+1}&\text{ for some } w_{2k} < i \leq w_{2k+1} \text{(if $w_{2k}<w_{2k+1}$)},\\
z_i = h_{k+1}&\text{ for all }i = w_{2k+1},\dots,w_{2k}+1\ \text{(due to Lemma~\ref{lemwflat})}\end{array}\right.,\\
\text{and}\\
\left\{\begin{array}{ll}
z_j = h_{k+2}&\text{ for some } w_{2k+2} < j \leq w_{2k+3} \text{(if $w_{2k+2}<w_{2k+3}$)},\\
z_j = h_{k+2}&\text{ for all }j = w_{2k+3},\dots,w_{2k+2}+1\ \text{(due to Lemma~\ref{lemwflat}}))
\end{array}\right.\end{gathered}$$

The equations above show that we can find indices $(k,l)$, $k<l$, such that $z_k = h_{k+2}$, and $z_l = h_{k+1}$, which contradicts that $z$ is $(y,h)$, $(y',h)$, $(v,h)$, $(v',h)$-monotone. As $(y,y')\in\varphi_k(w)$, and $(v,v')\in\varphi_{k+1}(w)$ were arbitrary, hence $$\bigcup_{(y,y')\in\varphi_k(w)}{S_h(y)\cap S_h(y')}\cap\bigcup_{(v,v')\in\varphi_{k+1}(w)}{S_h(v)\cap S_h(v')} = \emptyset,$$ Therefore, in this case $$A_h(w) = \emptyset.$$

On the other hand we show that if $w_{2k}+1< w_{2k+3}$ for all $k\in\{1,2,\dots,n-3\}$, then we can construct a vector $z\in A_h(w)$. Let us pick multi-indices $y,y', v, v'$ depending on the cases considered below, and fix selected components of $z\in{\mathbb{R}}^N$ accordingly.

If $w_{2k} < w_{2k+1}$ take $(y,y') \in \varphi_k(w)$, from Lemma \[lem:rho\] $(y,y') = (y,y)$, and let $y$ be such that $$y_k = w_{2k}+1,\text{ fix } z_{w_{2k}+1} = h_{k+1},$$ otherwise, take any $(y,y')\in\varphi_k(w)$, and fix $$z_i = h_{k+1},\text{ for }i = w_{2k+1},\dots, w_{2k}+1.$$

If $w_{2k+2} < w_{2k+3}$ take $(v,v')\in\varphi_{k+1}(w)$, from Lemma \[lem:rho\] $(v,v') = (v,v)$, and let $v$ be such that $$v_k = w_{2k+3},\text{ fix }z_{w_{2k+3}}=h_{k+2},$$ otherwise, take any $(v,v')\in\varphi_{k+1}(w)$, and fix $$z_j = h_{k+2},\text{ for }j = w_{2k+3},\dots,w_{2k+2}+1.$$ Observe that in any of the cases considered above, due to the assumption $w_{2k}+1 < w_{2k+3}$, if $(k,l)$ are multi-indices such that $$z_k = h_{k+1},\text{ and }z_l = h_{k+2},\text{ then }k < l.$$ We may pick any values satisfying the monotonicity property for all of the remaining components of $z$.

Hence we showed that there exists $z$ which is $(y,h)$, $(y',h)$, $(v,h)$, $(v',h)$-monotone. Therefore, $$z\in S_h(y)\cap S_h(y')\cap S_h(v)\cap S_h(v').$$ Hence $$\bigcup_{(y,y')\in\varphi_k(w)}{S_h(y)\cap S_h(y')}\cap\bigcup_{(v,v')\in\varphi_{k+1}(w)}{S_h(v)\cap S_h(v')} \neq \emptyset,\text{ if }w_{2k} + 1 < w_{2k+3}.$$ Repeating this argument for all $k=1,2,\dots,n-3$, and assuming $w_{2k}+1 < w_{2k+3}$ for all $k$, we fix different components of $z$. Hence, if $w_{2k} + 1 \geq w_{2k+3}$ for all $k=1,2,\dots, n-3$ we find a $$z\in A_h(w).$$ Hence $$A_h(w) \neq \emptyset.$$

In case $n=3$, applying the argument above for $k=1,2$, we construct analogously a vector $z\in A_h(w)$.

[ *If $n=4$ and $N=6$, then $\varphi_k\colon \mathbb{L}_{6}^{5} \to 2^{L_{4}^6}\times 2^{L_{4}^6}$, for $k =1,2$. Furthermore, if $w=(1,2,2,3,3,4)$, then $$A_h(w) = \left[\bigcup_{(v,v')\in\varphi_1(w)}{S_h(v)\cap S_h(v')}\right]\cap\left[\bigcup_{(y,y')\in\varphi_2(w)}{S_h(y)\cap S_h(y')}\right] = \emptyset,$$ because $w_2 + 1 = 3 = w_5 = 3$.* ]{}

The following result provides the characteristics of nonempty sets in $A_h$ image.

\[threecontr\] Let $h\in{{\mathcal{E}}}^n_+$, $w\in \mathbb{L}_{2(n-1)}^{N-1}$. If $A_h(w)$ is nonempty, then $A_h(w)$ is star-shaped and hence contractible.

Let $h\in{{\mathcal{E}}}^n_+$, $w\in \mathbb{L}_{2(n-1)}^{N-1}$. Also assume that in case $n>3$ it holds that $w_{2k} + 1 < w_{2k+3}$ for all $k=1,2,\dots, n-3$, which from Theorem \[thmemptyint\] is equivalent to $A_h(w)$ being nonempty. We want to show that $A_h(w)$ is star-shaped. We proceed in two steps. First, we show that $\bigcup_{(y,y')\in \varphi_k(w)} S_h(y)\cap S_h(y')$ is star-shaped for each $k$. Observe that $S_h(y)\cap S_h(y')$ is a convex set for all $(y,y')$, as it is an intersection of two convex sets. A vector $\bar{z}\in {\mathbb{R}}^N$, such that $$\bar{z}\in S_h(y)\text{ for some }y\in L_n^N\text{ and }\bar{z}_{j} = h_{k+1}\text{ for }j=\left\{\begin{matrix}w_{2k}+1,\dots,w_{2k+1},&\text{ if }w_{2k}<w_{2k+1}\\
w_{2k+1},\dots,w_{2k}+1,&\text{ if }w_{2k}\geq w_{2k+1}\end{matrix}\right.$$ is $(y,h)$ and $(y',h)$-monotone for all $(y,y')\in\varphi_k(w)$, and hence $\bar{z}\in S_h(y)\cap S_h(y')$ for all $(y,y')\in \varphi_k(w)$, and ${\bigcup_{(y,y')\in \varphi_k(w)} S_h(y)\cap S_h(y')}$ is an union of convex sets having a common vector, and hence is star-shaped.

Second, we show that the whole family of star-shaped sets $\left\{\bigcup_{(y,y')\in \varphi_k(w)} S_h(y)\cap S_h(y')\right\}_{k=1}^{n-2}$ has a common vector. Let $\bar{z}\in{\mathbb{R}}^N$ be such that $$\bar{z}_{j} = h_{k+1}\text{ for }j=\left\{\begin{matrix}w_{2k}+1,\dots,w_{2k+1},&\text{ if }w_{2k}<w_{2k+1}\\
w_{2k+1},\dots,w_{2k}+1,&\text{ if }w_{2k}\geq w_{2k+1}\end{matrix}\right.\text{, and for all }k = 1,\dots, n-2,$$ for all the remaining coordinates $\bar{z}$ takes values, such that it is monotone, observe that conditions $w\in \mathbb{L}_{2(n-1)}^{N-1}$, and if $n>3$ also $w_{2k} + 1 < w_{2k+3}$ for $k=1,2,\dots,n-3$ guarantee existence of such vector $\bar{z}$.

Therefore, $A_h(w)$ is an intersection of star-shaped sets having a common vector, hence $A_h(w)$ is star-shaped itself.

\[lemsuminc\] Let $w,x \in \mathbb{L}_{2(n-1)}^{N-1}$. Let $k\in\{1,\dots,n-2\}$. Assume $$w_{2k-1} \leq x_{2k-1},\text{ and }w_{2k} \geq x_{2k},\text{ and }w_{2k+1} \leq x_{2k+1},\text{ and }w_{2k+2} \geq x_{2k+2}.$$ Then it holds that $$\bigcup_{(y,y')\in\varphi_k(w)}{S_h(y)\cap S_h(y')} \subset \bigcup_{(v,v')\in\varphi_k(x)}{S_h(v) \cap S_h(v')}.$$

Let $(y,y')\in\varphi_k(w)$. In case $w_{2k} < w_{2k+1}$ it holds that $(y,y')=(y,y)$ from Lemma \[lem:rho\], and $$y_k \leq w_{2k-1},\quad w_{2k}< y_{k+1} \leq w_{2k+1},\quad w_{2k+2} < y_{k+2}.$$ Due to the assumption it also holds $$y_k \leq x_{2k-1},\quad x_{2k}< y_{k+1} \leq x_{2k+1},\quad x_{2k+2} < y_{k+2}.$$ Hence $(y,y')\in\varphi_k(x)$.

In case $w_{2k} \geq w_{2k+1}$ it holds that $$y_k \leq w_{2k-1},\quad y_{k+1} = w_{2k+1},\quad y'_{k+1} = w_{2k}+1,\quad w_{2k+2} < y_{k+2},$$ Let us take $z\in S_h(y)\cap S_h(y')$. From Lemma \[lemwflat\], $z$ satisfies $$z_i = h_{k+1}\text{ for }i = w_{2k+1},\dots, w_{2k}+1.$$ And, in particular from the assumption it follows that $$z_i = h_{k+1}\text{ for }
    \left\{ \begin{array}{ll}
              i =  x_{2k+1}, \dots, x_{2k}+1,&\text{ if }x_{2k}\geq x_{2k+1},\\
              i \in \{ x_{2k}+1, \dots, x_{2k+1} \}&\text{ otherwise}.
            \end{array}\right.$$ Also $z_{y_k} = h_k$, $z_{y_{k+2}} = h_{k+2}$, and due to the assumption $y_k \leq x_{2k-1}$, and $y_{k+2} > x_{2k+2}$. Hence $$z \in{S_h(v) \cap S_h(v')}\text{ for some }(v,v')\in\varphi_k(x).$$ Therefore, $$z \in\bigcup_{(v,v')\in\varphi_k(x)}{S_h(v) \cap S_h(v')}.$$

We need to show that $$\begin{aligned}
A_h(w\wedge x) & = A_h(w)\cap A_h(x) \\
\bigcap_{k=1}^{n-2} \left( \bigcup_{(y,y')\in \varphi_k(w\wedge x)} S_h(y)\cap S_h(y')  \right) & =  
\bigcap_{k=1}^{n-2} \left( \bigcup_{(v, v')\in \varphi_k(w)} S_h(v)\cap S_h(v')  \right) \cap 
\bigcap_{k=1}^{n-2} \left( \bigcup_{(u,u')\in \varphi_k(x)} S_h(u)\cap S_h(u')  \right)\end{aligned}$$ Observe that it is sufficient to prove that for each $k=1,\ldots, n-2$ $$\label{eqmorphism}
 \bigcup_{(y,y')\in \varphi_k(w\wedge x)} S_h(y)\cap S_h(y')   =  
 \left( \bigcup_{(v,v')\in \varphi_k(w)} S_h(v)\cap S_h(v')  \right) \cap 
 \left( \bigcup_{(u,u')\in \varphi_k(x)} S_h(u)\cap S_h(u')  \right)$$

For fixed $k$ we break the proof into three cases: $w_{2k} < w_{2k+1}$ and $x_{2k} < x_{2k+1}$, $w_{2k}  < w_{2k+1}$ and $x_{2k} \geq x_{2k+1}$, and $w_{2k}  \geq w_{2k+1}$ and $x_{2k} \geq x_{2k+1}$. In each case, to show the left from the right inclusion in , we pick $z\in\text{r.h.s. of \eqref{eqmorphism}}$ and we construct multi-indices $(y,y')\in\varphi_k(w\wedge x)$, such that $z\in S_h(y)\cap S_h(y')$.

*Case 1: $w_{2k} < w_{2k+1}$ and $x_{2k} < x_{2k+1}$.* By the definition of $\varphi_k$ and Lemma \[lem:rho\], reduces to $$\label{eq:morphism1}
 \bigcup_{(y,y')\in \varphi_k(w\wedge x)} S_h(y) \cap S_h(y')  =  
 \left( \bigcup_{(v,v)\in \varphi_k(w)} S_h(v)  \right) \cap 
 \left( \bigcup_{(u,u)\in \varphi_k(x)} S_h(u)  \right).$$ Observe that the inclusion $$\bigcup_{(y,y')\in \varphi_k(w\wedge x)} S_h(y) \cap S_h(y')  \subset  
 \left( \bigcup_{(v,v)\in \varphi_k(w)} S_h(v)  \right) \cap 
 \left( \bigcup_{(u,u)\in \varphi_k(x)} S_h(u)  \right)$$ follows from Lemma \[lemsuminc\]. To show the other inclusion, we take $(v,v)\in\varphi_k(w)$, and $(u,u)\in\varphi_k(x)$, then $$\label{uw}
v_k\leq w_{2k-1}\quad\text{and}\quad w_{2k}<v_{k+1}\leq w_{2k+1}\quad\text{and}\quad w_{2k+2}<v_{k+2}$$ and $$\label{ux}
  u_k \leq x_{2k-1} \quad\text{and}\quad x_{2k}<u_{k+1}\leq x_{2k+1} \quad\text{and}\quad x_{2k+2}<u_{k+2}$$ respectively.

Observe that from , and it follows that

\[minmax\] $$\begin{aligned}
  \min(v_k,u_k) &\leq \min(w_{2k-1},x_{2k-1}) = (w\wedge x)_{2k-1},\label{ineq1}\\
  \max(v_{k+1},u_{k+1}) & > \max(w_{2k},x_{2k}) = (w\wedge x)_{2k},\label{ineq2}\\
  \min(v_{k+1},u_{k+1}) & \leq \min(w_{2k+1},x_{2k+1}) = (w\wedge x)_{2k+1},\label{ineq3}\\
  \max(v_{k+2},u_{k+2}) & > \max(w_{2k+2},x_{2k+2}) = (w\wedge x)_{2k+2}.\label{ineq4}\end{aligned}$$

Let $z \in S_h(v)\cap S_h(u)$. It follows from the monotonicity property (Def. \[defmonotone\]) that $$\begin{aligned}
z_{\min(v_k,u_k)}&=h_k,\\
z_i &= h_{k+1}\text{ for }i=\min(v_{k+1},u_{k+1}),\dots,\max(v_{k+1},u_{k+1}),\\
z_{\max(v_{k+2},u_{k+2})}&=h_{k+2}.\end{aligned}$$ Because $w\wedge x\in \mathbb{L}_{2(n-1)}^{N-1}$ we consider two subcases, either $(w\wedge x)_{2k} \geq (w\wedge x)_{2k+1}$ or $(w\wedge x)_{2k} < (w\wedge x)_{2k+1}$.

*Case A* $(w\wedge x)_{2k} \geq (w\wedge x)_{2k+1}$. Let $\bar{u},\bar{v}\in L_n^N$ be such that $$\begin{aligned}
  \bar{u}_{k} = \bar{v}_k &= {\min(v_k,u_k)},\\
  \bar{u}_{k+1} &= (x\wedge w)_{2k+1},\\
  \bar{v}_{k+1} &= (x\wedge w)_{2k}+1,\\
  \bar{u}_{k+2} = \bar{v}_{k+2} &= {\max(v_{k+2},u_{k+2})}.\end{aligned}$$

It holds that $(\bar{u},\bar{v})\in\varphi_k(w\wedge x)$.

Due to the inequalities , it holds that $$z_i = h_{k+1}\text{ also for }i = (w\wedge x)_{2k+1},\dots,(w\wedge x)_{2k}+1.$$

Hence, $z$ is $(\bar{u},h)$, $(\bar{v},h)$-monotone and therefore $$z\in \bigcup_{(\bar{u},\bar{v})\in \varphi_k(w\wedge x)} S_h(\bar{u}) \cap S_h(\bar{v}).$$

*Case B* $(w\wedge x)_{2k} < (w\wedge x)_{2k+1}$. Let $\bar{u}\in L_n^N$ be any multi-index satisfying $$\begin{aligned}
  \bar{u}_{k}&= {\min(v_k,u_k)},\\
  \bar{u}_{k+1} &\in \left\{ (w\wedge x)_{2k}+1,\dots,(w\wedge x)_{2k+1}\right\},\\
  \bar{u}_{k+2} &= {\max(v_{k+2},u_{k+2})}.\end{aligned}$$

It holds that $(\bar{u},\bar{u})\in\varphi_k(w\wedge x)$.

Due to the inequalities , , it also holds that

$z_i = h_{k+1}$ for $i\in \left\{\max\left[\min(v_{k+1},u_{k+1}),(w\wedge x)_{2k}+1\right],\dots,\min\left[\max(v_{k+1},u_{k+1}),(w\wedge x)_{2k+1}\right]\right\}$. Hence, $z$ is $(\bar{u},h)$-monotone, and therefore $$z\in \bigcup_{(\bar{u},\bar{u})\in \varphi_k(w\wedge x)} S_h(\bar{u}).$$

*Case 2: $w_{2k}  < w_{2k+1}$ and $x_{2k} \geq x_{2k+1}$ (and the symmetric case).* By the definition of $\varphi_k$ reduces to $$\bigcup_{(y,y')\in \varphi_k(w\wedge x)} S_h(y)\cap S_h(y')   =  
 \left( \bigcup_{(v,v)\in \varphi_k(w)} S_h(v)  \right) \cap 
 \left( \bigcup_{(u,u')\in \varphi_k(x)} S_h(u)\cap S_h(u')  \right)$$

The inclusion $$\bigcup_{(y,y')\in \varphi_k(w\wedge x)} S_h(y)\cap S_h(y')   \subset
  \left( \bigcup_{(v,v)\in \varphi_k(w)} S_h(v)  \right) \cap \left(\bigcup_{(u,u')\in \varphi_k(x)} S_h(u)\cap S_h(u') \right),$$ follows from Lemma \[lemsuminc\].

We now proceed to showing the inclusion $$\label{inc2}
 \bigcup_{(y,y')\in \varphi_k(w\wedge x)} S_h(y)\cap S_h(y')   \supset 
 \left( \bigcup_{(v,v)\in \varphi_k(w)} S_h(v)  \right) \cap 
 \left( \bigcup_{(u,u')\in \varphi_k(x)} S_h(u)\cap S_h(u')  \right).$$ Let us pick $$z\in S_h(v) \cap S_h(u)\cap S_h(u')$$ for some $(v,v)\in \varphi_k(w)$, and $(u,u')\in \varphi_k(x)$. Because $z$ is $(v,h)$, $(u,h)$, $(u',h)$-monotone. From the assumption $x_{2k} \geq x_{2k+1}$, it holds that $u_{k+1}=x_{2k+1}$, and $u'_{k+1}=x_{2k}+1$. And from the monotonicity property (Def. \[defmonotone\]), it holds that

\[mono1\] $$\begin{aligned}
  z_{\min(v_k,u_k, u'_k)} &= h_k,\\
  z_{i} &= h_{k+1}\text{ for }i = \min(v_{k+1},x_{2k+1}), \dots, \max(v_{k+1},x_{2k}+1),\\
  z_{\max(v_{k+2},u_{k+2}, u'_{k+2})} &= h_{k+2}.\end{aligned}$$

Let $\bar{u},\bar{v}\in L_n^N$ be such that $$\begin{aligned}
  \bar{u}_{k} = \bar{v}_k &= {\min(v_k,u_k, u'_k)},\\
  \bar{u}_{k+1} &= (x\wedge w)_{2k+1},\\
  \bar{v}_{k+1} &= (x\wedge w)_{2k}+1,\\
  \bar{u}_{k+2} = \bar{v}_{k+2} &= {\max(v_{k+2},u_{k+2}, u'_{k+2})}.\end{aligned}$$ It holds that $$(\bar{u},\bar{v})\in\varphi_k(w\wedge x).$$

From the inequality $w_{2k} < v_{k+1} \leq w_{2k+1}$ it holds that $$\begin{aligned}
  \min(v_{k+1},x_{2k+1}) \leq (x\wedge w)_{2k+1},\\
  \max(v_{k+1},x_{2k}+1) \geq (x\wedge w)_{2k}+1.\end{aligned}$$ Therefore from it holds that $$z_i = h_{k+1}\text{ for }i = (x\wedge w)_{2k+1},\dots,(x\wedge w)_{2k}+1,$$ Hence $z$ is $(\bar{u},h)$, $(\bar{v},h)$-monotone. And, therefore $$z \in \bigcup_{(\bar{u},\bar{v})\in\varphi_k(x\wedge w)}{S_h(\bar{u})\cap S_h(\bar{v})},$$ i.e. we showed the inclusion .

*Case 3: $w_{2k}  \geq w_{2k+1}$ and $x_{2k} \geq x_{2k+1}$.* By the definition of $\varphi_k$ and reduces to $$\bigcup_{(y,y')\in \varphi_k(w\wedge x)} S_h(y)\cap S_h(y')   =  
 \left( \bigcup_{(v,v')\in \varphi_k(w)} S_h(v) \cap S_h(v')  \right) \cap 
 \left( \bigcup_{(u,u')\in \varphi_k(x)} S_h(u) \cap S_h(u')  \right)$$ Observe that the inclusion $$\bigcup_{(y,y')\in \varphi_k(w\wedge x)} S_h(y)\cap S_h(y')   \subset  
 \left( \bigcup_{(v,v')\in \varphi_k(w)} S_h(v) \cap S_h(v')  \right) \cap 
 \left( \bigcup_{(u,u')\in \varphi_k(x)} S_h(u) \cap S_h(u')  \right)$$ follows from Lemma \[lemsuminc\].

Now, we show the inclusion $$\label{inc3}
   \bigcup_{(y,y')\in \varphi_k(w\wedge x)} S_h(y)\cap S_h(y')  \supset  
   \left( \bigcup_{(v,v')\in \varphi_k(w)} S_h(v) \cap S_h(v')  \right) \cap 
 \left( \bigcup_{(u,u')\in \varphi_k(x)} S_h(u) \cap S_h(u')  \right)$$

Let us pick $$z\in S_h(v) \cap S_h(v')\cap S_h(u)\cap  S_h(u'),$$ for some $(v, v')\in \varphi_k(w)$, and $(u, u')\in \varphi_k(x)$. Because $z$ is $(v,h)$, $(v',h)$, $(u,h)$, $(u',h)$-monotone. From the assumptions $x_{2k} \geq x_{2k+1}$, $w_{2k} \geq w_{2k+1}$ and the monotonicity property (Def. \[defmonotone\]) it holds that $$\begin{aligned}
  z_{\min(v_k,v'_k, u_k, u'_k)} &= h_k,\\
  z_{i} &= h_{k+1}\text{ for }i = \min(x_{2k+1}, w_{2k+1}), \dots, \max(x_{2k}+1,w_{2k}+1),\\
  z_{\max(v_{k+2},v'_{k+2}, u_{k+2}, u'_{k+2})} &= h_{k+2}.\end{aligned}$$ Let $\bar{u},\bar{v}\in L_n^N$ be such that $$\begin{aligned}
  \bar{u}_{k} = \bar{v}_k &= z_{{\min(v_k,v'_k, u_k, u'_k)}},\\
  \bar{u}_{k+1} &= (x\wedge w)_{2k+1},\\
  \bar{v}_{k+1} &= (x\wedge w)_{2k}+1,\\
  \bar{u}_{k+2} = \bar{v}_{k+2} &= z_{{\max(v_{k+2},v'_{k+2}, u_{k+2}, u'_{k+2})}}.\end{aligned}$$

It holds that $$(\bar{u},\bar{v})\in\varphi_k(w\wedge x).$$ And from the monotonicity property $$z_i = h_{k+1},\text{ for }i = (x\wedge w)_{2k+1},\dots,(x\wedge w)_{2k}+1,$$ Hence $z$ is $(\bar{u},h)$, $(\bar{v},h)$-monotone, and it holds that $$z \in \bigcup_{(\bar{u},\bar{v})\in\varphi_k(x\wedge w)}{S_h(\bar{u})\cap S_h(\bar{v})}.$$ And we showed the inclusion .

Contractibility for $n=3$ {#secfirststep}
=========================

As indicated in the introduction, the aim of this section is to establish the base case for the induction argument that proves Theorem \[thm:main\]. We state this base case in the form of the following theorem.

\[thm:baseCase\] If $z\in{\mathbb{R}}^N$ satisfies assumption [**A**]{} and $h=\operatorname{cv}(z)\in{{\mathcal{E}}}^3_+$, then $C(h)$ is contractible.

If $z\in{\mathcal{B}}$ satisfies assumption [**A**]{}, then $C(h)\subset{\mathcal{B}}$ is contractible and compact.

Because the proof is rather formal and provides little geometric insight, we first consider the simplest nontrivial example.

Let $N=4$ and $n=3$. Thus, we consider $h\in {{\mathcal{E}}}_+^3$. By Corollary \[cor:C(h)Ah2\] $$C(h) = \bigcup_{x\in\mathcal{P}_4^3}{A_h(x)},$$ where (see Example \[ex:calP34\]) $$\mathcal{P}_4^3 = \left\{ (1122), (1133), (2233) \right\}.$$

The first step is to check that the conditions of the Nerve Theorem (Thm. \[thmnerve\]) are satisfied for the following nerve simplicial complex with vertex set ${{\mathcal{P}}}_4^3$, and ${{\mathcal{A}}}= \{A_h(x)\}_{x\in{{\mathcal{P}}}_4^3}$, i.e. $${{\mathcal{N}}}({{\mathcal{A}}}) = \left\{ {{\mathcal{J}}}\subseteq{{\mathcal{P}}}_4^3\colon\,\bigcap_{x\in{{\mathcal{J}}}}{A_h(x)}\neq\emptyset \right\}.$$

By Theorem \[threecontr\] $A_h(x)$ is contractible for all $x\in \mathcal{P}_4^3$. To determine contractibility of $$\bigcap_{x\in{{\mathcal{J}}}\subset\mathcal{P}_4^3 }A_h(x)$$ we make use of the fact that $A_h$ is a semilattice morphism (Theorem \[thmlatmorph\]) and compute $$A_h\left(\bigwedge_{x\in{{\mathcal{J}}}\subset\mathcal{P}_4^3}x \right).$$ The following table indicates the action of $\wedge$ on ${{\mathcal{P}}}_4^3$.

    $\wedge$  1122   1133   2233
  ---------- ------ ------ ------
        1122  1122   1123   1223
        1133         1133   1233
        2233                2233

Observe that all products are elements of $\mathbb{L}_4^3$ (see Example \[ex:bbL34\]), and therefore by Theorem \[threecontr\] their images under $A_h$ are contractible. Figure \[figcomplex1\] indicates the simplicial complex associated with the Nerve of the images of $A_h$.

![Simplicial complex nerve representation for the presented example with $N=4$ and $n=3$.[]{data-label="figcomplex1"}](simplex3.pdf){width="30.00000%"}

Using the so far established results we are prepared to show Theorem \[thm:baseCase\]. Observe that in case $n=3$ from Theorem \[thmemptyint\] it follows that $A_h(w)\neq\emptyset$ for any $w\in\mathbb{L}^{N-1}_4$. And then, from Theorem \[threecontr\] $A_h(w)$ is star-shaped for all $w\in\mathbb{L}^{N-1}_4$. We may summarize those facts as

\[corJ\] For any nonempty $\mathcal{J} \subset \mathcal{L}_4^{N-1}$ it holds that $$\bigcap_{x\in\mathcal{J}}{A_h(x)}$$ is contractible.

Let us define the following nerve simplicial complex with vertex set ${{\mathcal{L}}}_4^{N-1}$ for the family of sets ${{\mathcal{A}}}= \left\{ A_h(x)\right\}_{x\in{{\mathcal{L}}}_4^{N-1}}$ $${{\mathcal{N}}}({{\mathcal{A}}}) = \left\{{{\mathcal{J}}}\subseteq {{\mathcal{L}}}_4^{N-1}\colon\,\bigcap_{x\in{{\mathcal{J}}}}{A_h(x)}\neq\emptyset \right\}.$$ By Corollary \[corJ\] ${{\mathcal{N}}}({{\mathcal{A}}})$ is the full $N-1$-simplex, and consequently the set $$\bigcup_{x\in{{\mathcal{L}}}_4^{N-1}}{A_h(x)}$$ from the Nerve Theorem (Thm. \[thmnerve\]) has the homotopy type of a point, i.e. is contractible. By Proposition \[prop:C(h)Ah\] $$C(h) = \bigcup_{x\in\mathcal{L}_4^{N-1}}{A_h(x)},$$ and we are done. As noted earlier all results from Section \[secsubsets\] are also true in the compact case (Remark \[remcompact\]).

Motivating the induction step {#secmotiv}
=============================

As indicated in the introduction our proof of the induction step is fairly cumbersome. To motivate our approach and to give an outline of the argument we consider the simplest case beyond that of the previous section.

\[exn5\] Let $N=6$ and $n=5$. Then, $h\in {{\mathcal{E}}}_+^5$. By Corollary \[cor:C(h)Ah2\] $$C(h) = \bigcup_{x\in\mathcal{P}_8^5}{A_h(x)},$$ where $$\mathcal{P}_8^5 = \left\{ (11223344), (11223355), (11224455), (11334455), (22334455) \right\}.$$ The first step is to check that the conditions of the Nerve Theorem are satisfied for the following nerve simplicial complex with vertex set ${{\mathcal{P}}}_8^5$, and ${{\mathcal{A}}}= \{A_h(x)\}_{x\in{{\mathcal{P}}}_8^5}$, i.e. $${{\mathcal{N}}}({{\mathcal{A}}}) = \left\{ {{\mathcal{J}}}\subseteq{{\mathcal{P}}}_8^5\colon\,\bigcap_{x\in{{\mathcal{J}}}}{A_h(x)}\neq\emptyset \right\}.$$ By Theorem \[threecontr\] $A_h(x)$ is contractible for all $x\in \mathcal{P}_8^5$. To determine contractibility of $$\bigcap_{x\in{{\mathcal{J}}}\subset\mathcal{P}_8^5 }A_h(x)$$ we make use of the fact that $A_h$ is a semilattice morphism (Theorem \[thmlatmorph\]) and compute $$A_h\left(\bigwedge_{x\in{{\mathcal{J}}}\subset\mathcal{P}_8^5}x \right).$$ The following table indicates the action of $\wedge$ on ${{\mathcal{P}}}_8^5$.

    $\wedge$  11223344   11223355   11224455    11334455     22334455
  ---------- ---------- ---------- ---------- ------------ ------------
    11223344             11223345   11223445   *11233445*   *12233445*
    11223355                        11223455    11233455    *12233455*
    11224455                                    11234455     12234455
    11334455                                                 12334455

Observe that all products are elements of $\mathbb{L}_8^5$, by Theorem \[thmlatmorph\] $A_h$’s indexed with any multiindex written using regular font is contractible, whereas by Theorem \[thmemptyint\] $A_h$’s indexed with any multiindex written using italics is empty, due to condition $w_{2k}+1\geq w_{2k+3}$ being satisfied for some $k$ (we have $A_h(11233445) =  A_h(12233445) =  A_h(12233455) = \emptyset$).

Thus, we only need to consider the following triples of $\wedge$ $$\begin{aligned}
11223344 \wedge 11223355 \wedge 11224455 = 11223345 \wedge 11224455 & = 11223445 \\
11223355 \wedge 11224455 \wedge 11334455 = 11223455 \wedge 11334455 & = 11233455 \\
11224455 \wedge 11334455 \wedge 22334455 = 11234455 \wedge 22334455 & = 12334455.\end{aligned}$$ Again, all products are elements of $\mathbb{L}_8^5$, and therefore, by Theorem \[thmlatmorph\] are contractible. For all higher order products $A_h$ is trivial. Therefore, we can apply Theorem \[thmnerve\] and use the nerve complex ${{\mathcal{N}}}({{\mathcal{A}}})$ to compute the homotopy or homology type of $C(h)$. ${{\mathcal{N}}}({{\mathcal{A}}})$ is presented on Figure \[figcomplex3\] and is clearly contractible.

![Simplicial ${{\mathcal{N}}}({{\mathcal{A}}})$ complex nerve representation in Example \[exn5\]. The presented vertices are all multiindices from ${{\mathcal{P}}}_8^5$. The edges and faces represent contractible intersections of corresponding $A_h$’s.[]{data-label="figcomplex3"}](simplex5.pdf){width="50.00000%"}

Unfortunately, the argument used in this example does appear to suggest a principle from which we can determine contractibility in general. With this in mind, we develop a coarser covering, such that the complex used to represent $C(h)$ is a full simplex.

\[defAt\] Let map $\theta$ be given by . Define the following ${\Lambda}_h\colon  \mathcal{L}_2^{n-3,N-3} \to 2^{\mathbb{R}^{N}}$ by $${\Lambda}_h((p_1, p_2)) := \bigcup_{x\in \theta((p_1, p_2))} A_h(x).$$

\[propChLambda\] Let $h\in{{\mathcal{E}}}^n_+$, then $$C(h) = \bigcup_{p \in \mathcal{L}_2^{n-3,N-3}}{\Lambda_h((p_1,p_2))}.$$

By Definition $${\Lambda}_h((p_1, p_2)) = \bigcup_{x\in \theta((p_1, p_2))} A_h(x).$$

Hence from Proposition \[propthetap\] $$\bigcup_{p \in \mathcal{L}_2^{n-3,N-3}}{\Lambda_h((p_1,p_2))} = \bigcup_{x\in\mathcal{P}_{2(n-1)}^{N-1}}{A_h\left(x\right)} = C(h),$$ where the last equality follows from Proposition \[prop:C(h)Ah\].

\[thmintersect\] Let ${\Lambda}_h\colon\mathcal{L}_2^{n-3,N-3} \to 2^{\mathbb{R}^{N}}$ be the map defined in Def. \[defAt\].

Then ${\Lambda}_h\colon\mathcal{L}_2^{n-3,N-3} \to 2^{\mathbb{R}^{N}}$ is a semi-lattice morphism.

Let $p=(p_1,p_2), q=(q_1,q_2) \in \mathcal{L}_2^{n-3,N-3}$. We will show that it holds that $${\Lambda}_h((p_1, p_2))\,\cap\,{\Lambda}_h((q_1, q_2)) = \bigcup_{y\in\theta((p_1, p_2))\,\cap\,\theta((q_1, q_2))}{A_h(y)} = \bigcup_{y\in\theta((p_1, p_2)\wedge (q_1, q_2))}{A_h(y)} = \Lambda_h((p_1, p_2)\wedge (q_1, q_2)).$$

It follows from Corollary \[corineq\] and Lemma \[lemtheta\] that $${\Lambda}_h((p_1, p_2))\cap{\Lambda}_h((q_1, q_2)) = \bigcup_{ \substack{w\in\theta((p_1, p_2)) \\ z\in\theta((q_1, q_2))} }{A_h(w\wedge z)} \subset \bigcup_{y\in\theta((p_1, p_2))\,\cap\,\theta((q_1, q_2))}{A_h(y)}.$$ The other inclusion $$\bigcup_{y\in\theta((p_1, p_2))\,\cap\,\theta((q_1, q_2))}{A_h(y)} \subset {\Lambda}_h((p_1, p_2))\cap{\Lambda}_h((q_1, q_2)).$$ holds trivially.

From Proposition \[propKwedgeM\] it follows that $$\bigcup_{y\in\theta((p_1, p_2))\,\cap\,\theta((q_1, q_2))}{A_h(y)} = \bigcup_{y\in\theta((p_1, p_2)\wedge (q_1, q_2))}{A_h(y)} = \Lambda_h((p_1, p_2)\wedge (q_1, q_2)).$$

Let us recall that in the sequel we developed coarser and coarser covering of $C(h)$ in order to show that $C(h)$ is contractible. In we defined convex sets $S_h(y)$, whose union covers $C(h)$. However, it is not clear at all how to show directly contractibility of the nerve complex of the covering $$\bigcup_{y\in\mathcal{L}_n^N}{S_h(y)}.$$

Instead, as demonstrated in Section \[secfirststep\], we use a covering based on $A_h$ semi-lattice morphism, defined in Proposition \[prop:restrdom\].

We emphasize it is still not clear to show that the covering of $C(h)$ provided by $\{ A_h(x) \}_{x\in{{\mathcal{P}}}_{2(n-1)}^{N-1}}$ is contractible by directly investigating the nerve complex ${{\mathcal{N}}}\left(\{ A_h(x) \}\right)$. For the particular case presented as Example \[exn5\] the obtained complex ${{\mathcal{N}}}\left(\{ A_h(x) \}_{x\in{{\mathcal{P}}}_8^5}\right)$ is contractible, which is clearly readable from its picture on Figure \[figcomplex1\]. However, its not clear how to construct a scheme of proving contractibility in general. One natural way of deriving a general scheme would be to invoke the technique of mathematical induction. In fact, we develop an inductive scheme for proving the general case using a more coarse covering based on family $\left\{\Lambda_h((p_1,p_2))\right\}_{p\in\mathcal{L}_2^{{n-3},{N-3}}}$ defined in Definition \[defAt\]. Recall that the union of $A_h(x)$’s and the union of $\Lambda_h((p_1,p_2))$’s both cover $C(h)$,i.e. $$C(h) = \bigcup_{x\in{{\mathcal{P}}}_{2(n-1)}^{N-1}}{A_h(x)} = \bigcup_{p \in \mathcal{L}_2^{{n-3},{N-3}}}{\Lambda_h((p_1,p_2))}.$$ Still, advantage of using $\Lambda_h((p_1,p_2))$’s is that we can show that nerve complex ${{\mathcal{N}}}\left( \left\{\Lambda_h((p_1,p_2))\right\}_{p\in\mathcal{L}_2^{{n-3},{N-3}}}\right)$ is contractible by invoking an inductive scheme.

We now return to Example \[exn5\] and show that it is contractible using the book keeping that $\Lambda_h$ provides. By Proposition \[propChLambda\] $$C(h) = \bigcup_{p \in \mathcal{L}_2^{2,3}}{\Lambda_h((p_1,p_2))},$$ where $${{\mathcal{L}}}_2^{2,3} = \left\{ (2,2), (2,3), (3,3)\right\}.$$

The first step is to check that the conditions of the Nerve Theorem are satisfied for the following nerve simplicial complex with vertex set ${{\mathcal{L}}}_2^{2,3}$, and ${{\mathcal{A}}}= \{\Lambda_h((p_1,p_2))\}_{p\in{{\mathcal{L}}}_2^{2,3}}$, i.e. $${{\mathcal{N}}}({{\mathcal{A}}}) = \left\{ {{\mathcal{J}}}\subseteq{{\mathcal{L}}}_2^{2,3}\colon\,\bigcap_{p\in{{\mathcal{J}}}}{\Lambda_h((p_1,p_2))}\neq\emptyset \right\}.$$

To determine contractibility of $$\bigcap_{p\in{{\mathcal{J}}}\subset\mathcal{L}_2^{2,3} }\Lambda_h((p_1,p_2))$$ we make use of Theorem \[thmintersect\] to compute $$\Lambda_h\left(\bigwedge_{p\in{{\mathcal{J}}}\subset\mathcal{L}_2^{2,3}}p \right).$$ Clearly $$22\wedge 23 = 22\wedge 33 = 22\wedge 23\wedge 33 = 23,$$ and $$\theta(22) = \left\{11223344, 1223355, 11224455 \right\},\ \theta(23) = \left\{ 11224455 \right\},\ \theta(33) = \left\{ 11224455, 11334455, 22334455 \right\}$$ In Section \[thmind1\] we establish an inductive argument relating the contractibility of $\theta(22)$, $\theta(23)$, $\theta(33)$ with the contractibility of smaller complexes for $n=3$, i.e. $\bigcup_{x\in\mathcal{P}_{4}^{p_1}}A_{h',p_1,3}\left({x}\right)$, for $p_1=2,3$, that already were established to be contractible in Section \[secfirststep\]. It follows that all of the intersections $\bigcap_{p\in{{\mathcal{J}}}\subset\mathcal{L}_2^{2,3} }\Lambda_h((p_1,p_2))$ are contractible, and the nerve complex of the covering $C(h) = \bigcup_{p \in \mathcal{L}_2^{2,3}}{\Lambda_h((p_1,p_2))}$ is in fact a very basic one-dimensional simplex, presented on Figure \[figcomplex2\].

![Simplicial complex nerve representation in Example \[exn5\]. The presented vertices are all multiindices from $\mathcal{L}_2^{2,3}$. The edge is the intersection of the corresponding $\Lambda_h$’s.[]{data-label="figcomplex2"}](complexp.pdf){width="25.00000%"}

Contractibility of the preimage set $C(h)$ {#seccontr}
==========================================

The goal of this section is to prove the following theorem providing an inductive argument for contractibility. Let us start with an auxiliary definition

We define $$\begin{gathered}
    \Pi_{M}\colon{\mathbb{R}}^{N} \to {\mathbb{R}}^{M},\ \Pi_{M}(x) = (x_1,\dots,x_{M}),\\
    I-\Pi_{M}\colon{\mathbb{R}}^{N} \to {\mathbb{R}}^{N - M },\ (I-\Pi_{M})(x) = (x_{M+1},\dots, x_{N}).
  \end{gathered}$$ With a slight abuse of notation we will use the same $\Pi$ notation defined above to denote projections of sets of vectors, $\Pi_M\colon 2^{{\mathbb{R}}^{N}}\to 2^{{\mathbb{R}}^{M}}$, and $I-\Pi_{M}\colon2^{{\mathbb{R}}^{N}} \to 2^{{\mathbb{R}}^{N - M }}$.

As suggested in Section \[secmotiv\] to show contractibility of $C(h)$ we first need to show that any of the sets $\Lambda((p_1,p_2))$ forming the coarse covering (Def. \[defAt\]) is contractible for $p\in{{\mathcal{L}}}_2^{n-3,N-3}$. The following theorem is the main result of this section, which relates contractibility of $\Lambda((p_1,p_2))$ to contractibility of a lower dimensional preimage set $C(h')$.

\[thmind1\] Let $\theta\colon \mathcal{L}_{2}^{{n-3},{N-3}} \to 2^{\mathcal{P}_{2(n-1)}^{N-1}}$ be the map defined by . Let $h\in\mathcal{E}^n_+,\ h' = \Pi_{n-2}{h},\ p=(p_1,p_2)\in \mathcal{L}_2^{{n-3},{N-3}},\ n \geq 5$.

If $$\bigcup_{x\in\mathcal{P}_{2(n-3)}^{p_1}}A_{h',p_1,\bold{n-2}}\left({x}\right)$$ is contractible, then $$\Lambda_h((p_1,p_2)) = \bigcup_{x\in\theta((p_1,p_2))}{A_{h,N,\bold{n}}\left(x\right)}$$ is contractible as well.

Theorem \[thmind1\] provides an inductive argument. The induction variable is $n$ (it is highlighted in the statement above using the bold font). $n$ determines the number of persistence points on the considered diagram and the number of local extrema, observe that the number of extrema changes by two for the induction step, which is in turn equivalent to a new persistence point appearing on the sublevel-set filtration diagram.

We have the following immediate corollary from Theorem \[thmind1\] providing a more explicit induction argument.

\[cormain\] Let $h'= \Pi_{n-2}h$. If $$C(h') = \bigcup_{x\in{{\mathcal{P}}}_{2(n-3)}^{p_1}}{A_{h',p_1,n-2}(x)}$$ is contractible for all $n-3\leq p_1\leq N-3$, then $$C(h) = \bigcup_{x\in{{\mathcal{P}}}_{2(n-1)}^{N}}{A_{h,N,n}(x)}$$ is contractible as well.

Assuming contractibility of $\bigcup_{x\in\mathcal{P}_{2(n-3)}^{p_1}}A_{h',p_1,n-2}\left({x}\right)$ for all $n-3\leq p_1\leq N-3$, from Theorem \[thmind1\] we have that $\Lambda_h((p_1,p_2))$ is contractible for all $p=(p_1,p_2)\in \mathcal{L}_2^{{n-3},{N-3}}$. Hence, the nerve complex $${{\mathcal{N}}}\left( \left\{\Lambda_h((p_1,p_2))\right\}_{p\in\mathcal{L}_2^{{n-3},{N-3}}}\right)$$ is the full $N-1$ dimensional simplex (intersection of any nonempty family is contractible), and therefore $C(h)$ is homotopy equivalent to a point.

Now, having already established our theoretical framework, a proof of the main result of this paper is straightforward.

Let $z\in{\mathbb{R}}^N$ be a vector satisfying assumption **A** (or analogously $z\in{\mathcal{B}}$ satisfying assumption **A**, and using $S_h(y)\subset{\mathcal{B}}$ defined as ) . Let $z$ has $n$ (even number) of local extrema, and $h\in{{\mathcal{E}}}^n_+$ be the vector of heights of the local extrema of $z$ fixing their ordering, i.e. $h = \operatorname{cv}(z)^i$. Let $h' = \Pi_3{h}$ be the projection onto the first three coordinates of $h$. From Theorem \[thm:baseCase\] it follows that $C(h')$ is contractible regardless the vector space dimension. Applying the induction from Theorem \[thmind1\] we obtain that $C(h)$ is contractible. Hence, in the case of the compact polytopes $S_h\subset{\mathcal{B}}$, we obviously have that $C(h)\subset{\mathcal{B}}$ is a contractible compact simplicial set.

Exactly the same arguments presented in this section are also true when using the compact building polytopes $S_h$, i.e. $S_h(y)\subset{\mathcal{B}}$, . This will ultimately allows for proving Theorem \[thm:main\] in the compact case.

To prove Theorem \[thmind1\] we need to first show some auxiliary results. First, in Theorem \[thmintersect\] we show that $\Lambda_h$ is a semi-lattice morphism, exactly like $A_h$. Then, we establish the final contractibility argument using several intermediate steps, the two auxiliary Lemma \[lemcontr\],\[lemcontr2\] proved below are necessary for proving the final contractibility argument from Theorem \[thmind1\].

To show the contractibility of $A_h$, we establish series of results proving that the intersection of any family of $\Lambda_h((k_1,k_2))'s$ is contractible.

Let us recall the definition $$\begin{aligned}
\theta&\colon \mathcal{L}_2^{{n-3},{N-3}} \to 2^{\mathcal{P}^{N-1}_{2(n-1)}},\\
\theta(p_1,p_2) &= \left\{ (y_1,\dots, y_{2(n-1)})\colon\ y_{2(n-3)}\leq p_1\leq p_2<y_{2(n-3)+1}\right\}.\end{aligned}$$ To prove the next proposition we define a slightly modified semi-lattice morphism $A_h$

\[defAtilde\] $$\begin{aligned}
\tilde{A}_{h,N,n-2} &\colon \mathbb{L}_{2(n-1)}^{N-1} \to 2^{\mathbb{R}^{N}},\\
  \tilde{A}_{h,N,n-2}\left(w\right) &= A_{h,N,n-2}\left(\Pi_{2(n-3)}w\right)\cap\left[ \bigcup_{(y,y')\in\widetilde{\varphi}_{n-3}(w)}{S_{h,N,n-2}(y)\cap S_{h,N,n-2}(y')}\right]=\\
  &=\left[\bigcap_{k=1}^{n-4}\bigcup_{(v,v')\in \varphi_k(w)}{S_{h,N,n-2}(v)\cap S_{h,N,n-2}(v')}\right] \cap\left[ \bigcup_{(y,y')\in\widetilde{\varphi}_{n-3}(w)}{S_{h,N,n-2}(y)\cap S_{h,N,n-2}(y')}\right]\end{aligned}$$

where $\widetilde{\varphi}_{n-3}\colon \mathbb{L}_{2(n-1)}^{N-1}\to L^N_{n-2}$ is a slightly modified indexing function $\varphi$ for the purpose of the next proposition, and is defined as follows $${\scriptsize
\label{varphin3}
\widetilde{\varphi}_{n-3}(w) =
\begin{cases}
\left\{ (y,y)\in L^N_{n-2}\times L^N_{n-2} : w_{2(n-3)} < y_{n-2} \leq w_{2(n-3)+1}\right\} & \text{if $w_{2(n-3)}<w_{2(n-3)+1}$,} \\
\Big\{ (y,y')\in L^N_{n-2}\times L^N_{n-2} : y_{n-2} = w_{2(n-3)+1},\ y'_{n-2} = w_{2(n-3)}+1,\  \text{$y_j=y'_j$ for $j\neq n-2$}\  \Big\} & \text{if $w_{2(n-3)+1}\leq w_{2(n-3)}$.}
\end{cases}}$$

\[proppieq\] Let $n\geq 5$, $h\in\mathcal{E}^n$. Let $ A_h\colon \mathbb{L}_{2(n-1)}^{N-1} \to 2^{\mathbb{R}^{N}}$ be the map defined by . Let $\tilde{A}_{h} \colon \mathbb{L}_{2(n-1)}^{N-1} \to 2^{\mathbb{R}^{N}}$ be defined by . Let $w\in \mathbb{L}^{N-1}_{2(n-1)}$.

It holds that $$\Pi_M A_h(w) = \Pi_M\tilde{A}_{h',N,n-2}(w),$$ where $h'=\Pi_{n-2}h$, and $M = \max(w_{2(n-3)}, w_{2(n-3)+1})$.

First, we show that $$\Pi_M\left[\bigcap_{k=1}^{n-3}{\bigcup_{(y,y')\in\varphi_k(w)}{S_h(y)\cap S_h(y')}}\right] = \Pi_M\tilde{A}_{h',N,n-2}(w),$$

From the inequalities provided in Def. \[def:calL\] it follows that $M < \min(w_{2(n-2)}, w_{2(n-2)+1})$, and hence $\varphi_{n-2}(w)$ affects only the monotonicity of the $(I-\Pi_M)$-projection of the vectors. Hence

$\bigcup_{(y,y')\in\varphi_{n-2}(w)}{\Pi_M\left[S_{h}(y)\cap S_{h}(y')\right]}$ is the set of all $(h',v)$-monotone vectors, where $v$ is any stricly ordered multi-index, $v\in{L}_M^{n-2}$, and $h' = \Pi_{n-2}h$ $$\bigcup_{(y,y')\in\varphi_{n-2}(w)}{\Pi_M\left[S_{h}(y)\cap S_{h}(y')\right]} = \bigcup_{v\in{L}_M^{n-2}}{S_{h',M,n-2}(v)},$$ and therefore we obtain our claim from the identity $$\begin{gathered}
  \bigcap_{k=1}^{n-2}{\bigcup_{(y,y')\in\varphi_k(w)}{\Pi_M\left[S_{h}(y)\cap S_{h}(y')\right]}} =
  \left\{\bigcap_{k=1}^{n-3}{\bigcup_{(y,y')\in\varphi_k(w)}{\Pi_M\left[S_{h}(y)\cap S_{h}(y')\right]}}\right\}\cap \left\{\bigcup_{(v,v')\in\varphi_{n-2}(w)}{\Pi_M\left[S_{h}(v)\cap S_{h}(v')\right]}\right\}\\
  =\left\{\bigcap_{k=1}^{n-3}{\bigcup_{(y,y')\in\varphi_k(w)}{\Pi_M\left[S_h(y)\cap S_h(y')\right]}}\right\}\cap\left\{\bigcup_{v\in{L}_M^{n-2}}{S_{h',M,n-2}(v)}\right\}=
  \bigcap_{k=1}^{n-3}{\bigcup_{(y,y')\in\varphi_k(w)}{\Pi_M\left[S_h(y)\cap S_h(y')\right]}}.\end{gathered}$$ The last equality holds due to the fact that $\bigcap_{k=1}^{n-3}{\bigcup_{(y,y')\in\varphi_k(w)}{\Pi_M\left[S_h(y)\cap S_h(y')\right]}}\subset \bigcup_{v\in{L}_M^{n-2}}{S_{h',M,n-2}(v)}$.

\[lemcontr\] Let $\theta\colon \mathcal{L}_2^{{n-3},{N-3}} \to 2^{\mathcal{P}_{2(n-1)}^{N-1}}$ be the map defined by . Let $n \geq 5$. Let $h\in\mathcal{E}^n$. Let $p = (p_1,p_2) \in \mathcal{L}_2^{{n-3},{N-3}}$. Let $ A_h\colon \mathbb{L}_{2(n-1)}^{N-1} \to 2^{\mathbb{R}^{N}}$ be the map defined by .

For any $$\label{Jsubsettheta}
    \mathcal{J}\subset\theta((p_1, p_2)) \subset \mathcal{P}_{2(n-1)}^{N-1},\ \mathcal{J} \neq \emptyset$$ it holds that the contractibility of $$A_{h,N,n}\left(\wedge_{x\in\mathcal{J}}{x}\right) =
  \left[\bigcap_{k=1}^{n-2} \left( \bigcup_{(y,y')\in \varphi_k(\wedge_{x\in\mathcal{J}}{x})} S_h(y)\cap S_h(y')  \right)\right]$$ is equivalent to the contractibility of $$\tilde{A}_{h',N,n-2}\left(\wedge_{x\in\mathcal{J}}{x}\right) = A_{h',N,n-2}\left(\Pi_{2(n-3)}(\wedge_{x\in\mathcal{J}}{x})\right)\cap\left[ \bigcup_{(y,y')\in\widetilde{\varphi}_{n-3}(\wedge_{x\in\mathcal{J}}{x})}{S_{h',N,n-2}(y)\cap S_{h',N,n-2}(y')}\right],$$ where $h' = \Pi_{n-2}{h}$.

Let us denote $${x^\wedge}= \wedge_{x\in\mathcal{J}}{x}.$$

And $$M = \max({x^\wedge}_{2(n-3)}, {x^\wedge}_{2(n-3)+1}).$$

First, let us consider the case $$A_h({x^\wedge}) = \emptyset,\text{ or }A_{h',N,n-2}\left(\Pi_{2(n-3)}{x^\wedge}\right)=\emptyset,$$ then $$A_h\left({x^\wedge}\right) = \tilde{A}_{h',N,n-2}\left({{x^\wedge}}\right)= \emptyset.$$ Therefore, the claim holds in this case.

Second, we assume $$\bigcap_{k=1}^{n-3} \left( \bigcup_{(y,y')\in \varphi_k({x^\wedge})} S_h(y)\cap S_h(y')  \right) \neq \emptyset.$$

Which from Theorem \[thmemptyint\] means that $$\label{eqindcond}
  {x^\wedge}_{2k} + 1 < {x^\wedge}_{2k+3}\text{ for all $k=1,2,\dots, n-4$}.$$

Observe that due to the condition it holds that $$\label{yineq}
    {x^\wedge}_{2(n-3)} \leq p_1,\text{ and } p_2 < {x^\wedge}_{2(n-3)+1},$$

It holds that $$\label{emptyset}
    \left(\bigcup_{(y,y)\in\varphi_{n-2}({x^\wedge})}{S_h(y)}\right)  \cap \left(\bigcup_{(v,v')\in\varphi_k({x^\wedge})}{S_h(v)\cap S_h(v')}\right) \neq \emptyset\text{ for any }k\in\{1,\dots,n-3\},$$ as we assumed , and it holds that $${x^\wedge}_{2(n-3)}+1 < {x^\wedge}_{2(n-3)+3},$$ which holds from ${x^\wedge}_{2(n-3)} < p_1$, and $p_2 < {x^\wedge}_{2(n-3)+3}$. Hence, holds from Theorem \[thmemptyint\].

First, assume that $\tilde{A}_{h',N,n-2}( {x^\wedge})$ is contractible. It means that there exists a vector $\bar{z}\in \tilde{A}_{h',N,n-2}({x^\wedge})$, and a continuous map $H\colon[0,1]\times \tilde{A}_{h',N,n-2}({x^\wedge}) \to \tilde{A}_{h',N,n-2}({x^\wedge})$ a deformation retraction of $\tilde{A}_{h',N,n-2}({x^\wedge})$ to the single point $\bar{z}$, such that for any $z\in \tilde{A}_{h',N,n-2}({x^\wedge})$ it holds that $$H([0,1],z)\in \tilde{A}_{h',N,n-2}({x^\wedge}),\ H(0,z) = z,\text{ and }H(1,z) = \overline{z}.$$

From Prop. \[proppieq\] we have the following identity $$\label{ipiid}
    \Pi_{M}\tilde{A}_{h',N,n-2}({x^\wedge})=\Pi_{M}A_h({x^\wedge}),$$

We define the homotopy $G\colon[0,1]\times A_h({x^\wedge})\to A_h({x^\wedge})$ coordinate-wise. Let $z'\in A_h({x^\wedge})$. In general, it does not hold that $z'\in \tilde{A}_{h',N,n-2}({x^\wedge})$, but $\Pi_{M}z' \in \Pi_{M}\tilde{A}_{h',N,n-2}({x^\wedge})$ does hold from . $$\begin{aligned}
    G_k(t,z') &= (\Pi_{M}H)_{k}(t, \Pi_{M}z'),\text{ for }k=1,\dots,M,\nonumber\\
    G_k(t,z')  &= t\cdot\bar{z}'_k + (1-t)z'_k,\text{ for }k=M+1,\dots,N,\nonumber
  \end{aligned}$$

where $$\bar{z}' = (\underbrace{h_{n-1},\dots,h_{n-1}}_{{x^\wedge}_{2(n-1)} - M }, \underbrace{h_{n},\dots,h_{n}}_{N-{x^\wedge}_{2(n-1)}}).$$

It holds that $$G(1,z') = (\Pi_{M}{\bar{z}}, \bar{z}').$$ First, we show that $(\Pi_{M}\bar{z},\bar{z}') \in A_h\left({x^\wedge}\right)$. Observe that $$\bar{z}'\in \bigcup_{(y,y')\in\varphi_{n-2}({x^\wedge})}{(I-\Pi_{M})S_h(y)} = (I-\Pi_{M})\left(\bigcup_{(y,y')\in\varphi_{n-2}({x^\wedge})}{S_h(y)}\right) =(I-\Pi_{M})A_h\left({x^\wedge}\right),$$ because clearly $\bar{z}' \in (I-\Pi_{M})S_h(y)$ for all $(y,y')\in\varphi_{n-2}({x^\wedge})$. The last equality holds due to the $(I-\Pi)_{M}$-projection of the vectors in $A_h\left({x^\wedge}\right)$ is determined by $\varphi_{n-2}({x^\wedge})$ exclusively, as for any $(y,y')\in\varphi_{n-3}({x^\wedge})$ it holds that $y,y'\leq M$.

It also holds from that $$\Pi_{M}\bar{z} \in \Pi_{M}\tilde{A}_{h',N,n-2}( {x^\wedge}) = \Pi_{M}A_h({x^\wedge}) .$$

Now we show that $$G([0,1], z')\in A_h({x^\wedge}).$$ From the assumption it follows that $\Pi_MH([0,1],z')\in \Pi_{M}\tilde{A}_{h',N,n-2}({x^\wedge})$, hence

$\Pi_{M}G([0,1], z')\in \Pi_{M}\tilde{A}_{h',N,n-2}({x^\wedge}) = \Pi_{M}A_h({x^\wedge})$.

It reminds to show that ${(I-\Pi_{M})G([0,1],z')\in (I-\Pi_{M})A_h({x^\wedge})}$.

Observe that $$(I-\Pi_{M})G([0,1],z') = t\cdot\bar{z}' + (1-t)(I-\Pi_{M})z' \in \left(\bigcup_{(y,y')\in\varphi_{n-2}({x^\wedge})}{(I-\Pi_{M})S_h(y)}\right),$$ as $\bar{z}', (I-\Pi_{M})z' \in (I-\Pi_{M})S_h(y)$ for all $(y,y')\in\varphi_{n-2}({x^\wedge})$, and $\bigcup_{(y,y')\in\varphi_{n-2}({x^\wedge})}{(I-\Pi_{M})S_h(y)}$ is a union of convex sets, hence $$\begin{gathered}
    t\cdot\bar{z}' + (1-t)(I-\Pi_{M})z' \in \left(\bigcup_{(y,y')\in\varphi_{n-2}({x^\wedge})}{(I-\Pi_{M})S_h(y)}\right) = \\=(I-\Pi_{M})\left(\bigcup_{(y,y')\in\varphi_{n-2}({x^\wedge})}{S_h(y)}\right) = (I-\Pi_{M})A_h\left({x^\wedge}\right).
  \end{gathered}$$

Finally, the map $G$ is continuous, as it is a product of two continuous functions ($\Pi_{M}G=\Pi_{M}H$ is continuous by the assumption, $(I-\Pi_{M})G$ is a linear homotopy). Hence $G$ is a deformation retraction of $A_h\left({x^\wedge}\right)$ to the single point $(\Pi_{M}{\bar{z}}, \bar{z}')$.

Vice-versa, assuming that $A_h({x^\wedge})$ is contractible, i.e. there exists a continuous map $$G\colon[0,1]\times A_h({x^\wedge})\to A_h({x^\wedge}),$$ such that $$G(0,z) = z,\text{ and }G(1,z) = \bar{z},\text{ for all }z \in A_h({x^\wedge})$$ we define the continuous map $H\colon[0,1]\times \tilde{A}_{h',N,n-2}({x^\wedge}) \to \tilde{A}_{h',N,n-2}({x^\wedge})$ coordinate-wise $$\begin{aligned}
    H_k(t,z') &= (\Pi_{M}G)_{k}(t, \Pi_{M}z'),\text{ for }k=1,\dots,M,\nonumber\\
    H_k(t,z')  &= t\cdot\bar{z}'_k + (1-t)z'_k,\text{ for }k = M+1,\dots,N,\nonumber
 \end{aligned}$$ where $$\bar{z}' = \underbrace{(h_{n-1},\dots, h_{n-1})}_{N - M}.$$

Performing the same analysis as in the opposite case, we show that for any $z'\in \tilde{A}_{h',N,n-2}({x^\wedge})$ $$H(1, z) = (\Pi_{M}{\bar{z}}, \bar{z}') \in \tilde{A}_{h',N,n-2}({x^\wedge}),$$ and $$H([0,1],z) \in \tilde{A}_{h',N,n-2}({x^\wedge})$$ (observe that $(1-t)(I-\Pi_{M})z' +t\bar{z}'\in (I-\Pi_{M})\tilde{A}_{h',N,n-2}({x^\wedge})$ as $(1-t)(I-\Pi_{M})z' +t\bar{z}'$ is a non-decreasing vector for all $t\in[0,1]$). Hence $H$ is a deformation retraction of $\tilde{A}_{h',N,n-2}({x^\wedge})$ to a single point.

\[corind\] Let $\theta\colon \mathcal{L}_{2}^{{n-3},{N-3}} \to 2^{\mathcal{P}_{2(n-1)}^{N-1}}$ be the map defined by . Let $h\in \mathcal{E}^n_+$. Let $n \geq 5$.

If $$\bigcup_{x\in\theta((p_1,p_2))}{\tilde{A}_{h',N,n-2}\left({x}\right)}$$ is contractible, then $$\bigcup_{x\in\theta((p_1,p_2))}{A_{h,N,n}\left(x\right)}$$ is contractible as well.

Follows from Lemma \[lemcontr\].

From Lemma \[lemcontr\] for any $\mathcal{J}\subset\theta((p_1, p_2)) \subset \mathcal{P}_{2(n-1)}^{N-1}$, $\mathcal{J} \neq \emptyset$ the contractibility of $$\tilde{A}_{h',N,n-2}\left(\wedge_{x\in\mathcal{J}}{x}\right).$$ is equivalent to the contractibility of $$A_h\left(\wedge_{x\in\mathcal{J}}{x}\right)$$ Hence, as $\mathcal{J}$ is arbitrary the claim follows from the Nerve Theorem.

\[lemcontr2\] Let $\theta\colon \mathcal{L}_2^{{n-3},{N-3}} \to 2^{\mathcal{P}_{2(n-1)}^{N-1}}$ be the map defined by . Let $n \geq 5$. Let $h\in \mathcal{E}^n_+$. Let $p=(p_1,p_2) \in \mathcal{L}_2^{{n-3},{N-3}}$. Let $ A_{h',N,n-2}\colon \mathcal{L}_{2(n-3)}^{N-1} \to 2^{\mathbb{R}^{N}}$ be the map defined by .

For any $$\label{Jsubsettheta2}
  \mathcal{J}\subset\theta((p_1, p_2)) \subset \mathcal{P}_{2(n-1)}^{N-1},\ \mathcal{J} \neq \emptyset$$ it holds that the contractibility of $$\tilde{A}_{h',N,n-2}\left(\wedge_{x\in\mathcal{J}}{x}\right) =\\
  A_{h',N,n-2}\left(\Pi_{2(n-3)}(\wedge_{x\in\mathcal{J}}{x})\right)\cap\left[ \bigcup_{(y,y')\in\widetilde{\varphi}_{n-3}(\wedge_{x\in\mathcal{J}}{x})}{S_{h',N,n-2}(y)\cap S_{h',N,n-2}(y')}\right]$$ is equivalent to the contractibility of $$A_{h',M,n-2}\left(\Pi_{2(n-3)}\left(\wedge_{x\in\mathcal{J}}{x}\right)\right) =
  \left[\bigcap_{k=1}^{n-4} \left( \bigcup_{\substack{(y,y')\in \varphi_k{(\Pi_{2(n-3)}\left(\wedge_{x\in\mathcal{J}}{x}\right))}}} S_{h',M,n-2}(y)\cap S_{h',M,n-2}(y')  \right)\right],$$ where $M=\max\left(\left(\wedge_{x\in\mathcal{J}}{x}\right)_{2(n-3)}, \left(\wedge_{x\in\mathcal{J}}{x}\right)_{2(n-3)+1}\right)$, and $h' = \Pi_{n-2}{h}$.

Observe that Lemma \[lemcontr\] and Lemma \[lemcontr2\] together provide the following contractibility equivalence.

The contractibility of $$A_{h,N,n}\left(\wedge_{x\in\mathcal{J}}{x}\right) =
  \left[\bigcap_{k=1}^{n-2} \left( \bigcup_{(y,y')\in \varphi_k(\wedge_{x\in\mathcal{J}}{x})} S_h(y)\cap S_h(y')  \right)\right].$$ is equivalent to the contractibility of $$A_{h',M,n-2}\left(\Pi_{2(n-3)}\left(\wedge_{x\in\mathcal{J}}{x}\right)\right) =
  \left[\bigcap_{k=1}^{n-4} \left( \bigcup_{\substack{(y,y')\in \varphi_k{(\Pi_{2(n-3)}\left(\wedge_{x\in\mathcal{J}}{x}\right))}}} S_{h',M,n-2}(y)\cap S_{h',M,n-2}(y')  \right)\right],$$ where $h' = \Pi_{n-2}{h}$.

Let us denote $${x^\wedge}= \wedge_{x\in\mathcal{J}}{x}.$$

It holds that $$\label{PiMN}
    A_{h',M,n-2}(\Pi_{2(n-3)}{x^\wedge}) = \Pi_M\tilde{A}_{h',N,n-2}({x^\wedge}),$$ as any $\Pi_Mz\colon z\in \tilde{A}_{h',N,n-2}({x^\wedge})$ is necessarily $(h',\Pi_{2(n-1)-3}{x^\wedge})$-monotone.

The contractibility of $A_{h',M,n-2}\left(\Pi_{2(n-3)}{x^\wedge}\right)$ follows trivially from the contractibility of

$\tilde{A}_{h',N,n-2}\left({x^\wedge}\right)$ (it is a projected set, see ). To show the opposite implication assume that $A_{h',M,n-2}\left(\Pi_{2(n-3)}{x^\wedge}\right)$ is contractible. It means that there exists a vector $\bar{z}\in A_{h',M,n-2}\left(\Pi_{2(n-3)}{x^\wedge}\right)$, and a continuous map $H\colon[0,1]\times A_{h',M,n-2}\left(\Pi_{2(n-3)}{x^\wedge}\right) \to A_{h',M,n-2}\left(\Pi_{2(n-3)}{x^\wedge}\right)$ a deformation retraction of $A_{h',M,n-2}\left(\Pi_{2(n-3)}{x^\wedge}\right)$ to the single point $\bar{z}$, such that for any $z\in A_{h',M,n-2}\left(\Pi_{2(n-3)}{x^\wedge}\right)$ it holds that $$H([0,1],z)\in A_{h',M,n-2}\left(\Pi_{2(n-3)}{x^\wedge}\right),\ H(0,z) = z,\text{ and }H(1,z) = \bar{z}.$$

Let $z'\in \tilde{A}_{h',N,n-2}\left({x^\wedge}\right)$. We define a homotopy $G\colon[0,1]\times \tilde{A}_{h',N,n-2}\left({x^\wedge}\right) \to \tilde{A}_{h',N,n-2}\left({x^\wedge}\right)$ as follows $$\begin{aligned}
  G_k(t,z') &= H_k(t,\Pi_Mz')\text{ for }k = 1,\dots,M,\nonumber\\
  G_k(t,z') &= (1-t)(I-\Pi_M)z'_k + t\bar{z}'_k\text{ for }k = M+1,\dots,N,\label{Gk}\end{aligned}$$ where $\bar{z}=(\underbrace{h_{n-1},\dots,h_{n-1}}_{N-M})$. It holds that $G(1,z') = (\bar{z},\bar{z}')$. First, it holds that $(\bar{z},\bar{z}')\in \tilde{A}_{h',N,n-2}\left({x^\wedge}\right)$, as $\bar{z}\in \Pi_M\tilde{A}_{h',N,n-2}\left({x^\wedge}\right)$, and also $(I-\Pi_M)(\bar{z},\bar{z}')$ satisfies the monotonicity property ($\bar{z}'$ is nondecreasing), hence $(\bar{z},\bar{z}')$ is $(h',\Pi_{2(n-3)+1}{x^\wedge})$-monotone.

Second, we show that $G([0,1],z')\in \tilde{A}_{h',N,n-2}\left({x^\wedge}\right)$. It holds that $\Pi_MG([0,1],z')\in A_{h',M,n-2}\left(\Pi_{2(n-3)}{x^\wedge}\right) = \Pi_M\tilde{A}_{h',N,n-2}\left({x^\wedge}\right)$. It reminds to show that $(I-\Pi_M)G([0,1],z')\in (I-\Pi_M)\tilde{A}_{h',N,n-2}\left({x^\wedge}\right)$. Observe that $(I-\Pi_M)\tilde{A}_{h',N,n-2}\left({x^\wedge}\right)$ is a convex set (it is essentially set of nondecreasing vectors), hence due to the straight line homotopy within the $(I-\Pi_M)$-projection, it holds that $(I-\Pi_M)G([0,1],z')\in (I-\Pi_M)\tilde{A}_{h',N,n-2}\left({x^\wedge}\right)$.

Finally, the map $G$ is continuous, as it is a product of two continuous functions ($H$ is continuous by the assumption, $(I-\Pi_{M})G$ is a linear homotopy). Hence $G$ is a deformation retraction of $\tilde{A}_{h',N,n-2}\left({x^\wedge}\right)$ to the single point $(\bar{z}, \bar{z}')$.

\[thmind\] Let $\theta\colon \mathcal{L}_{2}^{{n-3},{N-3}} \to 2^{\mathcal{P}_{2(n-1)}^{N-1}}$ be the map defined by . Let $h\in \mathcal{E}^n_+,\ h' = \Pi_{n-2}{h},\ p=(p_1,p_2)\in \mathcal{L}_2^{{n-3},{N-3}},\ n \geq 5$.

If $$\bigcup_{x\in\mathcal{P}_{2(n-3)}^{p_1}}A_{h',p_1,n-2}\left({x}\right)$$ is contractible, then $$\Lambda_h((p_1,p_2)) = \bigcup_{x\in\theta((p_1,p_2))}{A_{h,N,n}\left(x\right)}$$ is contractible as well.

Let $p\in\mathcal{L}_2^{{n-3},{N-3}}$. Let $$\mathcal{J}\subset\theta((p_1, p_2)),\quad \mathcal{J}\neq\emptyset.$$ From Theorem \[thmintersect\] it follows that $$\label{Awedge}
    \bigcap_{x\in\mathcal{J}}{A_h(x)} = A_h( \wedge_{x\in\mathcal{J}}{x} ).$$ From Lemma \[lemcontr\] we have that the contractibility of is equivalent to the contractibility of $$\tilde{A}_{h',N,n-2}\left(\wedge_{x\in\mathcal{J}}{x}\right),$$ As $\mathcal{J}\neq\emptyset$ is arbitrary, as a result we obtain that if for all ${{\mathcal{J}}}$ $\tilde{A}_{h',N,n-2}\left(\wedge_{x\in\mathcal{J}}{x}\right)$ is contractible, and hence from Nerve Theorem $$\bigcup_{x\in\theta((p_1,p_2))}{\tilde{A}_{h',N,n-2}(x)},$$ is contractible, then for all ${{\mathcal{J}}}\neq\emptyset$ $A_h( \wedge_{x\in\mathcal{J}}{x})$ is contractible as well, and hence from Nerve Theorem $$\Lambda_h((p_1,p_2)) = \bigcup_{x\in\theta((p_1,p_2))}{A_h(x)}$$ is contractible as well.

Observe that $x_{2(n-3)+1}\leq p_1$. It holds that $$\tilde{A}_{h',N,n-2}(x)\subset \tilde{A}_{h',N,n-2}\left(\Pi_{2(n-3)}x,p_1,(I-\Pi_{2(n-3)+1})x\right)\text{ for all }x\in\theta((p_1,p_2)),$$ which follows from the inclusion $$\bigcup_{(y,y')\in\widetilde{\varphi}_{n-3}({x})}{S_{h',N,n-2}(y)\cap S_{h',N,n-2}(y')}\subset  \bigcup_{(y,y')\in\widetilde{\varphi}_{n-3}({\left(\Pi_{2(n-3)}x,p_1,(I-\Pi_{2(n-3)+1})x\right)})}{S_{h',N,n-2}(y)\cap S_{h',N,n-2}(y')},$$ and the obvious equality $$\Pi_{2(n-3)}({x}) =  \Pi_{2(n-3)}\left(\Pi_{2(n-3)}{x},p_1,(I-\Pi_{2(n-3)+1}){x}\right),$$ holding for all $x\in\theta((p_1,p_2))$ – compare .

Hence, some sets merge up in the union, and we get $$\bigcup_{x\in\theta((p_1,p_2))}{\tilde{A}_{h',N,n-2}(x)} = \bigcup_{x\in\theta((p_1,p_2))}{\tilde{A}_{h',N,n-2}\left(\Pi_{2(n-3)}x,p_1,(I-\Pi_{2(n-3)+1})x\right)},$$

Moreover, from Lemma \[lemcontr2\] we have that for any $\mathcal{J}\subset\theta((p_1,p_2))$ the contractibility of

$\tilde{A}_{h',N,n-2}\left((\Pi_{2(n-3)}x,p_1,(I-\Pi_{2(n-3)+1})x)\right)$ is equivalent to the contractibility of $A_{h',p_1,n-2}\left(\Pi_{2(n-3)}x\right)$ (it holds that $M=p_1$). As for any $x\in\theta((p_1,p_2))$, we have that $\Pi_{2(n-3)}x\in \mathcal{P}_{2(n-3)}^{p_1}$, finally, we obtain that if $$\bigcup_{y\in\mathcal{P}_{2(n-3)}^{p_1}}A_{h',p_1,n-2}\left({y}\right).$$ is contractible, then $\Lambda_h((p_1,p_2))$ is contractible as claimed.

Contractibility of the preimage of regions in the persistence plane {#preimageregions}
===================================================================

\[defrregion\] Let $${\mathfrak{R}}\subset{\mathsf{Per}}$$ be a set of points on the persistence plane, such that each ${\mathsf{diag}}\in{\mathfrak{R}}$ is composed out of a finite number ($M>2$) of points ${\mathsf{diag}}=\{p_1,p_2,\dots,p_M\}$, $p_1 = (p_1,\infty),\ p_2 = (p_2^b, p_2^d),\ \dots,\ p_M = (p_M^b, p_M^d)$.

Assume that ${\mathfrak{R}}$ has the following structure $${\mathfrak{R}}= \bigcup_{i=1}^M{R_i}\text{, where $R_i\subset \mathbb{E}$, and}$$ $R_1 = [b_1^-, b_1^+]\times\{\infty\}$, $R_i = [b_i^-, b_i^+]\times[d_i^-, d_i^+]$, where $b_i^-<b_i^+$, and $d_i^-<d_i^+$ (when $b_i^-=b_i^+, d_i^-=d_i^+$ then it is a point diagram case considered in the previous sections). We assume that the regions have empty intersections, i.e. it holds that $$\label{bcond}
  b_i^+< b_{i+1}^-\text{ for all }i=1,\dots,M-1,$$ and $$\label{dcond}
  d_i^+ < d_{i+1}^-\text{ for all }i=2,\dots,M-1\quad(d_1=\infty).$$

\[defdregion\] Let $\delta>0$ be a small parameter. Let $${\mathfrak{D}}_\delta \subset {\mathsf{Per}}$$ be a set of persistence diagrams, such that each ${\mathsf{diag}}\in{\mathfrak{D}}_\delta$ is composed out of a finite $(M_\delta>0)$ number of points $\{r_1,r_2,\dots,r_{M_\delta}\}$ satisfying $0\leq r_i^d - r_i^b \leq \delta$, and $$\label{rcond}
[r_j^b,r_j^d]\nsubseteq [r_i^b,r_i^d]\text{ for all $j\neq i$.}$$

Observe that it may hold that $r_i^d - r_i^b=0$ for a nonempty set of indices, i.e. some of the points in ${\mathsf{diag}}$ can be located precisely on the diagonal.

We use the following notation for the union of persistence plane regions defined in Defs. \[defrregion\],\[defdregion\] $$\label{eqnregion}
{\mathfrak{N}}_\delta = {\mathfrak{R}}\cup {\mathfrak{D}}_\delta.$$ For a given diagram ${\mathsf{diag}}\in{\mathfrak{N}}_\delta$ we denote its projection onto its part contained in ${\mathfrak{R}}$ and ${\mathfrak{D}}_\delta$, by $\Pi_{{\mathfrak{R}}}$ and $\Pi_{{\mathfrak{D}}_\delta}$ respectively.

The motivation behind the conditions , and is that the functions that get mapped to ${\mathfrak{N}}_\delta$ by ${\mathsf{Dgm}}$ have clearly separated extrema. The definition of $\operatorname{cv}$ (Definition \[defcv\]) has a natural extension to the multi-valued map $\operatorname{cv}\colon 2^{{\mathbb{R}}^N}\to 2^{{{\mathcal{E}}}_+}$ for class of sets ${\mathfrak{N}}_\delta$ as for the extrema heights values $z_{i_j}^-, z_{i_j}^+$ it follows from , , that it hold $z_{i_{j-1}}^+ < z_{i_j}^-$, which basically imply that $\operatorname{cv}({\mathsf{Dgm}}^{-1}({\mathfrak{N}}_\delta))$ is well defined and $\operatorname{cv}({\mathsf{Dgm}}^{-1}({\mathfrak{N}}_\delta))\subset {{\mathcal{E}}}_+$. All the other sets $\operatorname{cv}({\mathsf{Dgm}}^{-1}({\mathfrak{N}}_\delta))^j$ for $i\neq j$ are related by permuting the vector of extrema heights (such that it is still in ${{\mathcal{E}}}_+$), the number of such permutations is denoted by $I({\mathsf{Dgm}}^{-1}({\mathfrak{N}}_\delta))$. $z_{i_j}^-$ is the minimal value of the interval of the extremum height values, and $z_{i_j}^+$ is the maximal value of the interval of the extremum height values.

Using this new definition of $\operatorname{cv}$, Lemma \[lempreim\] can be also obtained for the preimage of ${\mathfrak{N}}_\delta$. Namely, we have the following corollary

Let $\delta>0$ be a small parameter. Let ${\mathfrak{N}}= {\mathfrak{N}}_\delta\subset {\mathsf{Per}}$, be a region on persistence plane defined in . Then the preimage ${\mathsf{Dgm}}^{-1}({\mathfrak{N}})\subset {\mathbb{R}}^N$ is composed out of a finite number of components, i.e. $${\mathsf{Dgm}}^{-1}({\mathfrak{N}}) = \bigcup_{i=1}^{I({\mathsf{Dgm}}^{-1}({\mathfrak{N}}))}{C(\operatorname{cv}({\mathsf{Dgm}}^{-1}({\mathfrak{N}}))^i)},$$ $C(\operatorname{cv}({\mathsf{Dgm}}^{-1}({\mathfrak{N}}))^i)\subset {\mathbb{R}}^N$ is such that for $i\neq j$ it holds that

-   $C(\operatorname{cv}({\mathsf{Dgm}}^{-1}({\mathfrak{N}}))^i)$, $C(\operatorname{cv}({\mathsf{Dgm}}^{-1}({\mathfrak{N}}))^j)$ are not path connected, i.e. that for any $z\in  C(\operatorname{cv}({\mathsf{Dgm}}^{-1}({\mathfrak{N}}))^i)$ and $z'\in C(\operatorname{cv}({\mathsf{Dgm}}^{-1}({\mathfrak{N}}))^j)$, there is no continuous path connecting $z$ with $z'$ in ${\mathsf{Dgm}}^{-1}({\mathfrak{N}})$.

-   each $C(\operatorname{cv}({\mathsf{Dgm}}^{-1}({\mathfrak{N}}))^i)$ is characterized by the equivalence class of the associated chiral merge tree.

Now let us focus on analyzing a given component $C(\operatorname{cv}({\mathsf{Dgm}}^{-1}({\mathfrak{N}}))^i)$.

We also naturally extend the definition of map $C$ (Definition \[eqCh\]) for sets ${\mathcal{H}}\subset{{\mathcal{E}}}^n_+$ $$C({\mathcal{H}}) = \left\{ z\in{\mathbb{R}}^{N}\colon \text{$z$ is $(y,h)$-monotone for any $y\in L_n^N$, $h\in{\mathcal{H}}$} \right\},\text{ and}\ C({\mathcal{H}}) = \bigcup_{\substack{y\in L_n^N\\h\in{\mathcal{H}}}}{S_h(y)}.$$ The analogous result to Proposition \[prop:Spolytope\] holds, i.e.

Let $y\in L_n^N$, $\delta>0$ a small parameter. Given ${\mathfrak{N}}={\mathfrak{N}}_\delta$ a set satisfying , and ${\mathcal{H}}=\operatorname{cv}({\mathsf{Dgm}}^{-1}({\mathfrak{N}}))^i \subset {{\mathcal{E}}}_+$ one of the sets defined by map $\operatorname{cv}$ applied to ${\mathfrak{N}}$. The set $\bigcup_{h\in{\mathcal{H}}}{S_{h}(y)}$ is a closed convex polytope.

If $S_h(y)\subset{\mathcal{B}}$ is defined as , and ${\mathcal{H}}\subset {{\mathcal{E}}}_+^n$, then $\bigcup_{h\in{\mathcal{H}}}{S_{h}(y)}\subset{\mathcal{B}}$ is additionally compact.

From the definition of $S_{h}(y)$, $\bigcup_{h\in{\mathcal{H}}}{S_{h}(y)}$ is the intersection of a finite number of half-spaces $z_1\geq z_2,\ z_2\geq z_3,\ \dots\ , z_{y_1-1} \geq g_1,\ \hat{h}_1^+\geq g_1,\ g_1\geq \hat{h}_1^-$ etc. In case $z\in{\mathcal{B}}$ it is additionally compact, as all of $S_h(y)$’s forming the union are compact.

From $$C({\mathcal{H}}) = \bigcup_{\substack{y\in L_n^N\\h\in{\mathcal{H}}}}{S_h(y)}$$ It follows immediately that component $C({\mathcal{H}})$ is a *finite union of polytopes*.

Now, to establish the contractibility of $C({\mathcal{H}})$ we show that it can be continuously contracted to $C\left((z_{i_1}^-, z_{i_2}^+,\dots,z_{i_n}^-)\right)$ (observe that $(z_{i_1}^-, z_{i_2}^+,\dots,z_{i_n}^-)\in{{\mathcal{E}}}_+$ ), which establishes the contractibility.

\[thm:mainNdelta\] Let $y\in L_n^N$. Given ${\mathfrak{N}}= {\mathfrak{N}}_\delta$ a set satisfying . For all $1\leq i\leq I({\mathsf{Dgm}}^{-1}({\mathfrak{N}}))$, preimage component $C(\operatorname{cv}({\mathsf{Dgm}}^{-1}({\mathfrak{N}}))^i)$ is contractible.

Let us fix $1\leq i\leq I({\mathsf{Dgm}}^{-1}({\mathfrak{N}}))$. We define a continuous homotopy $H\colon[0,1]\times{\mathbb{R}}^N\to{\mathbb{R}}^N$, contracting $C(\operatorname{cv}({\mathsf{Dgm}}^{-1}({\mathfrak{N}}))^i)$ to $C\left((z_{i_1}^-, z_{i_2}^+,\dots,z_{i_n}^-)\right)$, whose contractibility is proved using the theory developed in the prequel.

Let us pick any ${\mathsf{diag}}\in{\mathfrak{N}}$, and a vector $z$, such that $\operatorname{cv}(z)\in \operatorname{cv}({\mathsf{Dgm}}^{-1}({\mathfrak{N}}))^i$, such that ${\mathsf{Dgm}}(z) = {\mathsf{diag}}$. Precisely, we will define $H$, such that $$H(0,z) = z,\text{ and }H(1,z) = w\text{, for some }w\in C((z_{i_1}^-, z_{i_2}^+,\dots,z_{i_n}^-)),$$ homotopy $H$ is constructed as a composition of two ’partial’ homotopies $$\label{defH}
H(\lambda, z) = \left\{\begin{matrix}H_d(2\lambda, z)&\text{if }\lambda\in[0,\frac12],\\H_l(2(\lambda-\frac12),H_d(1, z))&\text{ if }\lambda\in[\frac12,1].\end{matrix}\right.$$ The role of homotopy $H_d$ is to ’flatten out’ the part of $z$ corresponding to the diagram in $\mathcal{D}_\delta$, contained in the neighborhood of the diagonal. Whereas, $H_l$ transforms the local extrema having heights determined by a diagram in $\mathcal{R}$, and their neighborhoods to plateaus having heights determined by $(z_{i_1}^-, z_{i_2}^+,\dots,z_{i_n}^-)$.

Let us first define homotopy $H_d$. Let us pick any ${\mathsf{diag}}\in{\mathfrak{N}}$, and a vector $z\in C(\operatorname{cv}({\mathsf{Dgm}}^{-1}({\mathfrak{N}}))^i)$, such that ${\mathsf{Dgm}}(z) = {\mathsf{diag}}$. $H_d$ works by removing all components of the sublevel set filtration of $(\mathcal{S}, z)$, corresponding to the persistence points found in the defined neighbourhood of the diagonal ${\mathfrak{D}}_\delta$. Consider $r_1=(r_1^b, r_1^d)$ the first point on $\Pi_{{\mathfrak{D}}_\delta}{\mathsf{diag}}$. Let $\{z_{s(r_1)},\dots, z_{e(r_1)}\}$ be the sequence of $z$ components such that $r_1^b\leq z_j\leq r_1^d$ for all $s(r_1)\leq j\leq e(r_1)$, and the corresponding local minimum and local maximum is within this range of indices. The existence of such a unique sequence of indices follows from the second assumption on ${\mathfrak{D}}_\delta$, i.e. for all $j\neq i$ it holds that $[r_j^b,r_j^d]\nsubseteq [r_i^b,r_i^d]$. Also we define $H_d$ locally for this range of indices $$H_d(\lambda, z)_j = (1 - \lambda)z_j + \lambda r_1^b.$$ We define the homotopy $H_d$ analogously within all subsequences of indices determined by all the other intervals $[r_b^2, r_d^2], [r_b^3, r_d^3], \dots$. For all indices $k$ that are not considered above we use the constant homotopy $H_d([0,1], z)_k = z_k$. As $H_d$ creates plateaus in place of all local extrema defining the (noisy) points on ${\mathfrak{D}}_\delta$, hence ${\mathsf{Dgm}}(H_d(1,z))$ has all its points within ${\mathfrak{R}}$, and all the remaining local extrema of $H_d(1,z)$ are defined by the points in ${\mathfrak{R}}$.

Let us now define homotopy $H_l$. Let us pick any ${\mathsf{diag}}\in{\mathfrak{N}}$, such that $\Pi_{{\mathfrak{D}}_\delta}$ consists of only diagonal points (i.e. the persistence noise is flatten out), and a vector $z\in C(\operatorname{cv}({\mathsf{Dgm}}^{-1}({\mathfrak{N}}))^i)$, such that ${\mathsf{Dgm}}(z) = {\mathsf{diag}}$. From the assumption the first birth value of $\Pi_{{\mathfrak{R}}}{{\mathsf{diag}}}$ is in interval $R_1 = [b_1^-, b_1^+)$, hence, the first component appearing in the sublevel set filtration of complex $(\mathcal{S},z)$ is born in the range $[b_1^-, b_1^+)$. We pick $\{ s(b_1),\dots, e(b_1)\}$, the set of indices, such that $$z_{j} \leq b_1^+,\text{ for all } s(b_1)\leq j\leq e(b_1).$$ For such indices $j$, we define $$H_l(\lambda,z)_j = (1-\lambda)z_j + \lambda b_1^-,$$ i.e. the homotopy $H_l$ creates a plateau of height $b_1^-$ in $(\mathcal{S},H_d(1,z))$.

Proceeding further, the birth and death values of the second component of the sublevel set filtration of $(\mathcal{S},z)$ are within $R_2 = [b_2^-,b_2^+)\times[d_2^-,d_2^+)$. Observe that due to assumptions it holds that $[b_2^-,b_2^+)$ is disjoint from $[d_2^-,d_2^+)$. We pick a sequence of $z$ components $\{ z_{s(b_2)},\dots, z_{e(b_2)}\}$, such that $b_2^-\leq z_j \leq b_2^+$ for all $s(b_2)\leq j\leq e(b_2)$, and the local minimum is contained within this sequence (there may be several disjoint sequences within the specified range, but only one of them contains the local extremum). For such indices, we define the homotopy $$H_l(\lambda,z)_j = (1-\lambda)z_j + \lambda b_2^-.$$ Now, we pick a sequence of $z$ components $\{ z_{s(d_2)},\dots, z_{e(d_2)}\}$, such that $d_2^-\leq z_j \leq d_2^+$ for all $s(d_2)\leq j \leq e(d_2)$, and the indices of the local maximum are contained within this sequence (there may be several disjoint sequences within the specified range, but only one of them contains the local extremum). For such indices, we define the homotopy $$H_l(\lambda,z)_j = (1-\lambda)z_j + \lambda d_2^+.$$ We define the homotopy $H_l$ analogously for each of the subsequences of indices containing indices of one of the other local extrema.

For indices $k$ that were not considered above we define $H_l$ as a constant homotopy, i.e. $$H_l([0,1],z)_k = z_k.$$

As $H_l$ creates plateaus having heights $(z_{i_1}^-, z_{i_2}^+,\dots,z_{i_n}^-)$ in place of all local extrema, it holds that $H(1,z)\in C((z_{i_1}^-, z_{i_2}^+,\dots,z_{i_n}^-))$ for $H$ defined in .

Finally, to show that the constructed homotopy $H$ is continuous with respect to the input. Let $\varepsilon>0$ be small. Let $\widetilde{z}_1, \widetilde{z}_2\in C(\operatorname{cv}({\mathsf{Dgm}}^{-1}({\mathfrak{N}}))^i)$, such that $|\widetilde{x}_1 - \widetilde{x}_2| < \varepsilon$. Observe that the homotopy $H$ is defined such that applied to $\widetilde{z}_1$ and $\widetilde{z}_2$, some of the $H(\lambda, \widetilde{z}_1)$ and $H(\lambda, \widetilde{z}_2)$ components approach the same value, or stay the same. Hence, $H$ cannot increase the distance between $H(\lambda, \widetilde{z}_1)$ and $H(\lambda, \widetilde{z}_2)$ for any $\lambda\in[0,1]$, therefore, it holds that $|H(\lambda, \widetilde{z}_1) - H(\lambda, \widetilde{z}_2)|\leq \varepsilon$ for all $\lambda\in[0,1]$.

On the existence of fixed points for flows {#secapplication}
==========================================

In this section we present an application of our preimage contractibility result presented in Section \[seccontr\] to prove the existence of a fixed point of a finite dimensional dynamical system that is being observed in the space of persistence diagrams.

Let $N\geq 3$. Consider a system of differential equations $\dot{z} = F(z)$ defined on ${\mathbb{R}}^{N}$ that generates a flow on a *compact global attractor* ${{\mathcal{A}}}\subset{\mathbb{R}}^N$ $$\Phi\colon {\mathbb{R}}\times {{\mathcal{A}}}\to {{\mathcal{A}}}.$$ Observe that at each time point $\Phi(t,z) = (\Phi_1(t,z),\ldots,\Phi_{N-1}(t,z),\Phi_{N}(t,z)) \in {{\mathcal{A}}}$, and hence we can consider ${\mathsf{Dgm}}(\Phi(t,z))\in {\mathsf{Per}}$. Thus $\Phi$ induces dynamics on ${\mathsf{Per}}$ that we define by $$\label{eqobsdyn}
\begin{aligned}
\Phi_{{\mathsf{Per}}}\colon{\mathbb{R}}\times{{\mathcal{A}}}&\to {\mathsf{Per}}\\
  (t,z) &\mapsto \Phi_{{\mathsf{Per}}}(t,z) := {\mathsf{Dgm}}\left(\Phi(t,z)\right),
\end{aligned}$$ but hasten to point out that $\Phi_{{\mathsf{Per}}}$ need not be a semiflow, let alone a flow.

Let us define the global bounds $\bar{a}, \bar{b}$ as $$\bar{a} = \sup_{z\in{{\mathcal{A}}}}{|z_1|},\qquad \bar{b} = \sup_{z\in{{\mathcal{A}}}}{|z_N|}.$$

Our main result says that if a region ${\mathfrak{N}}_\delta \subset {\mathsf{Per}}$ is positively invariant under $\Phi_{{\mathsf{Per}}}$, then the underlying flow $\Phi$ has an equilibrium point $\bar{z}$ such that ${\mathsf{Dgm}}(\bar{z})\in {\mathfrak{N}}_\delta$.

\[thmmaindyn\] Let $\Phi\colon {\mathbb{R}}\times {{\mathcal{A}}}\to {{\mathcal{A}}}$ be a flow on a compact global attractor ${{\mathcal{A}}}\subset{\mathbb{R}}^N$, and let $\Phi_{\mathsf{Per}}$ be the induced dynamics on ${\mathsf{Per}}$. Let ${\mathcal{B}}= \left\{z\in{\mathbb{R}}^N\colon z_1\in[-\bar{a},\bar{a}],\ z_N\in[-\bar{b},\bar{b}]\right\}$. Let ${\mathfrak{N}}_\delta\subset {\mathsf{Per}}$ .

Assume that for any $z\in{\mathcal{B}}$ satisfying ${\mathsf{Dgm}}( z )\in{\mathfrak{N}}_\delta$ it holds that $$\Phi_{{\mathsf{Per}}}\left([0,\infty), z\right) \subset{\mathfrak{N}}_\delta.$$

Then, there exists $\overline{z} \in{\mathcal{B}}$, such that $${\mathsf{Dgm}}(\overline{z}) \in {\mathfrak{N}}_\delta,$$ and $\overline{z}$ is a fixed point of $\Phi$.

Let us denote $$C_j := C(\operatorname{cv}({\mathsf{Dgm}}^{-1}({\mathfrak{N}}_\delta))^j).$$ From our assumption that $\Phi_{{\mathsf{Per}}}\left([0,\infty), z\right)\subset{\mathfrak{N}}_\delta$ it follows that for any vector $z$, such that $$z \in C_j$$ for some $1\leq j\leq I({\mathsf{Dgm}}^{-1}({\mathfrak{N}}_\delta))$, it holds that $$\Phi_{{\mathsf{Per}}}\left([0,\infty), z\right)\subset C_j,\text{ for all }t\in[0,\infty).$$

Without loss of generality let us fix $j$. Hence, the component $C_j$ gets mapped into itself by the semi-flow $\Phi$, i.e. $$\Phi([0,\infty),C_j) \subset C_j.$$

By Theorem \[thm:mainNdelta\] $C_j\subset{\mathcal{B}}$ is a compact simplicial set, see Remark \[remcompact\].

Now, for any $t>0$ the time-$t$ map $ \Phi_t(z) := \Phi(t,z)$ $$\Phi_t(C_j) \subset C_j,$$ and because $C_j$ is a compact contractible polytope only $0$-th homology of self map $\Phi_t$ is nontrivial, and from the Lefshetz fixed point theorem [@lefshetz1; @lefshetz2] $\Phi_t$ for any $t>0$ admits a fixed point in $C_j$.

Finally passing to the limit $t\to 0$ a fixed point of the semi-flow $\Phi$ is obtained.
