Georgian Mathematical Journal Volume 10 (2003), Number 1, 77–98

COMBINATORIAL HOMOLOGY IN A PERSPECTIVE OF IMAGE ANALYSIS

MARCO GRANDIS

Dedicated to Professor Hvedri Inassaridze, on the occasion of his seventieth birthday

Abstract. This is the sequel of a paper where we introduced an intrinsic homotopy theory and homotopy groups for simplicial complexes. We study here the relations of this homotopy theory with the well-known homology theory of simplicial complexes. Also, our investigation is aimed at applications in image analysis. A metric space X, representing an image, has a structure of simplicial complex at each resolution ε > 0, and the corresponding combinatorial homology groups H_{n}^{ε}(X) give information on the image. Combining the methods developed here with programs for automatic computation of combinatorial homology might open the way to realistic applications.

2000 Mathematics Subject Classification: 55N99, 68U10, 55U10, 54G99. Key words and phrases: Homology groups, image processing, simplicial complex, digital topology, mathematical morphology.

Introduction

This paper is devoted to the homology of simplicial complexes, its connections with the intrinsic homotopy theory developed in a previous work ([7], cited as Part I) and some methods of direct computation of combinatorial homology. As in Part I, the applications are aimed at image analysis in metric spaces, and connected with digital topology and mathematical morphology. In fact, a metric space X has a structure t_{ε}X of simplicial complex at each resolution ε > 0, and the corresponding homotopy and homology groups π_{n}^{ε}(X), H_{n}^{ε}(X) detecting singularities which can be captured by an n-dimensional grid, with edges bound by ε; this works equally well for continuous regions of R^{n} or discrete ones; in the latter case, our results are closely related with analyses of 0- or 1connection in “digital topology” (cf. [11, 12, 2]). Such methods, combined with the use of recent computer programs for the homology of simplicial complexes, should be of use in the analysis of complicated 2- or 3-dimensional images, as produced by scanning a geographical region or an object; this work is under progress, and it would be difficult to say now whether it will produce results of practical interest: “realistic images” tend to produce big simplicial complexes, on which the existing programs for computing homology do not terminate in a reasonable time; but algorithms can be developed to reduce the size of the simplicial complex without changing its homology.

ISSN 1072-947X / $8.00 / \begin{matrix}c \\ ◯ \end{matrix} Heldermann Verlag www.heldermann.de

To give a first idea of these applications, in an elementary case, consider the subset X ⊂ R^{2} of Fig. (a), representing a planar image we want to analyse, for instance the map of a region

X 1  5  8 9 1 4  ^{• • • • • • • • • • •} ^{• • • • • • • • • • •} ^{• • • • • • • • • • •} ^{• • • • • •} ^{• • • • • •} ^{• • • • • •} ^{• • • • • •} ^{• • • • • •} ^{• • • • • •} ^{• • • • • •} ^{• • • • • • • • • • •} ^{• • • • • • • • • • •} ^{• • • • • • • • • • •} ^{• • • • • • • • • • •} ^{• • • • • • • • • • •} ^{• • • • • • • • • • •} ^{• • • • • • • • • • •} ^{• • • • • • • • • •} ^{• • • • • • • • • • •} ^{• • • • • • • • • • •} ^{• • • • • • • • • • •} X′ 1  5  8 9 1 4 Fig. (a)  Fig. (b)

Viewing X as a topological space, we keep some relevant information which can be detected by the usual tools of algebraic topology; e. g. the fact that X is path-connected, with two “holes”. However, we miss all metric information and are not able to distinguish a lake from a puddle. Further, if this “continuous” subspace X is replaced by a discrete trace X′ = X ∩ (ρZ × ρZ) scanned at resolution ρ = 1/2, as in Fig. (b), we miss any topological information: X′ is a discrete space.

It is more useful to view X and X′ as metric spaces (we shall generally use the l_{∞}-metric of the plane, d(x, y) = max(|x_{1}−y_{1}|, |x_{2}−y_{2}|), essentially because this is the metric of the categorical product R × R, cf. 1.2), and explore them at a variable resolution ε (0 ⩽ ε ⩽ ∞). This will mean to associate to any metric space X a simplicial complex t_{ε}X at resolution ε, whose distinguished parts are the finite subsets ξ ⊂ X with diam(ξ)⩽ ε, and study this complex by combinatorial homology.

Thus, the homology group H_{1}^{ε}(X) = H_{1}(t_{ε}X) of the metric space X, at resolution ε, allows us to distinguish, in Fig. (a): two basins at fine resolution (0 < ε < 1); then, one basin for 1 ⩽ ε < 3; and finally no relevant basin at coarse resolution (ε ⩾ 3). The finite model X′ gives the same results, as soon as ε ⩾ ρ; of course, if ε < ρ, i. e. if the resolution of the analysis is finer than the scanner’s, we have a totally disconnected object, in accord with a general principle: a “very fine” analysis resolution is too affected by the plotting procedure or by errors, and unreliable. Rather, the whole analysis is of interest, and can be expressed – as above – by some critical values (detecting metric characters of the image) together with the value of our invariant within the intervals they produce.

One can note that Shape Theory has also been proposed as a theoretical support for pattern recognition and perception. Geometric shape theory introduced by Borsuk [1] and then developed in various versions (e. g. Mardešić–Segal [13]), aims at approaching a (compact) metric or topological space by polyhedra, and defines its shape as a weak homotopy type detected by such approximations; one can find a description and comparison of various such theories in Cordier– Porter’s text [3]. In this sense, our proposal is quite different: the metric space in Fig. (b) is already a compact polyhedron, and of course we do not want to view it in this trivial form, as a collection of points. However, the categorical setting in [3] is much more general, and our methods might perhaps be presented in some form of that type.

Now, for a general overview of the present approach, let us recall that a simplicial complex, also called here a combinatorial space, is a set X equipped with a family of distinguished finite subsets, the linked parts, so that every subset of a linked part is linked and so are all singletons. Part I introduced intrinsic homotopies and homotopy groups for simplicial complexes, based on the standard (integral) line Z (1.3), the set of integers with linked parts contained in contiguous pairs {i, i + 1}. A path in the simplicial complex X is precisely a map a : Z → X which is eventually constant on the left and the right. The set of paths P X inherits the simplicial structure from the homobject X^{Z} = Hom(Z, X) (the category of simplicial complexes being cartesian closed). Then, combinatorial homotopies are defined as maps α : X → P Y; this is more general than the classical contiguity relation (based on simplicial maps a : {0, 1} → X), in an effective way: for instance, the integral line is contractible with respect to the present notion, while it is not so with respect to the equivalence relation spanned by contiguity (2.3).

Homology of simplicial complexes is a well known tool, intrinsically defined via oriented or ordered simplicial chains ([17], Ch. 4; [10], Ch. 2). Here, in Section 1, we prefer to use cubical chains, generated by the cubical set T_{∗}X = (T_{n}X)_{n≥0} of links, the maps a : 2^{n} → X defined over a power of the elementary integral interval 2 (the object on two linked points, 0 and 1). Section 2 deals with the interaction with combinatorial homotopies; the present homotopical invariance theorem for homology (2.4) is stronger than the classical one, in as much as our homotopy relation is wider. For metric spaces, the derived metric combinatorial homology H_{n}^{ε}(X) = H_{n}(t_{ε}X) satisfies, at a fixed resolution, the axioms of Eilenberg–Steenrod in an adapted form depending on ε (2.6); it might be interesting to compare such groups with the Vietoris construction for compact metric spaces [18].

In Section 3, we consider various “comparisons”: the combinatorial Hurewicz homomorphism, from homotopy to homology of simplicial complexes (3.1); the well-known canonical isomorphism from combinatorial homology to singular homology of the geometric realisation (3.2); and, in a particular case and up to degree 1, a canonical isomorphism from combinatorial homology to the singular homology of the open-spot dilation (3.4–5); the latter is a particular “dilation operator” considered in mathematical morphology (cf. [8]).

In Section 4, direct computations of combinatorial homology groups are given, using the Mayer–Vietoris sequence (1.6) and telescopic homotopies, a tool introduced in Part I to reduce combinatorial subspaces of t_{ε}R^{n} to simpler ones (cf. 2.3). In particular, the examples of 4.3–4 should be sufficient to show how the study of the combinatorial homology groups H_{n}^{ε}(X) of a metric subspace of R^{2} or R^{3}, at variable resolution, can be used for image analysis. Of course, the planar cases examined here can also be analysed via the fundamental group, as in Part I; but, for 3-dimensional spaces (or complicated planar cases), homology groups are far easier to compute. It is also relevant to note that the geometric realisation of these spaces is huge and of little help (cf. I.1.9). Finally, critical values for the family H_{n}^{ε}(X) are briefly considered (4.4-5).

