Spaces of directed paths on pre-cubical sets

In recent years, much effort was made to understand spaces of directed paths on d-spaces. Particularly interesting examples of d-spaces are geometric realizations of pre-cubical sets [3, 4], thanks to their applications in concurrency—their directed path spaces can be interpreted as the executions spaces of Higher Dimensional Automata [8]. Raussen [9] proved that such spaces, under certain conditions, have the homotopy types of CW-complexes. In this paper we construct a combinatorial model of the space of directed paths between two fixed vertices of a pre-cubical set, assuming it satisfies a certain mild condition, i.e., its non-looping length covering being proper (cf. 1.3, 1.4).

The special cases of Higher Dimensional Automata are cubical complexes which are state spaces of PV-programs, i.e., concurrent programs using Dijkstra’s semaphores [2] for synchronization. Models for the execution spaces of PV-programs were constructed in [10‐12]. It is also known that homotopy types of such spaces may be quite complicated; in fact, any finite homotopy type can be obtained as a connected component of such a space [18], and the Betti numbers of execution spaces may grow exponentially with respect to the length of a PV-program [13]. Since cubical complexes coming from PV-programs are proper, the results of this paper can be applied in this case. The model of the execution space of a PV-program constructed here has a nice (though complicated) structure of a “permutahedral complex”. This allows to use methods of combinatorial topology to understand these spaces. On the other hand, Theorem 1.4 allows to implement an algorithm which calculates the homology of the execution state of a PV-program which could be more efficient than previously known ones.

A pre-cubical set K, called also a \(\square \)-set, is a sequence of disjoints sets K[n], for \(n\ge 0\), equipped with face maps \(d^\varepsilon _i{:}\;K[n]\rightarrow K[n-1]\), for \(\varepsilon \in \{0,1\}\) and \(i\in \{1,\dots ,n\}\), that satisfy pre-cubical relations; namely, \(d^\varepsilon _i d^\eta _j=d^{\eta }_{j-1}d^\varepsilon _i\) for \(i<j\). A \(\square \)-map \(f{:}\;K\rightarrow K'\) between \(\square \)-sets is a sequence of maps \(f[n]{:}\;K[n]\rightarrow K[n']\) that commute with the face maps. Elements of K[n] will be called n-cubes of K; in particular 0-cubes will be called vertices. A bi-pointed \(\square \)-set is a triple (K, v, w), where K is a \(\square \)-set, and \(v,w\in K[0]\) are vertices in K. Let \(\square \mathbf {Set}\) and \(\square \mathbf {Set}_*^*\) denote the category of \(\square \)-sets and \(\square \)-maps and the category of bi-pointed \(\square \)-sets and \(\square \)-maps preserving the distinguished vertices, respectively.

Let us introduce a notation for arbitrary compositions of face maps. For a function \(f{:}\;\{1,\dots ,n\}\rightarrow \{0,1,*\}\) such that \(|f^{-1}(*)|=m\), define a map \(d_f{:}\;K[n]\rightarrow K[m]\) bywhere \(d_i^*\) is, by convention, the identity map; we will also write \(d_{f^{-1}(0),f^{-1}(1)}\) for \(d_f\). Finally, let \(d^0_A:=d_{A,\emptyset }, d^1_A=d_{\emptyset ,A}\) and \(d^\varepsilon =d^\varepsilon _{\{1,\dots ,n\}}{:}\;K[n]\rightarrow K[0]\). If \(f{:}\;\{1,\dots ,n\}\rightarrow \{0,1,*\}, g{:}\;\{1,\dots ,m\}\rightarrow \{0,1,*\}\) are functions such that \(|f^{-1}(*)|=m, |g^{-1}(*)|=k\), then \(d_gd_f=d_h\), whereand \(\alpha {:}\;f^{-1}(*)\rightarrow \{1,\dots ,m\}\) is the unique increasing bijection.