Notation. We use the same notation as in Part I. A homotopy α between the maps f, g : X → Y is written as α : f → g : X → Y. The usual bracket notation for intervals refers to the real or integral line, according to context. The letter κ denotes an element of 2 = {0, 1} or S^{0} = {−1, 1}, according to convenience; it is always written −, + in superscripts. The reference I.m, or I.m.n, or I.m.n.p, applies to Part I, and precisely to its section m, or subsection m.n, or formula (p) in the latter.

1. On the Homology of Simplicial Complexes

After recalling the basic properties of simplicial complexes, we review their homology; this is constructed by means of cubical chains, based on the elementary integral interval 2 = {0, 1}.

1.1. Simplicial complexes. A simplicial complex, also called here a combinatorial space (c-space for short), is a set X equipped with a set !X ⊂ 𝒫_{f}X of finite subsets of X, called linked parts, which contains the empty subset, contains all singletons and is down closed: if ξ is linked, any ξ′ ⊂ ξ is so. A morphism of simplicial complexes, or map, or combinatorial mapping f : X → Y is a mapping between the underlying sets which preserves the linked sets: if ξ is linked in X, then f(ξ) is linked in Y. (Note that linked parts, here, are meant to express a notion of “proximity”, possibly derived from a metric; we shall generally avoid their usual name of simplices, as associated with a geometric realisation which is often inadequate for the present applications.)

As easily seen, the category Cs of combinatorial spaces is complete, cocomplete and cartesian closed (I.1). The linked parts of a cartesian product X_{1} × X_{2} are the subsets of all products ξ_{1} × ξ_{2} of linked parts; the exponential Hom(A, Y) = Y^{A}, characterised by the exponential law Cs(X × A, Y) = Cs(X, Y^{A}), is given by the set of maps Cs(A, Y) equipped with the structure where a finite subset φ of maps A → Y is linked whenever, for all ξ linked in A, φ(ξ) = ⋃_{f∈φ} f(ξ) is linked in Y.

The forgetful functor | − | : Cs → Set has left adjoint D and right adjoint C: the discrete structure DS is the finest (i. e., smallest) on the set S (only the empty subset and the singletons are linked), while the chaotic or codiscrete structure CS is the coarsest (all finite parts are linked). Also D has a left adjoint, the functor

π_{0} : Cs → Set,  π_{0}(X) = |X|/ ∼,  (1)

produced by the equivalence relation ∼ spanned by {x, y} ∈!X. A non-empty c-space X is said to be connected (or path-connected) if π_{0}X is a point; π_{0} is called the functor of connected components (or path-components). Any object is the sum of its connected components.

A subobject X′ ≺ X is a subset equipped with a combinatorial structure making the inclusion i : X′ → X a map; equivalently, !X′ ⊂!X (this is the usual notion of simplicial subcomplex [17]). The subobjects of X form a complete lattice: ⋂ X_{i} (resp. ⋃ X_{i}) is the intersection (resp. union) of the underlying subsets, with structure ⋂!X_{i} (resp. ⋃!X_{i}). More particularly, a (combinatorial) subspace, or regular subobject X′ ⊂ X, is a subobject with the induced structure: a part of X′ is linked iff it is so in X (the initial structure for i : X′ → X, i. e. the coarsest one making i a map); any intersection or union of subspaces is a subspace. An equivalence relation R in X produces a quotient X/R, equipped with the finest structure making the projection X → X/R a map: a subset of the quotient is linked iff it is the image of some linked part of X.

The category Cs^{∗} of pointed combinatorial spaces is also complete and cocomplete.

1.2. Tolerance sets and metric spaces. Tol denotes the category of tolerance sets, equipped with a reflexive and symmetric relation x!x′; the maps preserve such relations. Equivalently, one can consider a simple reflexive unoriented graph (as more used in combinatorics), or an adjacency relation, symmetric and anti-reflexive (as used in digital topology, cf. [11, 12]). The forgetful functor t : Cs → Tol takes the c-space X to the tolerance set over |X|, with x!y iff {x, y} ∈!X; it has a left adjoint d and a right adjoint c : Tol → Cs. We are more interested in the latter: for a tolerance set A, cA is the coarsest combinatorial space over A inducing the relation ! (a finite subset is linked iff all its pairs are !-related); we shall always identify a tolerance set A with the combinatorial space cA. Thus, Tol becomes a full reflective subcategory of Cs, consisting of those c-spaces where a finite subset is linked iff all its parts of two elements are so. The embedding c preserves all limits and is closed under subobjects; in particular, a product of tolerance sets, in Cs, is a tolerance set.

A metric space X has a family of canonical combinatorial structures t_{ε}X, at resolution ε ∈ [0, ∞], where a finite subset ξ is linked iff its diameter is ⩽ ε. Each of them is a tolerance set, defined by x!x′ iff d(x, x′) ⩽ ε. The category Mtr of metric spaces and weak contractions has thus a family of forgetful functors t_{ε} : Mtr → Cs, trivial for ε = 0 (giving the discrete structure) and ε = ∞ (the chaotic one). Marginally, and for ε > 0, we also consider the “open” tolerance structure t_{ε}^{−}X defined by d(x, x′) < ε; but the family t_{ε}X yields finer results (cf. 3.4).

Unless otherwise stated, the real line R has the standard metric and the combinatorial structure t_{1}R, with x!x′ iff |x − x′| ⩽ 1. Beware of the fact that, in Mtr, a product has the l_{∞}-metric, given by the least upper bound d(x, y) = sup_{i} d_{i}(x_{i}, y_{i}); this precise metric has to be used if we want to “assess” a map into a product by its components: a mapping f : Z → ∏ X_{i} is a weak contraction if and only if all its components f_{i} are so. Unless differently stated, the real n-space R^{n} will be endowed with the l_{∞}-metric max_{i} |x_{i} − y_{i}| and the derived structure t_{1}R^{n}: its linked parts are the finite subsets of all elementary real cubes ∏_{i}[x_{i}, x_{i} + 1].

1.3. Combinatorial line and spheres. The set of integers Z, equipped with the combinatorial structure of contiguity, generated by all contiguous pairs {i, i + 1}, is called the standard (integral) line and plays a crucial role in our homotopy theory. It is a combinatorial subspace of R and a tolerance set, with i!j whenever i, j are equal or contiguous; all its powers and subobjects of powers are tolerance sets. An integral interval has the induced structure, unless otherwise stated.

The structure of the standard (integral) n-space Z^{n} ⊂ R^{n} is generated by the “elementary cubes” ∏_{k} {i_{k}, i_{k} + 1}. As a crucial fact, the join and meet operations ∨, ∧ : Z^{2} → Z are combinatorial mappings (while sum and product are not), as well as − : Z → Z; thus, Z is an involutive lattice in Cs. The standard elementary interval 2 = [0, 1] ∈ Z is the chaotic c-space on two points, C {0, 1}. The standard elementary cube 2^{n} ⊂ Z^{n} is also chaotic, as well as the standard elementary simplex e^{n} = C {e_{0}, …, e_{n}} ⊂ Z^{n+1}, consisting of the n+1 unit points of the axes (the canonical basis).

The discrete S^{0} = {−1, 1} ⊂ Z is the standard 0-sphere (pointed at 1, when viewed in Cs^{∗}). There is no standard circle (I.6.6). But, for every integer k ≥ 3, there is a k-point circle, the quotient C_{k} = Z/ ≡_{k}= {[0], [1], …, [k − 1]}, with respect to congruence modulo k; the structure is generated by the contiguous pairs {[i], [i + 1]}; the base point is [0]; the homology groups are the ones of the circle (4.1; while the c-spaces similarly obtained for k = 1, 2 are chaotic, hence contractible). Such circles are not homotopically equivalent, but related by the following maps, identifying two points

p_{k} : C_{k+1} → C_{k},  p_{k}([i]) = [i] (i = 0, …, k),  (1)

which are weak homotopy equivalences.

More generally, there is no standard n-sphere for n > 0. The simplicial (or tetrahedral) n-sphere ΔS^{n} ≺ Z^{n+2} has the same n + 2 points of e^{n+1} = C(e_{0}, …, e_{n+1}) ⊂ Z^{n+2}, but a subset is linked iff it is not total; the base point is e_{0}. The cubical n-sphere □S^{n} ≺ Z^{n+1} has the same 2^{n+1} points of the cube 2^{n+1} = C {0, 1}^{n+1} ⊂ Z^{n+1}, but the linked parts are the sets of vertices contained in some face of the cube, i.e. in some hyperplane t_{i} = 0 or t_{i} = 1; the base point is 0. The octahedral n-sphere ⋄S^{n} = {±e_{0}, …, ±e_{n}} ⊂ Z^{n+1} has 2n + 2 points and the subspace structure: a subset is linked iff it does not contain opposed pairs ±e_{i}; the base point is e_{0}. Thus, ΔS^{0} ≅ □S^{0} ≅ ⋄S^{0} = S^{0}, ΔS^{1} ≅ C_{3}, □S^{1} ≅ ⋄S^{1} ≅ C_{4}. All these will be seen to be homological n-spheres (4.2).

Works in digital topology have considered various tolerance structures on Z^{n}; among the most used ones are the product structure, induced by the l_{∞}-metric (called 8-adjacency for Z^{2}, because any point is linked to 8 others), and the structure t_{1}(Z^{n}, d_{1}) induced by the l_{1}-metric Σ_{i}|x_{i} − y_{i}| (called 4-adjacency for Z^{2}); the fundamental group of regions of the latter has been considered in I.7.4.

1.4. Links. The elementary interval 2 = [0, 1] = C(0, 1) is an involutive lattice (with minimum and maximum); its structure is formalised by the following maps in Cs: faces (∂^{−}, ∂^{+}), degeneracy (e), connections (g^{−}, g^{+}) and symmetries (the reversion r and the interchange s)

{∗} ∂^{κ} 2 e  2^{2} g^{κ}  r : 2 → 2,  s : 2^{2} → 2^{2},  (1)
∂^{−}(∗) = 0, ∂^{+}(∗) = 1, g^{−}(i, j) = max(i, j) = i ∨ j,
g^{+}(i, j) = min(i, j) = i ∧ j, r(i) = 1 − i, s(i, j) = (j, i).

As a consequence, the endofunctor of 1-links or elementary paths or immediate paths in X

T (X) = X^{2} = {(x, x′) | x!x′ ∈ X}, (x, x′)!(y, y′) ⇔ {x, x′, y, y′} ∈!X, (2)

has natural transformations denoted by the same symbols and names

1 e T ∂^{κ}  g^{κ} T^{2}  r : T → T,  s : T^{2} → T^{2},  (3)

which satisfy the axioms of a cubical comonad with symmetries ([5, 6]; or I.2.4). By cartesian closedness, the power T^{n}(X) = X^{2^{n}} is the functor of n-links, or elementary n-paths a: 2^{n} → X (n ≥ 0). Globally, such functors form a cubical object with symmetries T_{∗}(X) (i = 1, …, n; κ ∈ 2)

T^{n}(X) = X^{2^{n}},  (4)
∂_{i}^{κ} = T^{n−i}∂^{κ}T^{i−1} : T^{n} → T^{n−1},
∂_{i}^{κ}(a)(t_{1}, …, t_{n−1}) = a(t_{1}, …, κ, …, t_{n−1}),
e_{i} = T^{n−i}eT^{i−1} : T^{n−1} → T^{n},
e_{i}(a)(t_{1}, …, t_{n}) = a(t_{1}, …, t̂_{i}, …, t_{n}),
g_{i}^{κ} = T^{n−i}g^{κ}T^{i−1} : T^{n} → T^{n+1},
g_{i}^{κ}(a)(t_{1}, …, t_{n+1}) = a(t_{1}, …, g^{κ}(t_{i}, t_{i+1}), …, t_{n+1}),
r_{i} = T^{n−i}rT^{i−1} : T^{n} → T^{n},
r_{i}(a)(t_{1}, …, t_{n}) = a(t_{1}, …, 1 − t_{i}, …, t_{n}),
s_{i} = T^{n−i}sT^{i−1} : T^{n+1} → T^{n+1},
s_{i}(a)(t_{1}, …, t_{n+1}) = a(t_{1}, …, t_{i+1}, t_{i}, …, t_{n+1}).

T_{∗}(X) is a subobject of the cubical set with symmetries S_{n}|X| = |X|^{2^{n}} similarly obtained in Set, the cubical set of (elementary) cubes of the set |X|: the latter coincides with T_{∗}(C|X|). Globally, we have a functor T_{∗} with values in the category of cubical sets with symmetries.

1.5. Cubical combinatorial homology. Every cubical set A determines a collection D_{n}(A) = ∪_{i}Im(e_{i} : A_{n−1} → A_{n}) of subsets of degenerate elements (with D_{0}A = ∅), yielding the normalised chain complex N : Cub → C_{∗}Ab

N_{n}(A) = F (A_{n})/F (D_{n}A) = F (A_{n} \ D_{n}A), ∂_{n}â = Σ_{i,κ}(−1)^{i+κ}(∂_{i}^{κ}a)ˆ , (1)

where a ∈ A_{n} and â denotes its class in the quotient.

The cubical chain complex of the simplicial complex X is the normalised chain complex C_{∗}X = NT_{∗}X, whose elements are the (normalised) cubical chains of X

Σ_{i}λ_{i}â_{i} ∈ C_{n}(X) = F (T^{n}X)/F (D_{n}T_{∗}X) (λ_{i} ∈ Z, a_{i} : 2^{n} → X); (2)

we shall often write the normalised class â as a, identifying all degenerate links to 0. We have thus the homology of a combinatorial space

H_{n} : Cs → Ab,  H_{n}(X) = H_{n}(C_{∗}X) = H_{n}(NT_{∗}(X)) (n ⩾ 0). (3)

Relative homology is defined in the usual way. A combinatorial pair (X, A) consists of a subobject A ≺ X (1.1): the subset A has a combinatorial structure finer than the restricted one so that the inclusion i : A → X is a map. We shall write Cs_{2} their category: a map f : (X, A) → (Y, B) comes from a map f : X → Y whose restriction A → B is also a map.

The induced map on cubical sets i_{∗} : T_{∗}A → T_{∗}X is injective as well as i_{∗} : C_{∗}A → C_{∗}X (a link in A is degenerate in X iff it is already so in A). We obtain the relative chains of (X, A) by the usual short exact sequence of chain complexes

0  C_{∗}A  C_{∗}X  C_{∗}(X, A)  0  (4)

the relative homology as the homology of the quotient, H_{n}(X, A)=H_{n}(C_{∗}(X, A)), and the natural exact sequence of the pair (X, A) from the exact homology sequence of (4), with Δ_{n}[c] = [∂_{n}c]

⋯ → H_{n}A → H_{n}X → H_{n}(X, A) →^{Δ} H_{n−1}A → ⋯

→ H_{0}A → H_{0}X → H_{0}(X, A) → 0.  (5)

Plainly, C_{∗}(X, ∅) = C_{∗}(X) and H_{n}(X, ∅) = H_{n}(X). More generally, given a combinatorial triple (X, A, B), consisting of subobjects B ≺ A ≺ X, the snake lemma gives a short exact sequence of chain complexes C_{∗}(A, B) ↣ C_{∗}(X, B) ↠ C_{∗}(X, A) and the exact sequence

⋯ → H_{n}(A, B) → H_{n}(X, B) → H_{n}(X, A) → H_{n−1}(A, B) → ⋯
→ H_{0}(X, A) → 0.  (6)

Plainly, the homology of a sum X = ΣX_{i} is a direct sum H_{n}X = ⊕H_{n}X_{i} (and every combinatorial space is the sum of its connected components, 1.1). It is also easy to see that if X is connected (non empty), then H_{0}(X) ≅ Z (via the augmentation ˜∂_{0} : C_{0}X = F |X| → Z taking each point x ∈ X to 1 ∈ Z); thus, for every c-space X, H_{0}(X) is the free abelian group generated by π_{0}X.

Finally, combinatorial homology has finite supports: the group H_{n}(X) is the inductive limit of the system of groups H_{n}(A), where A varies in the set of finite subspaces A ⊂ X (ordered by inclusion). In fact, this is already true at the chain level: each chain c = Σ_{i}λ_{i}â_{i} ∈ C_{n}(X) belongs to C_{n}(A), where A is the (finite) union of all images a_{i}(2^{n}).

1.6. Mayer–Vietoris and excision. Recall that, given two subobjects U, V ≺ X, the structure of their union U ∪ V is !U∪!V, while the structure of U ∩ V is !U∩!V (1.1). It follows easily that C_{∗} takes subobjects of X to chain subcomplexes of C_{∗}X, preserving joins and meets

C_{∗}(U ∪ V) = C_{∗}U + C_{∗}V,  C_{∗}(U ∩ V) = C_{∗}U ∩ C_{∗}V.  (1)

These facts have two important well-known consequences [17].

(a) The Mayer–Vietoris sequence. Let X = U ∪ V be a combinatorial space (we shall say that X is covered by its subobjects U, V). Then we have an exact sequence

⋯ ⟶ H_{n}(U ∩ V) ⟶^{(i_{∗},j_{∗})} (H_{n}U) ⊕ (H_{n}V) ⟶^{[u_{∗},−v_{∗}]} H_{n}(X)
⟶^{Δ} H_{n−1}(U ∩ V) ⟶ ⋯  (2)

with the obvious meaning of round and square brackets; the maps u : U → X, v : V → X, i : U ∩ V → X, j : U ∩ V → X are inclusions, and the connective Δ is:

Δ[c] = [∂_{n}a],  c = a + b (a ∈ N_{n}(T_{∗}U), b ∈ N_{n}(T_{∗}V)).  (3)