The results of this paper apply to finite \(\square \)-sets that have proper non-looping length coverings. We say that a \(\square \)-set K is proper, if the mapis an injection, i.e., the cubes of K can be distinguished by their extreme vertices. Every proper \(\square \)-set is non-self-linked in the sense of [3], i.e., for every \(c\in K[n]\) and \(f,g{:}\;\{1,\dots ,n\}\rightarrow \{0,1,*\}\), the equality \(d_f(c)=d_g(c)\) implies that \(f=g\). The non-looping length covering [11, 5.1] of a \(\square \)-set K is the \(\square \)-set \({\tilde{K}}\) such that \({\tilde{K}}[n] = K[n]\times \mathbb {Z}\) andClearly, if a \(\square \)-set is proper, then its non-looping length covering is also proper. Let \(\mathbf {pc}\square \mathbf {Set}_*^*\subseteq \square \mathbf {Set}_*^*\) be the full subcategory of finite bi-pointed \(\square \)-sets having proper non-looping coverings.

For a cube chain \(\mathbf {c}=(c_1,\dots ,c_l)\in {{\mathrm{Ch}}}(K)_v^w\) of type \((n_1,\dots ,n_l)\), an integer \(k\in \{1,\dots ,l\}\) and a subset \(A\subsetneq \{1,\dots , n_k\}\) having r elements, where \(0<r<n_k\), define a cube chainwhere \({\bar{A}}=\{1,\dots ,n_k\}\setminus A\). The cube chain \(\mathbf {c}\) is thus subdivided once at one of the inner vertices of \(c_k\). Let \(\le \) be the partial order on \({{\mathrm{Ch}}}(K)\) spanned by all relations having the form \(d_{k,A}(\mathbf {c})\le \mathbf {c}\). Clearly \(\dim (d_{k,A}(\mathbf {c}))=\dim (\mathbf {c})-1\); thus, the relation \(\le \) is antisymmetric.

For a \(\square \)-set K let |K| denote its geometric realization (3.1) and, for a bi-pointed \(\square \)-set (K, v, w), let \(\vec {P}(K)_v^w\) be the space of directed paths on |K| from v to w (cf. 2.1). Clearly, \((K,v,w)\mapsto {{\mathrm{Ch}}}(K)_v^w\) and \((K,v,w)\mapsto \vec {P}(K)_v^w\) are functors from \(\square \mathbf {Set}_*^*\) into the categories of posets and topological spaces, respectively.

Let \(\mathbf {hTop}\) be the homotopy category of the category of topological spaces. We prove the following

Next, we prove that the spaces \({{\mathrm{Ch}}}(K)_v^w\) have a natural CW-structure, which is coarser than the simplicial one. For a poset P and \(x\in P\), let \(P_{\le x}\) (resp. \(P_{<x}\)) be the subposet of P containing all elements that are less or equal to x (resp. less than x).

We also calculate the incidence numbers between the cells of this CW-complex. In Sect. 8 we construct, for every \(\mathbf {c}\in {{\mathrm{Ch}}}^{=n}(K)_v^w\), a cycle \(g_\mathbf {c}\) that represents a generator in the simplicial homology groupAs a consequence of Theorem 1.3, the group \(H_n(|{{\mathrm{Ch}}}^{\le n}(K)_v^w|, |{{\mathrm{Ch}}}^{<n}(K)_v^w|)\) is a free group generated by \(g_\mathbf {c}\) for \(\mathbf {c}\in {{\mathrm{Ch}}}^{=n}(K)_v^w\).

As a consequence, the homology of \(\vec {P}(K)_v^w\) can be calculated using the formula above.

We conclude with two examples. For \(K=\partial \square ^3\) (1.9), \(|{{\mathrm{Ch}}}(K)_v^w|\) is a hollow hexagon; its vertices correspond to directed paths from v to w running along vertices, i.e., cube chains of type (1, 1, 1), and its edges correspond to cube chains of types (1, 2) or (2, 1). For K being the barycentric subdivision of \(\square ^2, |{{\mathrm{Ch}}}(K)_v^w|\) is presented in (1.10).

In this section, we recall the notion of d-space and introduce complete d-spaces [5], which are necessary to define the d-structure on the geometric realization of a d-simplicial complex. For a complete exposition of this topic see for example [6].