The sequence is natural, for a map f : X → X′ = U′ ∪ V′, whose restrictions U → U′, V → V′ are maps. (If our subobjects are subspaces, it is sufficient to know that fU ⊂ U′ and fV ⊂ V′).

(b) Excision. Let a combinatorial space X be given, with subobjects B ≺ Y, A. The inclusion map i : (Y, B) → (X, A) is said to be excisive whenever !Y \!B =!X\!A (or equivalently: Y ∪ A = X, Y ∩ A = B, in the lattice of subobjects of X). Then i induces isomorphisms in homology.

The proof is similar to the topological one, simplified by the fact that here no subdivision is needed. For (a), it is sufficient to apply the algebraic theorem of the exact homology sequence to the following sequence of chain complexes

0 ⟶ C_{∗}(U ∩ V) ⟶^{(i_{∗},j_{∗})} (C_{∗}U) ⊕ (C_{∗}V) ⟶^{[u_{∗},−v_{∗}]} C_{∗}(X) ⟶ 0 (4)

whose exactness needs one non-trivial verification. Take a ∈ C_{n}U, b ∈ C_{n}V and assume that u_{∗}(a) = v_{∗}(b); therefore, each link really appearing in a (and b) has image in U ∩ V, and, by hypothesis, is a link there; globally, there is (one) normalised chain c ∈ C_{n}(U ∩ V) such that i_{∗}(c) = a, i_{∗}(c) = b.

For (b), the proof reduces to a Noether isomorphism for the chain complexes

C(Y, B) = (C_{∗}Y)/(C_{∗}(Y ∩ A)) = (C_{∗}Y)/((C_{∗}Y) ∩ (C_{∗}A))
= (C_{∗}Y + C_{∗}A)/(C_{∗}A) = (C_{∗}(Y ∪ A))/(C_{∗}A) = C_{∗}(X, A). (5)

2. Combinatorial Homotopy and Homology

We develop here the interaction of combinatorial homology with the intrinsic homotopy theory of simplicial complexes introduced in Part I.

2.1. Paths. A line of the combinatorial space X is a map a : Z → X, i.e. a sequence of points of X, written a(i) or a_{i}, with a_{i}!a_{i+1} for all i ∈ Z. The lines of X form the combinatorial space L(X) = X^{Z}; a finite set Λ of lines is linked iff each set ∪_{a∈Λ}{a_{i}, a_{i+1}} is linked in X (for i ∈ Z).

A path (I.2.2) in X is a line a : Z → X eventually constant on the left and on the right: there is a finite interval ρ = [ρ^{−}, ρ^{+}] ⊂ Z (ρ^{−} ⩽ ρ^{+}) such that a is constant on the half-lines ] − ∞, ρ^{−}], [ρ^{+}, ∞[

a(i) = a(ρ^{κ}), for κi ⩾ κρ^{κ} (κ = ±1),  (1)

and determined by its values over ρ; the latter is called an (admissible) support of a. The end points of a, or faces ∂^{κ}a = a(ρ^{κ}), do not depend on its choice.

The path object P X ⊂ X^{Z} is the combinatorial subspace of paths. The path functor P : Cs → Cs acts on a morphism f : X → Y as a subfunctor of (−)^{Z}

P f : P X → P Y,  (P f)(a) = fa;  (2)

the faces are natural transformations ∂^{κ} : P → 1. The functor P is again a cubical comonad with symmetries (I.2.4), which is relevant for the study of homotopy. Here, we just need “first order properties” of homotopy, and it is sufficient to recall: the degeneracy e : 1 → P, taking a point x to the constant path at x, e(x) : Z → X, and the reversion r : P → P, taking the path a to the reversed path r(a) = −a : i ↦ a(−i).

Two points x, x′ ∈ X are linked by a path in X iff x ∼ x′, for the equivalence relation generated by the tolerance relation ! of X (1.1): π_{0}X = |X|/ ∼ is indeed the set of path-components of X.

2.2. Homotopies. Classically (cf. [17, 3.5]), two maps f, g : X → Y are said to be contiguous if, for each ξ linked in X, f(ξ) ∪ g(ξ) is linked in Y, i.e. if f!g in the simplicial complex Y^{X} (1.1); a contiguity class of maps is an equivalence class generated by the previous relation. As in Part I, we shall use a wider notion of homotopy, the one deriving from the path functor P.

A homotopy of simplicial complexes (I.3.1) α : f → g : X → Y is a map α : X → P Y such that ∂^{−}α = f, ∂^{+}α = g. It can also be viewed as a map α : X → Y^{Z}, or α : Z × X → Y, such that every line α(x) admits a support ρ(x) = [ρ^{−}(x), ρ^{+}(x)] and

α(i, x) = f(x), for i ⩽ ρ^{−}(x),  α(i, x) = g(x), for i ⩾ ρ^{+}(x). (1)

Our homotopy is said to be bounded if it admits a constant support ρ(x) = ρ; and bounded on connected components if this holds on every connected component of X. Similarly, in a left bounded (resp. positive, immediate) homotopy α, all paths α(x) admit a support [ρ^{−}, ρ^{+}(x)] (resp. [0, ρ^{+}(x)], [0, 1]). Immediate homotopies belong to the set Cs(X, Y^{2}) = Cs(2 × X, Y): they are represented by the functor T Y = Y^{2} of elementary paths and corepresented by the elementary cylinder 2 × X. Thus, an immediate homotopy amounts to a pair of contiguous maps f!g, and two maps are bounded homotopic iff they are in the same contiguity class. Plainly, if X is finite, each homotopy defined on it is bounded.

On the other hand, general homotopies are represented by the path functor P (as maps X → P Y), but cannot be corepresented (as maps IX → Y, for some object IX): the path functor has no left adjoint and there is no cylinder functor (in fact, P preserves finite limits, but does not preserve infinite products, I.2.4). The category Cs will always be equipped with general homotopies and the operations produced by the path functor, its degeneracy and reversion:

(a) whisker composition of maps and homotopies (for u : X′ → X, v : Y → Y′):

v ∘ α ∘ u = vgu (v ∘ α ∘ u = P v.α.u : X′ → P Y′),

(b) trivial homotopies:

0_{f} : f → f (0_{f} = ef : X → P Y),

(c) reversion:

−α : g → f (−α = rα : X → P Y).

Therefore, the homotopy relation f ≃ g, defined by the existence of a homotopy f → g, is a reflexive and symmetric relation, “weakly’ consistent with composition (f ≃ g implies vfu ≃ vgu), but presumably not transitive (related congruences are discussed in I.3.2). Two objects are homotopy equivalent if they are linked by a finite sequence of homotopy equivalences. The object X is contractible if it is homotopy equivalent to a point.

A deformation retract S of a combinatorial space X is a subspace whose inclusion u has a retraction p, with up ≃ idX

u : S ⇄ X : p,  pu = 1, α : up → 1_{X},  (2)

and we speak of a positive (resp. bounded, immediate) deformation retract when the homotopy α can be so chosen. Thus, an immediate deformation retract u : S ⊂ X has a retraction p with (idX)!(up), i.e. ξ ∪ up(ξ) is linked for all ξ ∈!X. An object is positively (resp. immediately) contractible if it admits a positive (resp. immediate) deformation retract reduced to a point; thus, X is immediately contractible to its point x_{0} iff the latter can be added to any linked part (or is linked to any point, in a tolerance set). A non-empty chaotic space is immediately contractible to each of its points.

2.3. Telescopic homotopies. The simplicial complexes Z^{n} and R^{n} are contractible, but not bounded contractible. This can be shown by means of “telescopic” homotopies based on lattice operations, quite different from the usual topological contraction φ : [0, 1]×R^{n} = R^{n}, φ(t, x) = t.x. Such homotopies can also be adapted to various regions of Z^{n} and R^{n}, forming a tool of immediate use in computing homotopy or homology groups of planar or 3-dimensional images. We give here some prime examples, referring the reader to Part I (Section 3) for a more detailed study.

First, if E denotes either Z or R (with the t_{1}-structure) one can consider the homotopy

\begin{matrix}α : 0 → id : E → E, \\ α(i, x) = 0 ∨ (i ∧ x),  α(i, −x) = −α(i, x) (x ⩾ 0), \end{matrix}  (1)

whose general path α(−, x) has a positive support, namely [0, ρ^{+}(x)], with |x| ⩽ ρ^{+}(x) < |x| + 1.

We call α a telescopic homotopy because it can be pictured as a collection of “telescopic arms” which stretch down, in the diagram below (for E = Z), at increasing i ⩾ 0; the arm at x stabilities at depth ρ^{+}(x) = |x|

\begin{matrix}\begin{matrix}… \\ … \\ … \\ … \\ … \end{matrix} & \begin{matrix}| & \begin{matrix}0 \\ −1 \\ −2 \\ −3 \end{matrix} & | \\ … \end{matrix} & \begin{matrix}| & \begin{matrix}0 \\ −1 \\ −2 \end{matrix} & | \\ −2 \\ … \end{matrix} & \begin{matrix}| & \begin{matrix}0 \\ −1 \end{matrix} & | \\ −1 \\ −1 \\ … \end{matrix} & \begin{matrix}| & 0 & | \\ 0 \\ 0 \\ 0 \\ … \end{matrix} & \begin{matrix}| & {0 \atop 1} & | \\ 1 \\ 1 \\ … \end{matrix} & \begin{matrix}| & 0 1 2 & | \\ 2 \\ … \end{matrix} & \begin{matrix}| & 0 1 2 3 & | \\ … \end{matrix} & \begin{matrix}… \\ … \\ … \\ … \\ … \end{matrix} & \begin{matrix}(i = 0) \\ (i = 1) \\ (i = 2) \\ (i = 3) \end{matrix} \\ … & −3 & -2 & -1 & 0 & 1 & 2 & 3 & … & (x ∈ Z) \end{matrix} (2)

Note that there is no positive homotopy in the opposite direction id → 0. In fact, in the integral case, any positite homotopy β : id → f : Z → Z is necessarily trivial, since the map g = β(1, −) adjacent to id

\begin{matrix}… & −2 & −1 & 0 & 1 & 2 & … & (i = 0) \\ … & g(−2) & g(−1) & g(0) & g(1) & g(2) & … & (i = 1) \end{matrix}  (3)

must coincide with the former (g(j) is linked with j−1, j, j+1, whence g(j) = j), and so on. It is easy to see that the same holds in the real case. It follows that the only bounded deformation retract of the integral or real line is the line itself.

Now, for the n-dimensional space E^{n}, a telescopic homotopy will be any product of 1-dimensional telescopic homotopies (centred at any point) and trivial homotopies. For instance, for n = 2, consider β = α × α (centred at the origin) and γ = 0_{id} × α (centred at the horizontal axis)

β : 0 → id : E^{2} → E^{2},  β(i, x_{1}, x_{2}) = (α(i, x_{1}), α(i, x_{2})),  (4)
γ : p_{1} → id : E^{2} → E^{2},  γ(i, x_{1}, x_{2}) = (x_{1}, α(i, x_{2})),  (5)

which show, respectively, that the origin and the horizontal axis are homotopy retracts of E^{2}.

Less trivially, to prove that the simplicial complex t_{ε}X ⊂ t_{ε}R^{2} described in Fig. (a) of the Introduction is contractible for ε ⩾ 3, we need a generalised telescopic homotopy centred at the horizontal axis, with “variable vertical jumps” 1, 3, 1 (all ⩽ ε and adjusted to jump over the two holes); for a precise definition, see I.3.6.

2.4. Invariance Theorem. The homology functors H_{n} : Cs → Ab (1.5) are homotopy invariant: if f ≃ g, then H_{n}(f) = H_{n}(g). Similarly for relative homology.

Proof. Let us begin from an immediate homotopy α : f^{−} → f^{+}, represented by a map α : 2×X → Y. As for cubical singular homology [14], yields a homotopy of cubical sets

\begin{matrix}β : T_{∗}f^{−} → T_{∗}f^{+} : T_{∗}X → T_{∗}Y, \\ β_{n} : T^{n}X → T^{n+1}Y,  β_{n}(a : 2^{n} → X) = α ∘ (2 × a) : 2^{n+1} → Y; \end{matrix} (1)

in fact, for a ∈ T^{n}X, b ∈ T^{n−1}X, 1 ⩽ i ⩽ n, and κ = 0, 1 (−, + in superscripts)

\begin{aligned}(∂_{i+1}^{κ}β_{n}a)(t_{1}, …, t_{n}) & = α ∘ (t_{1}, a(t_{2}, …, κ, …, t_{n}))=(β_{n−1}∂_{i}^{κ}a)(t_{1}, …, t_{n}), \\ (∂_{1}^{κ}β_{n}a)(t_{1}, …, t_{n}) & = α ∘ (κ, a(t_{1}, …, t_{n})) = (f^{κ}a)(t_{1}, …, t_{n}), \\ (β_{n}e_{i}b)(t_{1}, …, t_{n+1}) & = α ∘ (t_{1}, b(t_{2}, …, t̂_{i+1}, …, t_{n+1})) = \\ & = (e_{i+1}β_{n−1}b)(t_{1}, …, t_{n+1}). \end{aligned} (2)

Then β produces a homotopy of the associated normalised chain complexes

γ_{n} : C_{n}X → C_{n+1}Y,  γ_{n} (Σ_{i}λ_{i}â_{i}) = Σ_{i}λ_{i}(β_{n}(a_{i}))ˆ .  (3)

Now, a bounded homotopy is a finite concatenation of immediate ones, and produces again a homotopy of chain complexes. Finally, for a general homotopy, it suffices to recall that combinatorial homology has finite supports (1.5), and that each homotopy on a finite domain is bounded (2.2). □

2.5. Reduced homology and the elementary suspension. Simplicial complexes have an elementary suspension ΣX, which plays the role of a homological suspension, i.e. a functor Σ : Cs → Cs with a natural isomorphism h_{n} : H̃_{n}(X) = H̃_{n+1}(ΣX), in reduced homology. (Its topological analogue is McCord’s non-Hausdorff suspension, [15, Section 8].)

The augmented cubical chain complex C̃_{∗}X has a component C_{−1}(X) = Z, with augmentation ˜∂_{0} : C_{0}X = F |X| → Z taking each point x ∈ X to 1 ∈ Z. Its homology is the reduced homology of X

H̃_{n} : Cs → Ab,  H̃_{n}(X) = H_{n}(C̃_{∗}X) (n ⩾ −1).  (1)

Let Z_{∗} = C̃_{∗}(∅) be the chain complex reduced to one component Z, in degree −1. The obvious short exact sequence Z_{∗} ↣ C̃_{∗}X ↠ C_{∗}X produces an exact homology sequence, which reduces to a four-term exact sequence in low dimension and a sequence of identities for n ⩾ 1

0 → H̃_{0}(X) → H_{0}(X) → Z → H̃_{−1}(X) → 0,  H̃_{n}(X) = H_{n}(X). (2)

Thus, also H̃_{0}(X) is free abelian. If X is empty, all homology and reduced homology groups vanish, except for H̃_{−1}(∅) = Z. In the contrary, ˜∂_{0} : F |X| → Z is surjective and H̃_{−1}(X) = 0: the sequence in (2) splits as H_{0}(X) ≅ H̃_{0}(X)⊕Z. Reduced homology also has a Mayer–Vietoris sequence, which ends in degree −1, proved in the same way; but note that it does not preserve sums.

Now, ΣX will be the c-space |X| ∪ {±∞}, with two new points, and new linked subsets of type ξ ∪ {−∞}, ξ ∪ {+∞} for ξ ∈!X. Thus, the octahedral spheres are obtained as iterated suspensions ⋄S^{n} = Σ^{n}S^{0} = Σ^{n+1}(∅) (in a particular instance of ΣX, the new points are written as convenient).

ΣX is covered by two subspaces, the lower and upper elementary cones

\begin{matrix}C^{−}X = X ∪ \{−∞\},  u^{+} : X ⊂ C^{−}X,  ∂^{−} : \{∗\} → C^{−}X, ∗ ↦ −∞, \\ C^{+}X = X ∪ \{+∞\},  u^{−} : X ⊂ C^{+}X,  ∂^{+} : \{∗\} → C^{+}X, ∗ ↦ +∞, \end{matrix}

(3)

which are immediately contractible to their vertex κ^{∞} (2.2). Since their intersection is X, the Mayer–Vietoris sequence of ΣX in reduced homology gives a natural isomorphism (for n ⩾ −1)

Δ_{n+1} : H̃_{n+1}(ΣX) = H̃_{n}(X),  Δ_{n+1}[c] = [∂_{n+1}a],  (4)

where c = a + b, a ∈ C_{n+1}(C^{−}X) and b ∈ C_{n+1}(C^{+}X).

The isomorphism s_{n} = (−1)^{n+1}(Δ_{n+1})^{−1} : H̃_{n}(X) = H̃_{n+1}(ΣX) has a more canonical description: it is induced by the following chain map s̄_{∗} of degree 1

\begin{matrix}s̄_{−1} : C̃_{−1}X = Z → C_{0}(ΣX),  1 ↦ (−∞) − (+∞), \\ s̄_{n} : C_{n}X → C_{n+1}(ΣX),  (a : 2^{n} → X) ↦ a^{−} − a^{+} (n ⩾ 0), \\ a^{κ} : 2^{n} × 2 → C^{κ}X ⊂ ΣX,  a^{κ}(t, 0) = a(t), a^{κ}(t, 1) = κ^{∞}, \\ ∂(a^{−} − a^{+}) = (Σ_{i,κ}(−1)^{i+κ}∂_{i}^{κ}(a^{−} − a^{+})) + (−1)^{n+1}(a − a) \\ = (∂a)^{−} − (∂a)^{+} (i ⩽ n; κ = ±). \end{matrix} (5)

Since we already know that Δ_{n+1} is iso, it is sufficient to check that Δ_{n+1}·s_{n} = (−1)^{n+1}id on each homology class [Σλ_{i}a_{i}] (∂(Σλ_{i}a_{i}) = 0)

Δ_{n+1} · s_{n}[Σλ_{i}a_{i}] = Δ_{n+1}[Σλ_{i}(a_{i}^{−} − a_{i}^{+})] = [Σλ_{i}∂(a_{i}^{−})]
= [(Σλ_{i}∂a_{i})^{−}] + (−1)^{n+1}[Σλ_{i}a_{i}] = (−1)^{n+1}[Σλ_{i}a_{i}]. (6)

We end with some formal remarks. The elementary lower cone C^{−}X comes with an immediate homotopy δ^{−} : ∂^{−}p → u^{+} : X → C^{−}X from the vertex to the basis, which is universal for all immediate homotopies f → g : X → Y where f is constant (factors through the point); symmetrically for C^{+}X. The elementary suspension comes with a homotopy of support [−1, 1])

\begin{matrix}σ : ∂^{−} → ∂^{+} : X → ΣX,  σ(−1, x) = −∞, \\ σ(0, x) = x,  σ(1, x) = +∞, \end{matrix}  (8)

which is universal for all homotopies of support [−1, 1], between constant maps defined on X.

But there is no standard cone and no standard suspension, representing homotopies of the previous kinds without restrictions on supports. In fact, and loosely speaking, the cone or the suspension of the singleton would produce a standard interval I and a cylinder functor I × (−), which we already know not to exist. (For a precise proof, one can adapt the argument of I.6.5 showing that the pointed S^{0} has no suspension in Cs^{∗}, even up to homotopy: there is no pointed simplicial complex S^{1} allowing one to represent π_{1}(X) = [S^{0}, ΩX] as [S^{1}, X].)

2.6. Metric combinatorial homology. Metric spaces inherit a family of homology theories (metric combinatorial homology at resolution ε) via the functors t_{ε} : Mtr_{2} → Cs_{2}

H_{n}^{ε} : Mtr_{2} → Ab, H_{n}^{ε}(X, A) = H_{n}(t_{ε}X, t_{ε}A) (0 < ε < ∞),  (1)

on the obvious category Mtr_{2} of pairs (X, A) of metric spaces (A ⊂ X with the induced metric).

The axioms of Eilenberg–Steenrod are satisfied in an adapted form depending on ε (for excision):

- the functoriality and dimension axioms hold trivially;

- exactness and naturality for the homology sequence of a pair (X, A) come from the similar properties (1.5) for the combinatorial pair (t_{ε}X, t_{ε}A);

- homotopy invariance holds for homotopies α : ([0, 1] × X, [0, 1] × A) → (Y, B) in Mtr_{2}; in fact, choose a finite partition 0 = t_{0} < ⋯ < t_{k} = 1 of the standard interval such that t_{i} − t_{i−1} ⩽ ε; then α produces a combinatorial homotopy (actually in Tol_{2}), with bounded support [0, k] ⊂ Z

β : (Z × t_{ε}X, Z × t_{ε}A) → (t_{ε}Y, t_{ε}B),  β(i, x) = α(t_{(i∨0)∧k}, x),  (2)

since |i − i′| ⩽ 1 and d(x, x′) ⩽ ε implies d(β(i, x), β(i′, x′)) ⩽ ε;

- finally, the excision isomorphism H_{n}^{ε}(X \U, A\U) → H_{n}^{ε}(X, A) holds for metric subspaces U ⊂ A ⊂ X, provided that: if x ∈ U and d(x, x′) ⩽ ε, then x′ ∈ A; in fact, under this condition, the combinatorial inclusion map (t_{ε}(X \ U), t_{ε}(A \ U)) = (t_{ε}X, t_{ε}A) is excisive (1.6b): if ξ is linked in X either it is contained in X \ U, or there is some x ∈ ξ ∩ U; but then ξ ⊂ A.

3. Comparison Homomorphisms

We deal now with the combinatorial Hurewicz homomorphism from homotopy to homology (3.1) and the canonical isomorphism from combinatorial homology to the singular homology of a realisation, either the well-known geometric one (3.2), or the “open-spot dilation” (in a particular case, 3.4-5).

3.1. The combinatorial Hurewicz comparison. Let X be a pointed combinatorial space. There is a natural Hurewicz homomorphism, for n ⩾ 1

\begin{matrix}h_{n} : π_{n}(X) → H_{n}(X),  [a] ↦ [Σ_{i}a_{i}], \\ a_{i} : 2^{n} → X,  a_{i}(j) = a(i + j) (i ∈ Z^{n}), \end{matrix}  (1)

where a : Z^{n} → X is a net with trivial faces, all a_{i} : 2^{n} → X are links (degenerate except for finitely many indices i, belonging to the support of a), and the normalised chain Σ_{i}a_{i} is a cycle.

Similarly, for a combinatorial space X,

h_{0} : π_{0}(X) → H_{0}(X),  [a] ↦ [a],  (2)

is a mapping of sets, and actually the canonical basis of the free abelian group H_{0}(X).

It should not be difficult to prove directly the Hurewicz theorem for combinatorial homotopy and homology, adapting the classical proof of the topological case; but we shall deduce it from the latter (in 3.3), via the geometric comparisons in homotopy (I.6.6) and homology (below).

3.2. The geometric comparison in homology. Let X be a combinatorial space, ℛX its geometric realisation. As proved in [17], there is a natural isomorphism (geometric comparison)

Φ_{n} : H_{n}(X) → H_{n}(ℛX),  Φ_{n}[Σ_{i}k_{i}a_{i}] = [Σ_{i}k_{i}â_{i}],  (1)

from combinatorial homology to (singular) homology, which we adapt now to cubical chains.

The geometric realisation ℛX is the set of all mappings λ : X → [0, 1] with linked support supp(λ), such that Σ_{x}λ(x) = 1. X is embedded in ℛX, identifying x ∈ X with its characteristic function. A point of ℛX can be viewed as a convex combination λ = Σ_{i}λ_{i}x_{i} of a linked family of X; each (non-empty) linked subset ξ having p + 1 points spans a simplex

Δ(ξ) = {λ ∈ ℛX | supp(λ) ⊂ ξ}.  (2)

All Δ(ξ) are equipped with the euclidean topology (via a bijective correspondence with the standard simplex Δ^{p}, determined by any linear order of ξ), and ℛX with the direct limit topology defined by such subsets: a subset of ℛX is open (or closed) if and only if it is so in every Δ(ξ). (This is generally known in the literature as the weak or coherent topology, as distinct from the metric topology, cf. [17, p. 111]). Each Δ(ξ) is closed in ℛX. The open simplex Δ^{∘}(ξ) = {λ ∈ ℛX | supp(λ) = ξ} is open in Δ(ξ); ℛX is the disjoint union of its open simplices.

The image of a link a : 2^{n} → X is a linked subset ξ of X, contained in the convex space Δ(ξ) ⊂ ℛX, and we can consider the multiaffine extension â : [0, 1]^{n} → ℛX of a (separately affine in each variable). This transformation, plainly consistent with faces and degeneracies, defines a natural homomorphism (1), which is proved in [17] to be iso.

If X is pointed or n = 0, this comparison is coherent with the similar isomorphism Φ_{n} : π_{n}(X) → π_{n}(ℛX) constructed in I.6.6: we have a commutative diagram

\begin{matrix}π_{n}(X) & ⟶^{Φ_{n}} & π_{n}(ℛX) \\ ^{h_{n}}↓ & & ↓^{h_{n}} \\ H_{n}(X) & ⟶^{Φ_{n}} & H_{n}(ℛX) \end{matrix}  (3)

with the Hurewicz maps h_{n}, the combinatorial one at the left (3.1) and the usual, topological one, at the right. This diagram is natural, for maps f : X → Y in Cs^{∗} (Cs for n = 0).

3.3. Corollary. (a) (Hurewicz) Let X be a pointed combinatorial space. If X is n-connected (π_{k}(X) trivial for 0 ⩽ k ⩽ n), then H_{k}(X) = 0 for 0 < k ⩽ n and h_{n+1} : π_{n+1}(X) → H_{n+1}(X) is iso (or, for n = 0, induces an iso ab(π_{1}(X)) → H_{1}(X) from the abelianised group).

(b) (Whitehead) If f : X → Y is a map of connected pointed simplicial complexes and π_{k}(f) is an isomorphism for 1 ⩽ k ⩽ n, the same holds for H_{k}(f).

(c) (Whitehead) If f : X → Y is a map of non empty simplicial complexes and for all x ∈ X, π_{k}(f) : π_{k}(X, x) → π_{k}(Y, f_{x}) is an iso for 0 ⩽ k ⩽ n, the same holds for H_{k}(f).

Proof. (a) Apply the usual (topological) Hurewicz theorem to the commutative diagram 3.2.3.

(b) Again in the diagram 3.2.3 (natural on f), apply a theorem of J.H.C. Whitehead [9, p. 167] saying that, if a map g : S → T between path-connected pointed spaces induces an iso on the k-homotopy groups, for 1 ⩽ k ⩽ n, the same holds for singular homology. (There is also a modified version, where one assumes that π_{k}(f) is an iso for 1 ⩽ k < n and epi for k = n, and concludes the same for H_{k}(f). Both facts are easily deduced from the exact homotopy and homology sequences of the pair (M_{f}, X) based on the mapping cylinder of f, linked by Hurewicz homomorphisms.)

(c) Follows from the previous point, via direct sum decomposition over pathcomponents. □

3.4. The open-spot dilation. Let X be a metric space and ε > 0. First, we want to compare the tolerance structures t_{ε}X and t_{ε}^{−}X, where two points are linked iff their distance is ⩽ ε or < ε, respectively (1.2). As is the case for homotopy groups, the homology groups of the first family determine the ones of the second (but not vice versa, cf. I.7.3)

H_{n}(t_{ε}^{−}X) = colim_{η<ε} H_{n}(t_{η}X),  (1)

as a trivial consequence of the finiteness of links: a map a : 2^{n} → t_{ε}^{−}X is also a map 2^{n} → t_{η}X, for η = diam(a(2^{n})) < ε.

Now, let X be a metric subspace of a normed vector space E and ε > 0. Recall (from I.7.4) that the open-spot realisation D_{ε}^{−}(X) of X in E (a dilation operator considered in mathematical morphology, cf. [8]) is the subspace of E formed by the union of all open d-discs centred at points of X, of radius ε/2 (pointed at the base-point of X, if X is pointed)

D_{ε}^{−}(X) = D_{ε}^{−}(X, d) = {x′ ∈ E | d(x, x′) < ε/2 for some x ∈ X} ⊃ X. (2)

Say that X is t_{ε}^{−}-closed (resp. t_{ε}-closed) in E if D_{ε}^{−}(X) contains the convex envelope of all linked subsets of t_{ε}^{−}X (resp. t_{ε}X), so that there is a continuous mapping

f_{ε}^{−} : ℛ(t_{ε}^{−}X) → D_{ε}^{−}(X) (resp. f_{ε} : ℛ(t_{ε}X) → D_{ε}^{−}(X)),  (3)

extending the identity of X and affine on each simplex Δ(ξ) of the domain. Note that, if X is t_{ε}-closed, then it is also t_{ε}^{−}-closed and f_{ε}^{−} = (ℛ(t_{ε}^{−}X) → ℛ(t_{ε}X) → D_{ε}^{−}(X)) factors as the map induced by the subobject-inclusion t_{ε}^{−}X ≺ t_{ε}X followed by f_{ε}.

3.5. Theorem (Open-spot comparison isomorphisms in homology).

(a) If X is t_{ε}^{−}-closed in E, there is a canonical isomorphism Ψ_{n}^{−} : H_{n}(t_{ε}^{−}X) → H_{n}(D_{ε}^{−}X) between the combinatorial and topological homology groups, which is the composite of the geometric realisation isomorphism Φ_{n} (3.2) with an isomorphism induced by the “affine” map f_{ε}^{−}

Φ_{n}^{−} = H_{n}(f_{ε}^{−}) · Φ_{n} = (H_{n}(t_{ε}^{−}X) → H_{n}(ℛ(t_{ε}^{−}X)) → H_{n}(D_{ε}^{−}X)) (n ⩽ 1). (1)

(b) If X is also t_{ε}-closed, there is a canonical isomorphism Ψ_{n} : H_{n}(t_{ε}X) → H_{n}(D_{ε}^{−}X) consisting of the lower row of the following commutative diagram of isomorphisms

\begin{matrix}H_{n}(t_{ε}^{−}X) & ⟶^{Φ_{n}} & H_{n}(ℛ(t_{ε}^{−}X)) & ⟶^{H_{n}(f_{ε}^{−})} & H_{n}(D_{ε}^{−}X) \\ ↓ & & ↓ & & ∥ \\ H_{n}(t_{ε}X) & ⟶^{Φ_{n}} & H_{n}(ℛ(t_{ε}X)) & ⟶^{H_{n}(f_{ε})} & H_{n}(D_{ε}^{−}X) \end{matrix}  (1)

(the two vertical arrows being induced by the inclusion t_{ε}^{−}X ≺ t_{ε}X).

Proof. Let X be t_{ε}^{−}-closed (resp. t_{ε}-closed) in E. As proved in theorem I.7.5, the homotopy homomorphism π_{n}(f_{ε}^{−}, x) (resp. π_{n}(f_{ε}, x)) is an isomorphism, for all x ∈ X and n ⩽ 1. From the Whitehead theorem (the classical, topological one, in form 3.3c) it follows that H_{n}(f_{ε}^{−}) (resp. H_{n}(f_{ε})) is iso, for n ⩽ 1.

Combining this with the geometric comparison Φ_{n} (3.2), we have the thesis.

□

4. Computation of Combinatorial Homology

In this section some computations of homology are given, either directly via the intrinsic Mayer–Vietoris (M-V) sequence, or via the geometric realisation; in some cases, one might similarly use the open-spot dilation (3.4-5). The results in 4.3-4 are used as a support for image analysis.

4.1. Homological circles. All the circles C_{k} (k ⩾ 3; 1.3) are homological 1spheres, since their geometric realisation is the circle. But the homology is also easily computed by the M-V sequence (1.6).

(a) If k > 3, C_{k} is covered by two subspaces U, V which are contractible (being isomorphic to integral intervals) and whose intersection is the discrete object on two points, e.g.

U = {[0], [1], [2]},  V = {[2], …, [k − 1], [0]},  (1)

so that, taking into account the homology of a sum and the invariance theorem (2.4), the computation on the M-V sequence proceeds precisely as for the topological circle.

(b) For C_{3}, take the subobject U = {[0], [1], [2]} ≺ C_{3} with the tolerance structure [0]![1]![2], and V = {[2], [0]} ⊂ C_{3}, with the induced (chaotic) structure.

Then, U and V are contractible and U ∩ V acquires the discrete structure. One concludes as above.

The naturality of the M-V sequence proves also that all maps p_{k} : C_{k+1} → C_{k} induce isomorphism in homology (by the Five Lemma); this suggests that it might be useful to realise a “standard circle” as a pro-object (cf. I.6.5).

4.2. Homological spheres. The n-sphere ΔS^{n} ≺ e^{n+1} (1.3) has the same homology as the topological n-sphere, since its geometric realisation is homeomorphic to the standard (topological) sphere S^{n}. Our result can also be proved by induction, as in the topological case, covering ΔS^{n} (n ⩾ 1) with the following subobjects (a face of the standard simplex and the union of all the others)

U = e^{n} = C{e_{0}, …, e_{n}} ⊂ ΔS^{n},  V ≺ ΔS^{n} ≺ e^{n+1},  (1)

where V has the same underlying set {e_{0}, …, e_{n+1}} as ΔS^{n}, and all its linked sets except U. Then, U ∩ V = ΔS^{n−1}.

For the cubical n-sphere □S^{n} ≺ 2^{n+1} (whose geometric realisation is a space of dimension 2^{n}−1, having the homotopy type of the n-sphere), the direct proof is similar: cover □S^{n} (n ⩾ 1) with the following subobjects (again, a face of the standard cube and the union of all the others)

U = 2^{n} = C{0, 1}^{n} ⊂ □S^{n},  V ≺ □S^{n} ≺ 2^{n+1},  (2)

where V has the same underlying set {0, 1}^{n} as □S^{n}, and all its linked sets except U. Again, U ∩ V = □S^{n−1}.

Finally, the octahedral n-sphere ⋄S^{n} = {±e_{0}, …, ±e_{n}} ⊂ Z^{n+1} has again for geometric realisation the n-sphere. But it suffices to recall that ⋄S^{n} = Σ^{n}S^{0} and apply the suspension isomorphisms (2.5); or also, to apply M-V to the following subspaces U, V, which are immediately contractible to ±e_{n}

U = ⋄S^{n−1} ∪ {−e_{n}},  V = ⋄S^{n−1} ∪ {e_{n}},  U ∩ V = ⋄S^{n−1}. (3)

4.3. Metric combinatorial homology and image analysis. The homology at variable resolution H_{n}^{ε}(X) = H_{n}(t_{ε}X) of a metric subspace X ⊂ (R^{n}, d_{∞}) can often be computed directly (as its fundamental group in Part I), using the telescopic retracts introduced in I.3 and the M-V sequence (instead of the van Kampen theorem). This can be of interest within image analysis, as showed by the examples below. Of course, H_{1}^{ε}(X) yields less fine results than the fundamental group (by Hurewicz); but, in higher dimension, homology is generally easier to compute.

Let us consider, as in I.7.1.2, the closed region X = T \ (A ∪ B ∪ C) of the real plane (with the l_{∞}-metric), endowed with the t_{ε}-structure (> 0)

X_{1}  _{4}  _{8}  _{10}^{1}^{2}^{5}  ^{A}  ^{B}  ^{C}  \begin{aligned}T & = [0, 11] × [0, 5] \\ A & =]1, 4[×]1, 4[ \\ B & = [4, 8]×]1, 2[ \\ C & =]8, 10[×]1, 3[ \end{aligned}  (1)

Then, the same coverings and telescopic homotopies used in I.7.1 for π_{1}^{ε}(X) show that H_{0}^{ε}(X) ≅ Z and H_{n}^{ε}(X) = 0 for all n > 1, while the first homology group gives:

H_{1}^{ε}(X) ≅ Z (0 < ε < 1; 2 ⩽ ε < 3), Z^{2} (1 ⩽ ε < 2), 0 (3 ⩽ ε ⩽ ∞), (2)

the generators being provided by the 1-chains associated to the loops which generate π_{1}^{ε}(X) (I.7.1). These results (including the description of generators) give the same analysis of the metric space X as provided by the fundamental group (I.1.8): at fine resolution (0 < ε < 1), our map presents one basin A∪B∪C; then two basins A, C connected by a bridgeable channel B (1 ⩽ ε < 2); or one basin A with a negligible appendix (2 ⩽ ε < 3); and finally no relevant basin (ε ⩾ 3). Also here, the finite model X ∩ (ρZ × ρZ), resulting from a scanner at resolution ρ = k^{−1} (for an integer k ⩾ 2, in order to simplify the interference with the boundary of X), has the same homology groups for ε ⩾ ρ (and the same analysis).

Similarly, one proves that the solid metric subspace X′ = T′ \(A′ ∪B′ ∪C′) ⊂ R^{3}, where

\begin{matrix}T′ = [0, 11] × [0, 5]^{2}, & A′ =]1, 4[×]1, 4[^{2}, \\ B′ = [4, 8]×]1, 2[^{2}, & C′ =]8, 10[×]1, 3[^{2}, \end{matrix}  (3)

equipped with the t_{ε}-structure (ε > 0), has H_{0}^{ε}(X) ≅ Z, H_{n}^{ε}(X′) = 0 for all other n ≠ 2, and

H_{2}^{ε}(X′) ≅ Z (0 < ε < 1; 2 ⩽ ε < 3), Z^{2} (1 ⩽ ε < 2), 0 (3 ⩽ ε ⩽ ∞). (4)

The analysis is analogous to the previous one, 1 dimension up: our object presents one cavity A′ ∪B′ ∪C′, at resolution 0 < ε < 1; then two cavities A′, C′ connected by a thin channel (1 ⩽ ε < 2); or one cavity A′ with a negligible appendix (2 ⩽ ε < 3); and finally no relevant cavity (ε ⩾ 3).

4.4. Critical values. Considering the previous examples, one is lead to consider the variation of the system of homology groups H_{n}^{ε}(X) → H_{n}^{η}(X) (0 ⩽ ε ⩽ η ⩽ ∞), for a metric space X, through its critical values (cf. Deheuvels [4], Milnor [16]).

Say that ε is a left regular (resp. right regular, regular) value for this system (i.e., for the combinatorial n-homology of X) if the system itself is constant on a left (resp. right, bilateral) neighbourhood of ε in the extended real interval [0, ∞]. In the contrary, ε is a left critical (resp. right critical, critical) value; and a bilateral critical value if it is both left and right critical.

Thus, in dimension 1, the metric space X considered in 4.3.1 has a right critical value at 0 and left critical values at 1, 2, 3. The metric subspace Y = T \ (A ∪ B) ⊂ R^{2} represented below has a right critical value at 0 and a bilateral critical value at 2

1  _{3}  _{8}  _{10}^{1}^{4}  ^{A}  ^{B}  \begin{matrix}T = & [0, 11] × [0, 4] \\ A = & ]1, 3[×]1, 3[ \\ B = & [8, 10] × [1, 3] \end{matrix}  (1)

H_{1}^{ε}(Y) ≅ Z^{2} (0 < ε < 2),  Z (ε = 2),  0 (ε > 2),  (2)

since its homology groups can be computed by the same techniques as above (cf. I.7.2).

4.5. Proposition. For a general metric space X, assume that the real interval K = [ε, η] ⊂ [0, ∞] does not contain any critical value in dimensions n − 1, n, n + 1 (except possibly a left critical value at ε and a right one at η). Then H_{n}^{ε}(X) → H_{n}^{η}(X) is an isomorphism (but not vice versa, cf. 4.3.2).

Proof. K is compact and every p ∈ K has a K-neighbourhood where the homology system is constant, in the given degrees; by the Lebesgue covering theorem, one can find a finite partition of K, ε = p_{0} < p_{1} < ⋯ < p_{k} = η, whose intervals [p_{i−1}, p_{i}] are contained in such neighbourhoods. Thus all H_{m}(t_{p_{i−1}}X) → H_{m}(t_{p_{i}}X) are iso (m = n − 1, n, n + 1), and the relative homologies H_{m}(t_{p_{i}}X, t_{p_{i−1}}X) are null, for m = n, n+1, by the exact homology sequence of a pair. The exact homology sequence of the triple (t_{p_{i+1}}X, t_{p_{i}}X, t_{p_{i−1}}X) shows then that also H_{m}(t_{p_{i+1}}X, t_{p_{i−1}}X) = 0, in the same degrees m = n, n + 1 (0 < i < k). Similarly, by finite induction, H_{m}(t_{η}X, t_{ε}X) = 0 for m = n, n+1; finally, the thesis follows from the exact homology sequence of the pair (t_{η}X, t_{ε}X). □

Acknowledgements

This work is supported by MIUR Research Projects.

References

1. K. Borsuk, Concerning homotopy properties of compacta. Fund. Math. 62(1968), 223–254.

2. L. Boxer, A classical construction for the digital fundamental group. J. Math. Imaging Vision 10(1999), 51–62.

3. J. M. Cordier and T. Porter, Shape theory: categorical methods of approximation. Ellis Horwood, Chichester, 1989.

4. R. Deheuvels, Topologie d’une fonctionelle. Ann. of Math. (2) 61(1955), 13–72.

5. M. Grandis, Cubical monads and their symmetries. Proc. of the Eleventh Intern. Conf. on Topology, Trieste 1993, Rend. Ist. Mat. Univ. Trieste 25(1993), 223–262.

6. M. Grandis, Cubical homotopical algebra and cochain algebras. Ann. Mat. Pura Appl. 170(1996), 147–186.

7. M. Grandis, An intrinsic homotopy theory for simplicial complexes, with applications to image analysis. Appl. Categ. Structures 10(2002), 99–155.

8. H. J. A. M. Heijmans, Mathematical morphology: a modern approach in image processing based on algebra and geometry. SIAM Rev. 37(1995), 1–36.

9. S. T. Hu, Homotopy theory. Academic Press, New York, 1959.

10. P. J. Hilton and S. Wylie, Homology theory. Cambridge Univ. Press, Cambridge, 1962.

11. T. Y. Kong, R. Kopperman, and P. R. Meyer, A topological approach to digital topology. Amer. Math. Monthly 98(1991), 901–917.

12. T. Y. Kong, R. Kopperman, and P. R. Meyer Eds., Special issue on digital topology. Topology Appl. 46(1992), No. 3, 173–303.

13. S. Mardešić and J. Segal, Shape theory: the inverse system approach. North-Holland Mathematical Library, 26. North-Holland Publishing Co., Amsterdam-New York, 1982.

14. W. Massey, Singular homology theory. Graduate Texts in Mathematics, 70. Springer-Verlag, New York-Berlin, 1980.

15. M. C. McCord, Singular homology groups and homotopy groups of finite topological spaces. Duke Math. J. 33(1966), 465–474.

16. J. W. Milnor, Morse theory. Annals of Mathematics Studies, No. 51. Princeton Univ. Press, Princeton, N.J., 1963 .

17. E. H. Spanier, Algebraic topology. McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1966

18. L. Vietoris, Über den höheren Zusammenhang kompakter Räume und eine Klasse von zusammenhangstreue Abbildungen. Math. Ann. 97(1927), 454–472.

(Received 28.05.2002; revised 14.12.2002)

Author’s address:

Dipartimento di Matematica Università di Genova Via Dodecaneso, 35, 16146-Genova Italy E-mail: grandis@dima.unige.it