The category of d-spaces and d-maps is complete and cocomplete. For an arbitrary family of paths \({\mathfrak {S}}\subseteq P(X)\) there exists a smallest d-structure \({\overline{\mathfrak {S}}}\) on X containing \(\mathfrak {S}\); it can be constructed as the intersection of all d-structures containing \(\mathfrak {S}\), or by adding to \(\mathfrak {S}\) all constant paths and all non-decreasing reparametrizations of concatenations of paths in \(\mathfrak {S}\).

The following d-spaces play an important role in this paper:Let us recall the definition of complete d-spaces introduced in [17] (called there “good” d-spaces).

The family of all almost directed paths \({\mathfrak {D}}_c\) on a d-space \((X,{\mathfrak {D}})\) is a d-structure on X. The d-space \((X,\mathfrak {D}_c)\) will be called the completion of \((X,\mathfrak {D})\); if a given d-space is equal to its completion, it is called complete. If \({\mathfrak {S}}\subseteq P(X)\) is an arbitrary family of paths, then its completion \({\overline{\mathfrak {S}}}_c\) is the smallest complete d-structure containing \(\mathfrak {S}\). We add a criterion which allows to verify whether a continuous map between complete d-spaces is a d-map.

For every \(n\ge 0\), the directed n-cube and the directed n-simplex are complete d-spaces. The d-structure on \(\vec {I}^n\) is generated by the family of pathsand the d-structure on \(\vec {\Delta }^n\) byIf it is clear which d-structure we consider on a given space X, we will denote it by \(\vec {P}(X)\); the elements of \(\vec {P}(X)\) will be called directed paths or d-paths. Given two points \(x,y\in X\), letbe the space of directed paths from x to y. We extend the notion of directedness for paths defined on arbitrary closed intervals; a path \([a,b]\rightarrow X\) is called directed if its linear reparametrization \([0,1]\ni t\mapsto \alpha (a+t(b-a))\in X\) is directed. The space of such paths will be denoted by \(\vec {P}_{[a,b]}(X)\).

In this section we introduce \(\square \)-sets with height function, and prove that their geometric realizations are complete d-spaces. For a more detailed discussion on \(\square \)-sets see also [3].

The geometric realization of a \(\square \)-set K is a d-spacewhere \(\delta ^\varepsilon _i(s_1,\dots ,s_{n-1})=(s_1,\dots ,s_{i-1},\varepsilon , s_i,\dots ,s_{n-1})\). A path \(\alpha \in P(|K|)\) is directed if there exist numbers \(0=t_0<t_1<\dots <t_l=1\), cubes \(c_i\in K[n_i]\) and directed paths \(\beta _i{:}\;[t_{i-1},t_i]\rightarrow \vec {I}^{n_i}\) such that \(\alpha (t)=(c_i,\beta _i(t))\) for \(t\in [t_{i-1},t_i]\). For every \(x\in |K|\) there exists a unique cube \({{\mathrm{supp}}}(x)\) of K, called the support of x, such that \(x=({{\mathrm{supp}}}(x),(t_1,\dots ,t_n))\), and \(t_i\ne 0,1\) for \(i\in \{1,\dots ,n\}\). For shortness, we will further write \(\vec {P}(K)\) instead of \(\vec {P}(|K|)\).

Not every \(\square \)-set allows a height function; see the directed circle (1.5) for example.

A height function h on K determines a d-mapwhich will also be called a height function. If \(\alpha \in \vec {P}(K)\) is a directed path, then \(l_1(\alpha )=h(\alpha (1))-h(\alpha (0))\), where \(l_1\) is the \(L_1\)-arc length of Raussen [11, 5.1]. In particular, if \(\alpha \in \vec {P}(K)\) is not constant on any interval, then \(h\circ \alpha \) is a strictly increasing function, which implies that all directed loops on a \(\square \)-set with height function are constant.

The space \(\vec {N}(K)_v^w\) can be regarded as a subspace \(\vec {P}(K)_v^w\) via the reparametrizing inclusionOn the other hand, by [9, 2.15] there exists a naturalization map which is a left inverse of (3.3). As shown in [9], these maps are mutually inverse homotopy equivalences.

We conclude this section with the following

In this section, we recall the definition of a d-simplicial complex and prove that every proper \(\square \)-set with height function has a d-simplicial triangulation.

For the rest of the section we assume that K is a proper \(\square \)-set. We will construct a triangulation of K, i.e., a d-simplicial complex \({{\mathrm{Tr}}}_K\) such that |K| and \({{\mathrm{Tr}}}_K\) are d-homeomorphic. With notation as in (1.1), letwhere \(f_j<f_k\) means that \(f_j\ne f_k\) and \(f_j(i)\le f_k(i)\) for all i. Introduce a binary relation \(\le _{{{\mathrm{Tr}}}(K)}\) on K[0] byEvery element \(A=\{d_{f_0}(c)<\dots <\dots ,d_{f_k}(c)\}, c\in K[n]\) of \(S_{{{\mathrm{Tr}}}(K)}\) can be written aswhere \(c'=d_{f_k^{-1}(0),f_0^{-1}(1)}(c)\) andis an increasing bijection. Thus, A has a unique presentation such that \(f_0\equiv 0\) and \(f_k\equiv 1\). By the properness of K, the cube c is determined by its extreme vertices \(d^0(c)=d_{f_0}(c)\) and \(d^1(c)=d_{f_k}(c)\) and, for every vertex v of c, there exists a unique f such that \(v=d_f(c)\). Such a presentation of a simplex of \({{\mathrm{Tr}}}(K)\) will be called canonical.

The d-simplicial complex \({{\mathrm{Tr}}}(K)\) will be called the triangulation of K.

Our next goal is to construct a d-homeomorphism between the geometric realization of K and the geometric realization of its triangulation. Let A be a simplex of \({{\mathrm{Tr}}}(K)\) and let \((d_{f_0}(c),\dots ,d_{f_{k}}(c)), c\in K[n]\) be its unique presentation such that \(f_0\equiv 0, f_k\equiv 1\). Define a continuous mapwhere functions \(f{:}\;\{1,\dots ,n\}\rightarrow [0,1]\) are regarded as points \((f(1),\dots ,f(n))\in \vec {I}^n\).

As a consequence, the maps \(F_A\) glue to a continuous map \(F_K{:}\;|{{\mathrm{Tr}}}(K)|\rightarrow |K|\).

We conclude with some obvious properties of the triangulation.

Recall [16] that a d-simplicial complex M has no loops if for every sequence of vertices \(v_0\le \dots \le v_n\le v_0\) in M we have \(v_0=\dots =v_n\). We say that a \(\square \)-set K has no loops if, for every vertex \(v\in K[0]\), every cube chain from v to v is empty. If K admits a height function, then, clearly, it has no loops. Immediately from the construction follows that the triangulation of a proper \(\square \)-set having no loops also has no loops. In this section we prove that the space of directed paths between two arbitrary vertices of a proper \(\square \)-set having no loops is homotopy equivalent to its subspace containing only tame paths, i.e. paths that cross from one cube to another at vertices only. It is a consequence of the results from [16] for d-simplicial complexes.

The tameness of paths on \(\square \)-sets is defined quite similarly:

For the remaining part of this section we assume that K is a proper \(\square \)-set with height function.

The main result of this section is the following

Let K be a finite proper \(\square \)-set with height function and let \(v,w\in K[0]\). Let(cf. 3.4) denote the space of natural tame paths; thanks to Theorem 5.6 and [9, 2.16] the spaces \(\vec {N}_t(K)_v^w, \vec {N}(K)_v^w, \vec {P}_t(K)_v^w\) and \(\vec {P}(K)_v^w\) are all homotopy equivalent via normalization maps and inclusions. In this section we construct a good closed cover of \(\vec {N}_t(K)_v^w\) indexed with the poset of cube chains from v to w.

Recall that a cube chain from v to w is a sequence of cubes \(\mathbf {c}=(c_1,\dots ,c_l)\) such that \(d^0(c_1)=v, d^1(c_l)=w\) and \(d^1(c_i)=d^0(c_{i-1})\) for \(1\le i<l\). Recall also thatfor \(k\in \{1,\dots ,l\}, A\cap {\bar{A}}=\emptyset , A\cup {\bar{A}}=\{1,\dots ,\dim (c_k)\}\) and that \(\le \) is the transitive-reflexive closure of relations \(d_{k,A}(\mathbf {c})\le \mathbf {c}\) on \({{\mathrm{Ch}}}(K)_v^w\). For a cube chain \(\mathbf {c}=(c_1,\dots ,c_l)\) we will write \(l^{\mathbf {c}}=l, n^\mathbf {c}_i=\dim (c_i), v^\mathbf {c}_i=d^0(c_{i+1})=d^1(c_i)\) and \(b^\mathbf {c}_k=n^\mathbf {c}_1+\dots +n^\mathbf {c}_k, k\in \{1\dots l\}\). The upper index \(\mathbf {c}\) will be omitted if it does not lead to confusion.

Note that \(\alpha (b^\mathbf {c}_i)=v^\mathbf {c}_i\) for \(\alpha \in \vec {N}(K,\mathbf {c}), i\in \{0,\dots ,l^\mathbf {c}\}\).

For \(v,w,z\in K[0]\) and cube chains \(\mathbf {c}=(c_1,\dots ,c_l)\in {{\mathrm{Ch}}}(K)_v^w, \mathbf {c}'=(c'_1,\dots ,c'_{l'})\in {{\mathrm{Ch}}}(K)_w^z\) we define the concatenation \(\mathbf {c}*\mathbf {c}'\in {{\mathrm{Ch}}}(K)_v^z\) of \(\mathbf {c}\) and \(\mathbf {c}'\) byThe concatenation of paths induces a homeomorphism

This allows us to prove Theorem 1.2 in the following special case. Let \(\mathbf {fph}\square \mathbf {Set}_*^*\) be the category of finite proper \(\square \)-sets with height function and \(\square \)-maps that preserve height functions. For \((K,v,w)\in \mathbf {fph}\square \mathbf {Set}_*^*\) let \(\varepsilon _{(K,v,w)}\) be the compositionAll the maps in the sequence and homotopy equivalences. This follows from Theorem 5.6 for the left-most inclusion, [9, 2.16] for the nat map, and from [14, 4.1] and Proposition 6.2 for the remaining two maps. This implies that \(\varepsilon _{(K,v,w)}\) is well-defined up to homotopy, and it is a homotopy equivalence. Furthermore, all the maps are functorial with respect to (K, v, w). As a consequence, we obtain the following.

The proof of Theorem 1.2 in full generality is postponed to Sect. 9.

In this section we study the posets of faces of products of permutohedra (see [15, p.18]), which play an important role in the description of the posets of cube chains on \(\square \)-sets. There are (at least) three ways to describe the face poset of the \((n-1)\)-dimensional permutahedron:The first description is most common and, probably, more intuitive than the others. We will pass freely between these three approaches; however, we will mainly use surjective functions since they allow more rigorous arguments.

Clearly, the function f is determined uniquely. The poset \(O_n\) has a greatest element: the constant function with value 1, which will be denoted by \(f_n\). Let

Next, we will identify the product \(O_{n_1}\times \dots \times O_{n_l}\) with the sub-poset of \(O_n, n=\sum _k n_k\), consisting of those weak strict orderings \(\sqsubseteq \) of \(\{1,\dots ,n\}\) which satisfywhere \(i \sqsubset i'\) means that \(i\sqsubseteq i'\) and not \(i'\sqsubseteq i\).

Let \({{\mathrm{Seq}}}(n)\) be the set of all sequences of positive integers \(\mathbf {n}=(n_1,\dots ,n_{l(\mathbf {n})})\) such that \(n=n_1+\dots +n_{l(\mathbf {n})}\). For a given partition \(\mathbf {n}\in {{\mathrm{Seq}}}(n)\), letNotice that \(O_{(n)}=O_n\). Whenever it does not lead to confusion, we will write l or \(b_k\) instead of \(l(\mathbf {n})\) or \(b_k(\mathbf {n})\).

Fix \(\mathbf {n}\in {{\mathrm{Seq}}}(n)\). For every \(f\in O_{\mathbf {n}}\), there exists a non-decreasing function \(h{:}\;\{1,\dots ,k(f)\}\rightarrow \{1,\dots ,l\}\) such that \(h\circ f=f_\mathbf {n}\). Thus, for \(k\in \{1,\dots ,l\}, f\) determines a functionwhich is an element of \(O_{n_k}\). On the other hand, a sequencefor \(k\in \{1,\dots ,l\}\), determines an element \(f\in O_\mathbf {n}\) such thatThese constructions give an isomorphism of posets \(O_{\mathbf {n}} \cong O_{n_1}\times \dots \times O_{n_l}\). Thus, \(O_\mathbf {n}\) is isomorphic to the face lattice of the product of permutahedra of dimensions \(n_1-1,\dots ,n_k-1\) respectively; as a consequence, there is a homeomorphismwhere \(\partial O_{\mathbf {n}}:=O_{\mathbf {n}}\setminus \{f_\mathbf {n}\}\), which generalizes Proposition 7.2.

The main goal of this section is to construct a fundamental class of the pair (7.5) in simplicial homology [7, p. 104]; to achieve this, we need to introduce a notation for the simplices of the nerve \(\mathcal {N}O_{n}\) of \(O_n\). Before passing to formal definitions, let us present a general idea of this notation.

LetFor \(\mathbf {n}\in {{\mathrm{Seq}}}(n)\) define \(\tau _\mathbf {n}\in T^0_n\) by \(\tau _\mathbf {n}(i)=f_\mathbf {n}(i+1)-f_\mathbf {n}(i)\), and for \(\tau \in T^0_n\) define \(f^\tau \in O_n\) byClearly, \(f^{\tau _\mathbf {n}}=f_\mathbf {n}\), and this defines a bijection between \(T^0_n\) and \({{\mathrm{Seq}}}(n)\). For \(\tau \in T^d_n\) letLet us enlist some properties of the functions \(f^\tau \):

Let us introduce the following maps between integers:furthermore, for \(r\le s\) denote \(\mathsf {t}_r^s=\mathsf {t}_r\mathsf {t}_{r+1}\dots \mathsf {t}_{s-1}\); it is easy to check that \(\mathsf {t}_r^s(i)=i\) for \(i<r\) or \(i>s, \mathsf {t}_r^s(s)=r\), and \(\mathsf {t}_r^s(i)=i+1\) for \(r\le i<s\).

Every element \(\tau \in T^d_n\) determines a sequence \((\mathsf {p}_0\circ \tau , \dots , \mathsf {p}_d\circ \tau )\) of \(d+1\) elements of \(T^0_n\). Thus, for \(\sigma \in \Sigma _{n}\) and \(\tau \in T^d_{n}\), we can define a d-simplex in \(O_{n}\):Notice that Proposition 7.4(b) implies that \(f^{\mathsf {p}_0\tau }\sigma \preceq f^{\mathsf {p}_1\tau }\sigma \preceq \dots \preceq f^{\mathsf {p}_d\tau }\sigma \). This definition coincides with Example 7.3

For \(\mathbf {n}\in {{\mathrm{Seq}}}(n)\) define Notice that \(T^0_\mathbf {n}=\{\tau \in T^0_n{:}\; f^\tau \preceq f_\mathbf {n}\}\), and \(T^d_{\mathbf {n}}=\{\tau \in T^d_n{:}\; \mathsf {p}_{d}\tau \in T^0_\mathbf {n}\}\).

The next step is to construct a generator of the top homology class of the pair \((\mathcal {N}O_\mathbf {n}, \mathcal {N}\partial O_\mathbf {n})\). It is clear that this a combination of all simplices of \(\mathcal {N}O_\mathbf {n}\) having the maximal dimension; the difficult part is to choose \(\pm 1\) coefficients at these simplices. For \(\sigma \in \Sigma _n\) let \({{\mathrm{sgn}}}(\sigma )\in \{\pm 1\}\) be the sign of the permutation \(\sigma \). For \(\mathbf {n}\in {{\mathrm{Seq}}}(n)\) and \(\tau \in T^{n-l}_\mathbf {n}\), the image of \(\tau \) contains \(\{1,\dots ,n-l\}\), and \(\tau (b_j)=n-l\) for \(j=1,\dots ,l-1\). Then the restrictionis a bijection. Let \(\varrho _{\mathbf {n}}{:}\; \{1,\dots ,n-l\} \rightarrow \{1,\dots ,n-1\}\setminus \{b_1,\dots ,b_{l-1}\}\) be the (unique) increasing bijection. The composition \(\tau \varrho _\mathbf {n}\) is a permutation on \(n-l\) letters, and we define the sign of \(\tau \in T^{n-l}_{\mathbf {n}}\) asDefine a chain \(g_\mathbf {n}\in C_{n-l}(\mathcal {N}O_\mathbf {n})\) byWe will show that \(g_\mathbf {n}\) represents a fundamental class in \(H_{n-l}(|O_\mathbf {n}|,|\partial O_\mathbf {n}|)\) (cf. 7.5).

Let \(\mathbf {n}\in {{\mathrm{Seq}}}(n)\). For \(k\in \{1,\dots ,l\}, r\in \{1,\dots ,n_k-1\}\) denote

Fix \(\mathbf {n}\in {{\mathrm{Seq}}}(n)\). For \(k\in \{1,\dots ,l\}, r\in \{1,\dots ,n_k-1\}\), let

For \(A\in S_\mathbf {n}(k,r)\), let \(\xi _{k,A}\in \Sigma _\mathbf {n}\) be the permutation determined by the following conditions:

Every permutation \(\xi \in \Sigma _\mathbf {n}\) induces an automorphism \(\sigma ^*{:}\;O_\mathbf {n}\rightarrow O_\mathbf {n}\) by the formula \(\sigma ^*(f)=f\sigma \); note that \(\xi _* a[\sigma ,\tau ]=a[\sigma \xi ,\tau ]\). Define an inclusion \(\iota _{k,A}\) as the composition \(O_{\mathbf {n}[k,r]}\subseteq O_\mathbf {n}\xrightarrow {(\xi _{k,A})^*}O_\mathbf {n}\).

Throughout the whole section, K is a finite proper \(\square \)-set with height function h, and \(v, w\in K[0]\) are two vertices such that \(h(v)=0, h(w)=n\). For \(s\in \mathbb {Z}\), define a function

For \(v,w\in K[0]\) and \(\mathbf {c}=(c_1,\dots ,c_l)\in {{\mathrm{Ch}}}(K)_v^w\), define a mapwhere \(f^i\) are defined as in (7.3).

Let \({{\mathrm{Ch}}}^{\le n}(K)_v^w\subseteq {{\mathrm{Ch}}}(K)_v^w\) be the subset of cube chains having dimension less of equal n; clearly \(|{{\mathrm{Ch}}}^{\le n}(K)_v^w|\) is the n-skeleton of \(|{{\mathrm{Ch}}}(K)_v^w|\). For a chain \(\mathbf {c}\in {{\mathrm{Ch}}}(K)_v^w\) of type \(\mathbf {n}\) and dimension n letThe group \(H_n(|{{\mathrm{Ch}}}^{\le n}(K)_v^w|, |{{\mathrm{Ch}}}^{\le n-1}(K)_v^w|)\) is a free \(\mathbb {Z}\)-module generated by (simplicial, homological) chains \(g_\mathbf {c}\) for \(\mathbf {c}\in {{\mathrm{Ch}}}^{=n}(K)_v^w\).

In this section we generalize the results obtained for finite proper \(\square \)-sets with height function to a larger class of \(\square \)-sets that have proper non-looping length coverings. Recall that \(\mathbf {pc}\square \mathbf {Set}_*^*\) is the category of finite bi-pointed \(\square \)-sets having proper non-looping coverings.

For \(K\in \mathbf {pc}\square \mathbf {Set}_*^*\) and \(n\ge 0\) define a \(\square \)-subset \({\tilde{K}}_n\subseteq {\tilde{K}}\) by \({\tilde{K}}_n[d]=K[d]\times \{0,\dots ,n-d\}\) (cf. 1.4). For every n, the formula \((K,v,w)\mapsto ({\tilde{K}}_n,(v,0),(w,n))\) defines a functor from \(\mathbf {pc}\square \mathbf {Set}_*^*\) to \(\mathbf {fph}\square \mathbf {Set}_*^*\).

Let \(p{:}\;{\tilde{K}}\ni (c,k)\mapsto c\in K\) denote the obvious projection, and let \(p_n=p|_{{\tilde{K}}_n}\).

This criterion shows that, when proving Theorem 1.2, we can restrict to the case when K if a finite proper \(\square \)-set with height function.