Completions, Perforations and Fillings

Abstract

We introduce new local operations, perforations and fillings, which transform couples of objects (X, Y) such that $X \subseteq Y$. We complement these two operations by collapses and anti-collapses of both X and Y. This set of operations may be seen as a generalization of transformations based solely on collapses, thus a generalization of simple homotopy. Though these transformations do not, in general, preserve homotopy, we make a link between perforations, fillings, and simple homotopy. We give a full characterization of the collection of couples of objects that is closed under the above set of operations. Also, we provide a full characterization of the collection of couples of objects that is closed under the single operation of collapse.

1 Introduction

Simple homotopy, introduced by J. H. C. Whitehead in the early 1930’s, may be seen as a refinement of the concept of homotopy [1]. Two complexes are simple homotopy equivalent if one of them may be obtained from the other by a sequence of elementary collapses and anti-collapses.

Simple homotopy plays a fundamental role in combinatorial topology [1,2,3,4]. Also, many notions relative to homotopy in the context of computer imagery rely on the collapse operation. In particular, this is the case for the notion of a simple point, which is crucial for all image transformations that preserve the topology of the objects [5,6,7], see also [8,9,10].

In this paper, we introduce new local operations, perforations and fillings, which transform couples of objects. Intuitively, a perforation of a couple (X, Y), with $X \subseteq Y$, consists of removing a part of Y which is also a part of X, a filling is the operation that reverses the effect of a perforation. We complement these two operations by collapses and anti-collapses of both X and Y, with the constraint that we keep the inclusion relation between X and Y. This set of operations may be seen as a generalization of transformations based solely on collapses, thus a generalization of simple homotopy. We formalize these notions by means of completions, which are inductive properties expressed in a declarative way [11].

Our main results include the following:

• Though these transformations do not, in general, preserve homotopy, we make a link between perforations, fillings, and simple homotopy.

• In particular, we show there is an equivalence between the collection of couples of objects that is closed under the above local operations and the collection made of all contractible objects.

• We give a full characterization of this collection. This characterization is given by four global properties, which are a subset of the five completions that describe acyclic pairs of objects.

• We also provide a full characterization of the collection of couples of objects that is closed under the single operation of collapse.

The paper is organized as follows. First, we give some basic definitions for simplicial complexes (Sect. 2) and simple homotopy (Sect. 3). Then, we recall some facts relative to completions (Sect. 4). We also recall the definitions of the completions that describe acyclic objects (dendrites) and acyclic pairs (dyads) in Sect. 5. Then, we present homotopic pairs and give preliminary results on contractibility (Sect. 6). In Sect. 7, we introduce our perforation and filling operations and give properties relative to these transformations. In Sect. 8, we present some results on collapsible pairs. Note that the paper is self contained.

2 Basic Definitions for Simplicial Complexes

Let X be a finite family composed of finite sets. The simplicial closure of X is the complex $X^- = \{ y \subseteq x \; | \; x \in X \}$. The family X is a (simplicial) complex if $X = X^-$. We write $\mathbb {S}$ for the collection of all simplicial complexes.

Observe that $\emptyset \in \mathbb {S}$ and $\{ \emptyset \} \in \mathbb {S}$. The complex $\emptyset$ is the void complex, and the complex $\{ \emptyset \}$ is the empty complex.

Let $X \in \mathbb {S}$. An element of X is a simplex of X or a face of X. A facet of X is a simplex of X that is maximal for inclusion. For example, the family $X = \{ \emptyset , \{ a \}, \{ b \}, \{a,b \} \}$ is a simplicial complex with four faces and one facet. Note that the empty set is necessarily a face of X whenever $X \not = \emptyset$.

A simplicial subcomplex of $X \in \mathbb {S}$ is any subset Y of X that is a simplicial complex. If Y is a subcomplex of X, we write $Y \preceq X$.

Let $X \in \mathbb {S}$. The dimension of $x \in X$, written dim(x), is the number of its elements minus one. The dimension of X, written dim(X), is the largest dimension of its simplices, the dimension of $\emptyset$, the void complex, being defined to be $-1$. Observe that the dimension of the empty complex $\{ \emptyset \}$ is also $-1$.

A complex $A \in \mathbb {S}$ is a cell if $A = \emptyset$ or if A has precisely one non-empty facet x. We set $A^{\circ } = A \setminus \{ x\}$ and $\emptyset ^\circ = \emptyset$. We write $\mathbb {C}$ for the collection of all cells. A cell $\alpha \in \mathbb {C}$ is a vertex if $dim(\alpha ) = 0$.

The ground set of $X \in \mathbb {S}$ is the set $\underline{X} = \cup \{ x \in X \; | \; dim(x) = 0 \}$. Thus, if $A \in \mathbb {C}$, with $A \not = \emptyset$, then $\underline{A}$ is precisely the unique facet of A. In particular, if $\alpha$ is a vertex, we have $\alpha = \{\emptyset , \underline{\alpha }\}$.

We say that $X \in \mathbb {S}$ and $Y \in \mathbb {S}$ are disjoint, or that X is disjoint from Y, if $\underline{X} \cap \underline{Y} = \emptyset$. Thus, X and Y are disjoint if and only if $X \cap Y = \emptyset$ or $X \cap Y = \{ \emptyset \}$.

If $X \in \mathbb {S}$ and $Y \in \mathbb {S}$ are disjoint, the join of X and Y is the simplicial complex XY such that $X Y = \{ x \; \cup \; y \; | \; x \in X, y \in Y \}$. Thus $X Y = \emptyset$ if $Y = \emptyset$, and $X Y = X$ if $Y = \{ \emptyset \}$. The join $\alpha X$ of a vertex $\alpha$ and a complex $X \in \mathbb {S}$ is a cone.

3 Collapse

Let us first recall some basic definitions related to the collapse operator [1].

Let $X \in \mathbb {S}$, and let x, y be two distinct faces of X. The couple (x, y) is a free pair for X if y is the only face of X that contains x. Thus, the face y is necessarily a facet of X. If (x, y) is a free pair for X, then $Y = X \setminus \{x,y \}$ is an elementary collapse of X, and X is an elementary expansion of Y. We say that X collapses onto Y, or that Y expands onto X, if there exists a sequence $\langle X_0,...,X_k \rangle$ such that $X_0 = X$, $X_k = Y$, and $X_i$ is an elementary collapse of $X_{i-1}$, $i \in [1,k]$. The complex X is collapsible if X collapses onto $\emptyset$. We say that X is (simply) homotopic to Y, or that X and Y are (simply) homotopic, if there exists a sequence $\langle X_0,...,X_k \rangle$ such that $X_0 = X$, $X_k = Y$, and $X_i$ is an elementary collapse or an elementary expansion of $X_{i-1}$, $i \in [1,k]$. The complex X is (simply) contractible if X is simply homotopic to $\emptyset$.

In the sequel, we will use the following facts.

• 1) Let $X,Y \in \mathbb {S}$, and let (x, y) be a free pair for Y. Thus $Y' = Y \setminus \{x,y\}$ is an elementary collapse of Y. If x and y are not in X, we observe that $X \cup Y'$ is an elementary collapse of $X \cup Y$. It follows that:

  $$The~complex~Y~collapses~onto~X \cap Y~if~and~only~if~ X \cup Y~collapses~onto~X.$$

• 2) Let $\alpha$ be an arbitrary vertex. We have $\alpha = \{ \emptyset , \underline{\alpha } \}$. The couple $(\emptyset , \underline{\alpha })$ is a free pair for $\alpha$. Hence $\alpha$ collapses onto $\emptyset$, i.e., the vertex $\alpha$ is collapsible.

• 3) Let $X \in \mathbb {S}$, $Y \preceq X$, and let $\alpha$ be a vertex disjoint from X. If $X = \{ \emptyset \}$, we have $\alpha X = \alpha$, and either $Y= X$ or $Y = \emptyset$. Otherwise, let x be a facet of X that is not in Y. We observe that the couple $(x, \underline{\alpha } \cup x)$ is a free pair for the cone $\alpha X$. Thus, the cone $\alpha X'$, with $X' = X \setminus \{x, \underline{\alpha } \cup x \}$, is an elementary collapse of the cone $\alpha X$. By induction, we obtain:

  $$If~Y \preceq X,~then~\alpha X~collapses~onto~\alpha Y.$$

  If $Y = \emptyset$, it means that $\alpha X$ collapses onto $\emptyset$. Thus:

  $${Any~cone~is~collapsible.}$$

• 4) Let $X,Y \in \mathbb {S}$, with $X \preceq Y$, and let $\alpha$ be a vertex disjoint from Y. Let x and y be two faces of X. The couple (x, y) is a free pair for X if and only if $(\underline{\alpha } \cup x, \underline{\alpha } \cup y)$ is a free pair for $\alpha X \cup Y$. Thus, by induction, we have the following:

  $$The~complex~X~collapses~onto~Z~if~and~only~if~\alpha \,X \cup Y~collapses~onto~\alpha \,Z \cup Y.$$

  As a special case of this result, we obtain:

  $$The~complex~X~is~collapsible~if~and~only~if~\alpha \,X \cup Y~collapses~onto~Y.$$

• 5) Let $A \in \mathbb {C}$. If $A = \emptyset$, or if A is a vertex, then A is collapsible. Otherwise, there exists a vertex $\alpha$ and a cell B such that $A = \alpha B$, which is a cone. Thus, any cell is collapsible. Using the result 4), we see that the cell $A = \alpha B$ collapses onto the cell B. By induction, we obtain the following result:

  $$ If~A,B~\in ~\mathbb {C},~and~if~B \preceq A,~then~A~collapses~onto~B.$$

• 6) Let $X,Y \in \mathbb {S}$, with $X \not = \emptyset$. We observe that X is an elementary collapse of Y if and only if there exists a cell D, $D \not = \emptyset$, such that $Y = X \cup \alpha D$ and $X \cap \alpha D = \alpha D^\circ$, where $\alpha$ is a vertex disjoint from D.

Now, we recall the definition of the dual of a complex, and we give two related propositions which will be used for collapsibility.

Let $A \in \mathbb {C}$ and $X \preceq A$. The dual of X for A is the simplicial complex, written $X_A^*$, such that $X_A^* = \{ x \in A \; | \; (\underline{A} \setminus x) \not \in X \}$.

We have $\emptyset _A^* = A$ and $\{ \emptyset \}_A^* = A^\circ$, and, for any $A \in \mathbb {C}$, we have the following:

• If $X \preceq A$, then $(X_A^*)_A^* = X$.

• If $X \preceq A$, $Y \preceq A$, then $(X \cup Y)_A^* = X_A^* \cap Y_A^*$ and $(X \cap Y)_A^* = X_A^* \cup Y_A^*$.

Proposition 1

([4, 11]). Let $A \in \mathbb {C}$. Let $X,Y \in \mathbb {S}$, with $X \preceq Y \preceq A$. The complex Y collapses onto X if and only if $X_A^*$ collapses onto $Y_A^*$.

Proposition 2

([12]). Let $A \in \mathbb {C}$. Let $X,Y \in \mathbb {S}$, with $X \preceq Y \preceq A$, and let $\alpha$ be a vertex disjoint from A. Then we have $(\alpha X \cup Y)_{\alpha A}^* = \alpha Y_A^* \cup X_A^*$.

4 Completions

We give some basic definitions for completions. A completion may be seen as a rewriting rule that permits to derive collections of sets. See [11] for more details.

Let $\mathbf {S}$ be a given collection and let $\mathcal {K}$ be an arbitrary subcollection of $\mathbf {S}$. Thus, we have $\mathcal {K}\subseteq \mathbf {S}$. In the sequel of the paper, the symbol $\mathcal {K}$, with possible superscripts, will be a dedicated symbol (a kind of variable).

Let $\scriptstyle {\mathbf {K}}$ be a binary relation on $2^\mathbf {S}$, thus $\scriptstyle {\mathbf {K}}$ $\subseteq 2^\mathbf {S} \times 2^\mathbf {S}$. We say that $\scriptstyle {\mathbf {K}}$ is finitary, if $\mathbf {F}$ is finite whenever $(\mathbf {F}, \mathbf {G}) \in \; \scriptstyle {\mathbf {K}}$.

Let $\langle \mathrm {K} \rangle$ be a property that depends on $\mathcal {K}$. We say that $\langle \mathrm {K} \rangle$ is a completion (on $\mathbf {S}$) if $\langle \mathrm {K} \rangle$ may be expressed as the following property:

• $- \!\!\!>$ If $\mathbf {F} \subseteq \mathcal {K}$, then $\mathbf {G} \subseteq \mathcal {K}$ whenever $(\mathbf {F}, \mathbf {G}) \in \; \scriptstyle {\mathbf {K}}$.                                $\langle$ $\scriptstyle {\mathbf {K}}$ $\rangle$

where $\scriptstyle {\mathbf {K}}$ is a finitary binary relation on $2^\mathbf {S}$.

If $\langle \mathrm {K} \rangle$ is a property that depends on $\mathcal {K}$, we say that a given collection $\mathbf {X} \subseteq \mathbf {S}$ satisfies $\langle \mathrm {K} \rangle$ if the property $\langle \mathrm {K} \rangle$ is true for $\mathcal {K}= \mathbf {X}$.

Theorem 1

[11]. Let $\langle \mathrm {K} \rangle$ be a completion on $\mathbf {S}$ and let $\mathbf {X} \subseteq \mathbf {S}$. There exists, under the subset ordering, a unique minimal collection that contains $\mathbf {X}$ and that satisfies $\langle \mathrm {K} \rangle$.

If $\langle \mathrm {K} \rangle$ is a completion on $\mathbf {S}$ and if $\mathbf {X} \subseteq \mathbf {S}$, we write $\langle \mathbf {X}; \mathrm {K} \rangle$ for the unique minimal collection that contains $\mathbf {X}$ and that satisfies $\langle \mathrm {K} \rangle$.

Let $\langle \mathrm {K} \rangle$ be a completion expressed as the above property $\langle$ $\scriptstyle {\mathbf {K}}$ $\rangle$. By a fixed point property, the collection $\langle \mathbf {X}; \mathrm {K} \rangle$ may be obtained by starting from $\mathcal {K} = \mathbf {X}$, and by iteratively adding to $\mathcal {K}$ all the sets $\mathbf {G}$ such that $(\mathbf {F}, \mathbf {G}) \in \; \scriptstyle {\mathbf {K}}$ and $\mathbf {F} \subseteq \mathcal {K}$ (see [11]). Thus, if $\mathbf {C} = \langle \mathbf {X}; \mathrm {K} \rangle$, then $\langle \mathbf {X}; \mathrm {K} \rangle$ may be seen as a dynamic structure that describes $\mathbf {C}$; the completion $\langle \mathrm {K} \rangle$ acts as a generator, which, from $\mathbf {X}$, makes it possible to enumerate all elements in $\mathbf {C}$. We will see now that $\langle \mathrm {K} \rangle$ may in fact be composed of several completions.

Let $\langle \mathrm {K}_1 \rangle ,\langle \mathrm {K}_2 \rangle ,..., \langle \mathrm {K}_k \rangle$ be completions on $\mathbf {S}$. We write $\wedge$ for the logical “and”. It may be seen that $\langle \mathrm {K} \rangle = \langle \mathrm {K}_1 \rangle \wedge \langle \mathrm {K}_2 \rangle ...\wedge \langle \mathrm {K}_k \rangle$ is a completion. In the sequel, we write $\langle \mathrm {K}_1, \mathrm {K}_2,...,\mathrm {K}_k \rangle$ for $\langle \mathrm {K} \rangle$. Thus, if $\mathbf {X} \subseteq \mathbf {S}$, the notation $\langle \mathbf {X}; \mathrm {K}_1,\mathrm {K}_2,..., \mathrm {K}_k \rangle$ stands for the smallest collection that contains $\mathbf {X}$ and that satisfies each of the properties $\langle \mathrm {K}_1 \rangle , \langle \mathrm {K}_2 \rangle ,..., \langle \mathrm {K}_k \rangle$.

Let $\langle \mathrm {K} \rangle$, $\langle \mathrm {Q} \rangle$ be two completions on $\mathbf {S}$. We say that $\langle \mathrm {K} \rangle$ and $\langle \mathrm {Q} \rangle$ are equivalent if, for any $\mathbf {X} \subseteq \mathbf {S}$, the collection $\mathbf {X}$ satisfies $\langle \mathrm {K} \rangle$ if and only if $\mathbf {X}$ satisfies $\langle \mathrm {Q} \rangle$.

5 Dyads and Dendrites

The notion of a dendrite was introduced in [11] as a way for defining a collection made of acyclic complexes. Let us consider the collection $\mathbf {S} = \mathbb {S}$, and let $\mathcal {K}$ denote an arbitrary collection of simplicial complexes.

We define the two completions $\langle \textsc {D} 1 \rangle$ and $\langle \textsc {D} 2 \rangle$ on $\mathbb {S}$: For any $S,T \in \mathbb {S}$,

• $-\!\!\! >$ If S, $T \in \mathcal {K}$, then $S \cup T \in \mathcal {K}$ whenever $S \cap T$ $\in \mathcal {K}$.                                $\langle \textsc {D} 1 \rangle$

• $- \!\!\!>$ If S, $T \in \mathcal {K}$, then $S \cap T \in \mathcal {K}$ whenever $S \cup T$ $\in \mathcal {K}$.                                $\langle \textsc {D} 2 \rangle$

Let $\mathbb {D} = \langle \mathbb {C}; \textsc {D} 1, \textsc {D} 2 \rangle$. Each element of $\mathbb {D}$ is a dendrite or an acyclic complex.

The collection $\mathbb {T}$ of all trees (i.e., all connected acyclic graphs) provides an example of a collection of dendrites. It may be checked that $\mathbb {T}$ satisfies both $\langle \textsc {D} 1 \rangle$ and $\langle \textsc {D} 2 \rangle$, and that we have $\mathbb {T} \subseteq \mathbb {D}$. In fact, we have the general result [11]:

$$ A~complex~is~a~dendrite~if~and~only~if~it~is~ acyclic~in~the~sense~of~homology.$$

As a consequence, any contractible complex is a dendrite but there exist some dendrites that are not contractible. The punctured Poincaré homology sphere provides such a counter-example.

In the following, we will say that a dendrite is twisted if it is not contractible.

Intuitively, a dyad is a couple of complexes (X, Y), with $X \preceq Y$, such that the cycles of X are “at the right place with respect to the ones of Y”.

We set $\ddot{\mathbb {S}} = \{ (X,Y) \; | \; X,Y \in \mathbb {S}, X \preceq Y \}$, the notation $\ddot{\mathcal {K}}$ stands for an arbitrary subcollection of $\ddot{\mathbb {S}}$.

We define five completions on $\ddot{\mathbb {S}}$ (the symbols $\widetilde{\textsc {T}}$, $\widetilde{\textsc {U}}$, $\widetilde{\textsc {L}}$ stand respectively for “transitivity”, “upper confluence”, and “lower confluence”):

• For any S, $T \in \mathbb {S}$,

• $- \!\!\!>$ If $(S \cap T,T)$ $\in \ddot{\mathcal {K}}$, then $(S, S \cup T) \in \ddot{\mathcal {K}}$.                                            $\langle \widetilde{\textsc {X}} \rangle$

• $- \!\!\! >$ If $(S,S \cup T)$ $\in \ddot{\mathcal {K}}$, then $(S \cap T, T) \in \ddot{\mathcal {K}}$.                                            $\langle \widetilde{\textsc {Y}} \rangle$

• For any $(R,S),(S,T),(R,T) \in \ddot{\mathbb {S}}$,

• $- \!\!\! >$ If $(R,S) \in \ddot{\mathcal {K}}$ and $(S,T) \in \ddot{\mathcal {K}}$, then $(R,T) \in \ddot{\mathcal {K}}$.                                $\langle \widetilde{\textsc {T}}\rangle$

• $- \!\!\! >$ If $(R,S) \in \ddot{\mathcal {K}}$ and $(R,T) \in \ddot{\mathcal {K}}$, then $(S,T) \in \ddot{\mathcal {K}}$.                                $\langle \widetilde{\textsc {U}}\rangle$

• $- \!\!\! >$ If $(R,T) \in \ddot{\mathcal {K}}$ and $(S,T) \in \ddot{\mathcal {K}}$, then $(R,S) \in \ddot{\mathcal {K}}$.                                $\langle \widetilde{\textsc {L}}\rangle$

We set $\ddot{\mathbb {C}} = \{(A,B) \in \ddot{\mathbb {S}}\; | \; A, B \in \mathbb {C} \}$ and $\ddot{\mathbb {X}} = \langle \ddot{\mathbb {C}}; \widetilde{\textsc {X}}, \widetilde{\textsc {Y}}, \widetilde{\textsc {T}}, \widetilde{\textsc {U}}, \widetilde{\textsc {L}}\rangle$.

Each couple of $\ddot{\mathbb {X}}$ is a dyad or an acyclic pair.

Fig. 1.

Left: A circle X in a cylindrical surface Y, the couple (X, Y) is a dyad. Middle: The complex $\alpha X \cup Y$ is a dendrite. Thus, $\alpha X \cup Y$ is acyclic. Right, illustration of the completion $\langle \widetilde{\textsc {X}} \rangle$: If a complex Z is such that $Z \cap Y = X$, then $(Z,Z \cup Y)$ is a dyad. Here Z is a punctured cylindrical surface. Again, the complex $\alpha Z \cup (Z \cup Y)$ is acyclic.

In [12], the following fundamental relation between dyads and dendrites was given. Intuitively, Theorem 2 indicates that (X, Y) is a dyad if and only if we cancel out all cycles of Y (i.e., we obtain an acyclic complex), whenever we cancel out those of X (by the way of a cone). See Fig. 1, which also gives an illustration of the completion $\langle \widetilde{\textsc {X}} \rangle$.

Theorem 2

Let $(X,Y) \in \ddot{\mathbb {S}}$ and let $\alpha$ be a vertex disjoint from Y.

The couple (X, Y) is a dyad if and only if $\alpha X \cup Y$ is a dendrite.

In particular, setting $X = \emptyset$ in the above theorem, we see that a complex $D \in \mathbb {S}$ is a dendrite if and only if $(\emptyset ,D)$ is a dyad. Therefore, we have the following corollary of Theorem 2.

Corollary 1

Let $(X,Y) \in \ddot{\mathbb {S}}$ and let $\alpha$ be a vertex disjoint from Y.

The couple (X, Y) is a dyad if and only if $(\emptyset ,\alpha X \cup Y)$ is a dyad.

If $(X,Y) \in \ddot{\mathbb {S}}$ and $\alpha$ is a vertex disjoint from Y, we say that $\alpha X \cup Y$ is the $\varDelta$ -form of (X, Y) (with vertex $\alpha$ ). Such forms play a decisive role in our framework. We see that Theorem  2 may be formulated in this way: A couple $(X,Y) \in \ddot{\mathbb {S}}$ is a dyad if and only if its $\varDelta$-form is a dendrite.

6 Homotopy and Contractibiliy

We now recall the completions introduced in [13] for simple homotopy.

If $(I,O) \in \ddot{\mathbb {S}}$, the basic idea is to continuously deform both the inner complex I and the outer complex O, these deformations keeping I inside O.

If $X,Y \in \mathbb {S}$, we write $X {\mathop {\longmapsto }\limits ^{E}} Y$, whenever Y is an elementary expansion of X. We define four completions on $\ddot{\mathbb {S}}$: For any (R, S), (R, T), (S, T) in $\ddot{\mathbb {S}}$,

• $-\!\!\! >$ If $(R,S) \in \ddot{\mathcal {K}}$ and $S {\mathop {\longmapsto }\limits ^{E}} T$, then $(R,T) \in \ddot{\mathcal {K}}$.                 $\langle \textsc {O}{}^+ \rangle$

• $-\!\!\! >$ If $(R,T) \in \ddot{\mathcal {K}}$ and $S {\mathop {\longmapsto }\limits ^{E}} T$, then $(R,S) \in \ddot{\mathcal {K}}$.                 $\langle \textsc {O}{}^- \rangle$

• $- \!\!\! >$ If $(R,T) \in \ddot{\mathcal {K}}$ and $R {\mathop {\longmapsto }\limits ^{E}} S$, then $(S,T) \in \ddot{\mathcal {K}}$.                 $\langle \textsc {I}{}^+ \rangle$

• $- \!\!\! >$ If $(S,T) \in \ddot{\mathcal {K}}$ and $R {\mathop {\longmapsto }\limits ^{E}} S$, then $(R,T) \in \ddot{\mathcal {K}}$.                 $\langle \textsc {I}{}^- \rangle$

We set $\ddot{\mathbb {I}} = \{(X,X) \; | \; X \in \mathbb {S} \}$ and $\ddot{\mathbb {H}} = \langle \ddot{\mathbb {I}}; \textsc {O}{}^+, \textsc {O}{}^-, \textsc {I}{}^+, \textsc {I}{}^- \rangle$.

Each element of $\ddot{\mathbb {H}}$ is a homotopic pair.

Observe that X is homotopic to Y whenever $(X,Y) \in \ddot{\mathbb {H}}$. The following is a variant of a result given in [13] which gives a basic characterization of the collection $\ddot{\mathbb {H}}$.

Theorem 3

Let $(X,Y) \in \ddot{\mathbb {S}}$. We have $(X,Y) \in \ddot{\mathbb {H}}$ if and only if there exists a complex Z such that Z collapses onto X and Z collapses onto Y.

The following theorem is the important global result given in [13]. It shows that four of the five completions that describe dyads allow for a characterization of the collection made of all homotopic pairs. Thus, in this framework, we have a unified presentation of both acyclicity and homotopy.

Theorem 4

We have $\ddot{\mathbb {H}} = \langle \ddot{\mathbb {C}}; \widetilde{\textsc {X}}, \widetilde{\textsc {T}}, \widetilde{\textsc {U}}, \widetilde{\textsc {L}}\rangle$.

We now present some facts relative to contractibility. This special case of homotopy will play a crucial role in the sequel of this paper. The following is a direct consequence of the definition of contractibility and that of the collection $\ddot{\mathbb {H}}$.

Proposition 3

A complex $X \in \mathbb {S}$ is contractible if and only if $(\emptyset ,X) \in \ddot{\mathbb {H}}$.

The next proposition is a basic fact which will be useful in the sequel. It indicates that, if a subcomplex X of Y is contractible, then we can add or remove a cone on X without changing the homotopy of Y. Observe that it is not easy to prove this fact by using direct arguments, since the steps involved in the contractibility of X may “extend X outside Y”. With the global properties given by Theorem 4, only few lines are needed for establishing this result. See [17], Proposition 0.17, for a counterpart of this property in the framework of general homotopy.

Proposition 4

Let $(X,Y) \in \ddot{\mathbb {S}}$ and let $\alpha$ be a vertex disjoint from Y.

Suppose the complex X is contractible, i.e., we have $(\emptyset ,X) \in \ddot{\mathbb {H}}$. Then we have $(Y,\alpha X \cup Y) \in \ddot{\mathbb {H}}$. In particular, we have $(\emptyset ,Y) \in \ddot{\mathbb {H}}$ if and only if $(\emptyset ,\alpha X \cup Y) \in \ddot{\mathbb {H}}$.

Proof. Since any cone is collapsible, we have $(\emptyset ,\alpha X) \in \ddot{\mathbb {H}}$. By Theorem 4, the collection $\ddot{\mathbb {H}}$ satisfies $\langle \widetilde{\textsc {U}} \rangle$. Thus $(X,\alpha X) \in \ddot{\mathbb {H}}$. We may write $(Y \cap \alpha X,\alpha X) \in \ddot{\mathbb {H}}$. By $\langle \widetilde{\textsc {X}} \rangle$, we obtain $(Y,\alpha X \cup Y) \in \ddot{\mathbb {H}}$. Since $\ddot{\mathbb {H}}$ satisfies also $\langle \widetilde{\textsc {T}} \rangle$ and $\langle \widetilde{\textsc {L}} \rangle$, we see that $(\emptyset ,Y) \in \ddot{\mathbb {H}}$ if and only if $(\emptyset ,\alpha X \cup Y) \in \ddot{\mathbb {H}}$.$\Box$

Proposition 5

Let $(X,Y) \in \ddot{\mathbb {S}}$ and let $\alpha$ be a vertex disjoint from Y.

If $(X,Y) \in \ddot{\mathbb {H}}$, then $\alpha X \cup Y$ is contractible, i.e., we have $(\emptyset ,\alpha X \cup Y) \in \ddot{\mathbb {H}}$.

Proof. Let $(X,Y) \in \ddot{\mathbb {H}}$. We have $\alpha X \cap Y = X$, thus $(\alpha X \cap Y,Y) \in \ddot{\mathbb {H}}$. By $\langle \widetilde{\textsc {X}} \rangle$, we obtain $(\alpha X,\alpha X \cup Y) \in \ddot{\mathbb {H}}$. Since any cone is collapsible, we have $(\emptyset , \alpha X) \in \ddot{\mathbb {H}}$. The result follows from $\langle \widetilde{\textsc {T}} \rangle$. $\Box$

The converse of Proposition 5 is not true. Let X be a twisted dendrite, i.e., a non contractible dendrite. If A is a cell, with $X \preceq A$, then X is not homotopic to A, but $\alpha X \cup A$ is contractible. This fact is well known in algebraic topology [17].

Let $\ddot{\mathbb {K}}$ be a collection of couples such that $(\emptyset , \emptyset )$ is in $\ddot{\mathbb {K}}$. We define the kernel of $\ddot{\mathbb {K}}$ as the collection of all complexes $X \in \mathbb {S}$ such that $(\emptyset , X)$ is in $\ddot{\mathbb {K}}$.

Let us consider the two following properties, where $\alpha$ is a vertex disjoint from Y:

If $(X,Y) \in \ddot{\mathbb {K}}$, then the $\varDelta$-form $\alpha X \cup Y$ is in the kernel of $\ddot{\mathbb {K}}$.                          (K1)

If $(X,Y) \in \ddot{\mathbb {S}}$ and the $\varDelta$-form $\alpha X \cup Y$ is in the kernel of $\ddot{\mathbb {K}}$, then $(X,Y) \in \ddot{\mathbb {K}}$. (K2)

By Corollary 1, the collection $\ddot{\mathbb {X}}$ of dyads satisfies both (K1) and (K2). In particular, it means that $\ddot{\mathbb {X}}$ may be recovered from its kernel. By Proposition 5 and the above remark, the collection of all homotopic pairs $\ddot{\mathbb {H}}$ satisfies (K1) but not (K2).

In the next section, we will investigate the collection $\ddot{\mathbb {W}}$ of all pairs (X, Y) such that the $\varDelta$-form $\alpha X \cup Y$ is contractible. Thus, $\ddot{\mathbb {W}}$ will satisfy both (K1) and (K2) and, by the preceding remark, $\ddot{\mathbb {W}}$ will strictly contain the collection $\ddot{\mathbb {H}}$. Furthermore, we will see that $\ddot{\mathbb {W}}$ has a remarkable global characterization.

7 Filling and Perforation

Let $(X,Y) \in \ddot{\mathbb {S}}$ and $(X',Y') \in \ddot{\mathbb {S}}$. We say that (X, Y) is an elementary perforation of $(X',Y')$, if there exists a face f of both $X'$ and $Y'$ such that $X = X' \setminus \{ f \}$ and $Y = Y' \setminus \{ f \}$. Thus f is necessarily a facet of both $X'$ and $Y'$.

We say that $(X',Y')$ is an elementary filling of (X, Y), if (X, Y) is an elementary perforation of $(X',Y')$.

Let $(X,Y) \in \ddot{\mathbb {S}}$. We write $(X,Y) {\mathop {\longmapsto }\limits ^{F}} (X',Y')$ if $(X',Y')$ is an elementary filling of (X, Y). We define two completions on $\ddot{\mathbb {S}}$: For any (S, T), $(S',T')$ in $\ddot{\mathbb {S}}$,

• $- \!\!\! >$ If $(S,T) \in \ddot{\mathcal {K}}$ and $(S,T) {\mathop {\longmapsto }\limits ^{F}} (S',T')$, then $(S',T') \in \ddot{\mathcal {K}}$.                 $\langle \textsc {F}{} \rangle$

• $- \!\!\! >$ If $(S,T) \in \ddot{\mathcal {K}}$ and $(S',T') {\mathop {\longmapsto }\limits ^{F}} (S,T)$, then $(S',T') \in \ddot{\mathcal {K}}$.                 $\langle \textsc {P}{} \rangle$

We set $\ddot{\mathbb {\emptyset }} = \{ (\emptyset ,\emptyset ) \}$ and $\ddot{\mathbb {W}} = \langle \ddot{\mathbb {\emptyset }}; \textsc {O}{}^+, \textsc {O}{}^-, \textsc {I}{}^+, \textsc {I}{}^-, \textsc {F}{}, \textsc {P}{} \rangle$.

Each couple of $\ddot{\mathbb {W}}$ is a contractible pair.

We first observe that any couple $(X,X) \in \ddot{\mathbb {I}}$ may be obtained from $(\emptyset ,\emptyset )$ by iteratively applying the completion $\langle \textsc {F}{} \rangle$. In fact we see that $\ddot{\mathbb {I}} = \langle \ddot{\mathbb {\emptyset }}; \textsc {F}{} \rangle$.

Thus, we have $\ddot{\mathbb {W}} = \langle \ddot{\mathbb {I}}; \textsc {O}{}^+, \textsc {O}{}^-, \textsc {I}{}^+, \textsc {I}{}^-, \textsc {F}{}, \textsc {P}{} \rangle$.

See Fig. 2 which provides an illustration of four contractible pairs.

We have $\ddot{\mathbb {H}} = \langle \ddot{\mathbb {I}}; \textsc {O}{}^+, \textsc {O}{}^-, \textsc {I}{}^+, \textsc {I}{}^- \rangle$. Therefore, we immediately note that $\ddot{\mathbb {H}} \subseteq \ddot{\mathbb {W}}$ since the two additional completions $\langle \textsc {F}{} \rangle$ and $\langle \textsc {P}{} \rangle$ allow to generate more couples in $\ddot{\mathbb {W}}$. Also, we observe that, if we apply the completions $\langle \textsc {F}{} \rangle$ or $\langle \textsc {P}{} \rangle$ on a couple $(X,Y) \in \ddot{\mathbb {S}}$, then the homotopy of both X and Y is changed. Nevertheless, we will see that all couples $(X,Y) \in \ddot{\mathbb {W}}$ satisfy an homotopy condition.

It can be checked that each transformation of a couple $(X,Y) \in \ddot{\mathbb {S}}$, that is made according to the six completions which constitute the definition of $\ddot{\mathbb {W}}$, may be seen as a collapse or an expansion of a complex of the form $\alpha X \cup Y$.

Fig. 2.

Four contractible pairs. For each pair (X, Y), the subcomplex X of Y is highlighted by its facets (triangles, segments, or vertices). (a) A pair $(X_0,Y_0) \in \ddot{\mathbb {I}}$, thus $X_0 = Y_0$. (b) A pair $(X_1,Y_1)$: the complex $Y_1$ is obtained from $Y_0$ with a sequence of expansions, and $X_1$ is obtained from $X_0$ with a sequence of collapses. (c) A pair $(X_2,Y_2)$ obtained from $(X_1,Y_1)$ with three perforations. (d) A pair $(X_3,Y_3)$ obtained from $(X_2,Y_2)$ with three fillings.

Proposition 6

Let $(X,Y) \in \ddot{\mathbb {S}}$, let $X' \preceq X$, $Y' \preceq Y$, and let $\alpha$ be a vertex disjoint from Y. The complex $\alpha X' \cup Y'$ is an elementary collapse of $\alpha X \cup Y$ if and only if the couples $(X',Y')$ and (X, Y) are such that:

• we have $Y' = Y$ and the complex $X'$ is an elementary collapse of X, or

• we have $X' = X$ and the complex $Y'$ is an elementary collapse of Y, or

• the couple $(X',Y')$ is an elementary perforation of (X, Y).

As a consequence, we have the following result which makes the connection between the collection $\ddot{\mathbb {W}}$ and contractible complexes.

Proposition 7

Let $(X,Y) \in \ddot{\mathbb {S}}$ and let $\alpha$ be a vertex disjoint from Y.

We have $(X,Y) \in \ddot{\mathbb {W}}$ if and only if $\alpha X \cup Y$ is contractible, i.e., if and only if $(\emptyset ,\alpha X \cup Y) \in \ddot{\mathbb {H}}$.

By Theorem 3, we have $(\emptyset ,\alpha X \cup Y) \in \ddot{\mathbb {H}}$ if and only if there exists a complex Z such that Z collapses onto $\emptyset$, and Z collapses onto $\alpha X \cup Y$. Thus, the complex Z is collapsible. It follows that Proposition 7 and Theorem 3 permits to establish a link between the collection $\ddot{\mathbb {W}}$ and collapsibility. The following proposition will allow us to refine this result.

Proposition 8

Let $X \in \mathbb {S}$, $A \in \mathbb {C}$, with $X \preceq A$, and let $\alpha$ be a vertex disjoint from A. If X collapses onto $\emptyset$, then $\alpha A$ collapses onto X.

Proof. Suppose X collapses onto $\emptyset$, and let $A \in \mathbb {C}$ with $X \preceq A$. By Proposition 1, since $\emptyset _A^* = A$, the complex A collapses onto $X_A^*$. Let $\alpha$ be a vertex disjoint from A, and let $Z = \alpha X_A^* \cup A$. Since A collapses onto $X_A^*$, the complex Z collapses onto $\alpha X_A^*$. Thus Z collapses onto $\emptyset$. By Proposition 2, we have $Z_{\alpha A}^* = \alpha A^*_A \cup (X^*_A)^*_A$. We obtain $Z_{\alpha A}^* = X$. By Proposition 1, we deduce that $\alpha A$ collapses onto X. $\Box$

By Proposition 7, Theorem 3, and Proposition 8, we deduce that $(X,Y) \in \ddot{\mathbb {W}}$ if and only if there exists a cell $B \in \mathbb {C}$ such that B collapses onto $\alpha X \cup Y$. Clearly, we can assume that B is of the form $\alpha C$, with $C \in \mathbb {C}$.

Proposition 9

Let $(X,Y) \in \ddot{\mathbb {S}}$ and let $\alpha$ be a vertex disjoint from Y.

We have $(X,Y) \in \ddot{\mathbb {W}}$ if and only if there exists a cell $C \in \mathbb {C}$, which is disjoint from $\alpha$, such that the cell $\alpha C$ collapses onto $\alpha X \cup Y$.

Under the conditions of Proposition 9, we may write $\alpha C = \alpha C \cup C$. Hence, we have $(X,Y) \in \ddot{\mathbb {W}}$ if and only if there exists a cell $C \in \mathbb {C}$ such that (X, Y) may be obtained from (C, C) by using the three transformations given in Proposition 6. Since $(C,C) \in \ddot{\mathbb {I}}$, we obtain the following result.

Proposition 10

We have $\ddot{\mathbb {W}} = \langle \ddot{\mathbb {I}}; \textsc {O}{}^-, \textsc {I}{}^-, \textsc {P}{} \rangle$.

A direct consequence of Theorem 3 is that we have $\ddot{\mathbb {H}} = \langle \ddot{\mathbb {I}}; \textsc {O}{}^-, \textsc {I}{}^- \rangle$ (see Proposition 7 of [13]). Thus, the previous result may be seen as a counterpart of this characterization of homotopic pairs. We now point out the following equivalence.

Proposition 11

The two completions $\langle \textsc {F}{} \rangle$ and $\langle \widetilde{\textsc {X}} \rangle$ are equivalent and the two completions $\langle \textsc {P}{} \rangle$ and $\langle \widetilde{\textsc {Y}} \rangle$ are equivalent.

Proof. Let $\ddot{\mathbb {K}}$ be an arbitrary subcollection of $\ddot{\mathbb {S}}$.

• i) Suppose $\ddot{\mathbb {K}}$ satisfies property $\langle \textsc {P}{} \rangle$ and let $(S,S \cup T) \in \ddot{\mathbb {K}}$. Let x be a facet of S, with $x \not \in T$. If no such a facet exists, we are done. Otherwise, the face x is also a facet of $S \cup T$. Thus the couple $(S \setminus \{x\},(S \setminus \{x\}) \cup T)$ is an elementary perforation of $(S,S \cup T)$. By induction on the number of such facets, $\ddot{\mathbb {K}}$ satisfies $\langle \widetilde{\textsc {Y}} \rangle$.

• ii) Suppose $\ddot{\mathbb {K}}$ satisfies property $\langle \widetilde{\textsc {Y}}{} \rangle$. Let $(S,T) \in \ddot{\mathbb {K}}$ and let $(S',T')$ be an elementary perforation of (S, T). We have $(S,T) = (S, S \cup T')$, thus by $\langle \widetilde{\textsc {Y}}{} \rangle$, we have $(S \cap T', T') = (S', T') \in \ddot{\mathbb {K}}$. We deduce that $\ddot{\mathbb {K}}$ satisfies $\langle \textsc {P}{} \rangle$.

  It follows that $\langle \textsc {P}{} \rangle$ and $\langle \widetilde{\textsc {Y}} \rangle$ are equivalent. By reversing the above operations, we get the equivalence between $\langle \textsc {F}{} \rangle$ and $\langle \widetilde{\textsc {X}} \rangle$.    $\square$

Since the collection $\ddot{\mathbb {H}}$ satisfies the property $\langle \widetilde{\textsc {X}}{} \rangle$, a consequence of the above equivalence is that we can add another local transformation to the four completions which define homotopic pairs.

Corollary 2

We have $\ddot{\mathbb {H}} = \langle \ddot{\mathbb {I}}; \textsc {O}{}^+, \textsc {O}{}^-, \textsc {I}{}^+, \textsc {I}{}^-, \textsc {F} \rangle$.

The following is one of the main results of this paper. It shows that the collection of contractible pairs is uniquely identified by four global properties.

Theorem 5

We have $\ddot{\mathbb {W}} = \langle \ddot{\mathbb {C}}; \widetilde{\textsc {X}}, \widetilde{\textsc {Y}}, \widetilde{\textsc {T}}, \widetilde{\textsc {U}}\rangle$.

Proof. We set $\ddot{\mathbb {W'}} = \langle \ddot{\mathbb {C}}; \widetilde{\textsc {X}}, \widetilde{\textsc {Y}}, \widetilde{\textsc {T}}, \widetilde{\textsc {U}}\rangle$.

• 1) In this part, we show that we have $\ddot{\mathbb {W}} \subseteq \ddot{\mathbb {W'}}$.

  For that purpose we first establish the following result (R).

  Let $X,Y \in \mathbb {S}$. If $(\emptyset ,Y) \in \ddot{\mathbb {W'}}$ and if Y collapses onto X,then $(\emptyset ,X) \in \ddot{\mathbb {W'}}$.        (R)

  Suppose $(\emptyset ,Y) \in \ddot{\mathbb {W'}}$ and X is an elementary collapse of Y. If $X = \emptyset$, we are done. Otherwise, there exists a cell D, $D \not = \emptyset$, such that $Y = X \cup \alpha D$ and $X \cap \alpha D = \alpha D^\circ$, where $\alpha$ is a vertex disjoint from D. The complex $\alpha D$ being a cone, we have $(\emptyset , \alpha D) \in \ddot{\mathbb {W'}}$ (see Lemma 1 in [13]). By $\langle \widetilde{\textsc {U}}\rangle$, we get $(\alpha D,Y) = (\alpha D,X \cup \alpha D) \in \ddot{\mathbb {W'}}$. By $\langle \widetilde{\textsc {Y}} \rangle$, we derive $(\alpha D^\circ , X) \in \ddot{\mathbb {W'}}$. Since $\alpha D^\circ$ is a cone, we have $(\emptyset , \alpha D^\circ ) \in \ddot{\mathbb {W'}}$, and we obtain $(\emptyset , X) \in \ddot{\mathbb {W'}}$ (by $\langle \widetilde{\textsc {T}}\rangle$). By induction, we derive the result (R).

  Now, let $(X,Y) \in \ddot{\mathbb {S}}$ and let $\alpha$ be a vertex disjoint from Y. Suppose $(X, Y) \in \ddot{\mathbb {W}}$. Then, there exists a cell $\alpha C \in \mathbb {C}$ such that $\alpha C$ collapses onto $\alpha X \cup Y$ (Proposition 9). We have $(\emptyset ,\alpha C) \in \ddot{\mathbb {W'}}$. By (R) we obtain $(\emptyset ,\alpha X \cup Y) \in \ddot{\mathbb {W'}}$. We also have $(\emptyset , \alpha X) \in \ddot{\mathbb {W'}}$. Hence, by $\langle \widetilde{\textsc {U}}\rangle$, we have $(\alpha X, \alpha X \cup Y) \in \ddot{\mathbb {W'}}$. By $\langle \widetilde{\textsc {Y}} \rangle$, we deduce $(\alpha X \cap Y, Y) \in \ddot{\mathbb {W'}}$. Therefore $(X, Y) \in \ddot{\mathbb {W'}}$. Thus, we proved that $\ddot{\mathbb {W}} \subseteq \ddot{\mathbb {W'}}$.

• 2) By Proposition 11, $\ddot{\mathbb {W}}$ satisfies $\langle \widetilde{\textsc {X}} \rangle$ and $\langle \widetilde{\textsc {Y}} \rangle$. We also have $\ddot{\mathbb {C}} \subseteq \ddot{\mathbb {W}}$. So, we only have to show that $\ddot{\mathbb {W}}$ satisfies $\langle \widetilde{\textsc {U}}\rangle$ and $\langle \widetilde{\textsc {T}}\rangle$ in order to prove the inclusion $\ddot{\mathbb {W'}} \subseteq \ddot{\mathbb {W}}$.

  Let $(R,S),(S,T),(R,T) \in \ddot{\mathbb {S}}$. Suppose $(R,S) \in \ddot{\mathbb {W}}$, and let $\alpha$, $\beta$ be two distinct vertices disjoint from T. Let us consider the complex $U = \beta (\alpha R \cup S) \cup (\alpha R \cup T)$. By Proposition 7, we have $(\emptyset ,\alpha R \cup S) \in \ddot{\mathbb {H}}$. Hence, by Proposition 4, we have $(\alpha R \cup T, U) \in ~\ddot{\mathbb {H}}$. But we can write $U = \alpha (\beta R) \cup (\beta S \cup T)$. Since $(\emptyset , \beta R) \in \ddot{\mathbb {H}}$, again by Proposition 4, we have $(\beta S \cup T,U) \in \ddot{\mathbb {H}}$.

  • i) Suppose $(S,T) \in \ddot{\mathbb {W}}$. We have $(\emptyset ,\beta S \cup T) \in \ddot{\mathbb {H}}$ (Proposition 7) and $(\beta S \cup T,U) \in \ddot{\mathbb {H}}$. Thus $(\emptyset , U) \in \ddot{\mathbb {H}}$ (since $\ddot{\mathbb {H}}$ satisfies $\langle \widetilde{\textsc {T}}\rangle$). We have $(\alpha R \cup T, U) \in \ddot{\mathbb {H}}$ and $(\emptyset , U) \in \ddot{\mathbb {H}}$. Thus $(\emptyset ,\alpha R \cup T) \in \ddot{\mathbb {H}}$ (since $\ddot{\mathbb {H}}$ satisfies $\langle \widetilde{\textsc {L}}\rangle$). We obtain $(R,T) \in \ddot{\mathbb {W}}$ (Proposition 7). It follows that the collection $\ddot{\mathbb {W}}$ satisfies $\langle \widetilde{\textsc {T}}\rangle$.

  • ii) Suppose $(R,T) \in \ddot{\mathbb {W}}$. We have $(\emptyset ,\alpha R \cup T) \in \ddot{\mathbb {H}}$ (Proposition 7) and $(\alpha R \cup T, U) \in \ddot{\mathbb {H}}$. Thus $(\emptyset ,U) \in \ddot{\mathbb {H}}$ (since $\ddot{\mathbb {H}}$ satisfies $\langle \widetilde{\textsc {T}}\rangle$). We have $(\beta S \cup T,U) \in \ddot{\mathbb {H}}$ and $(\emptyset ,U) \in \ddot{\mathbb {H}}$. Thus $(\emptyset , \beta S \cup T) \in \ddot{\mathbb {H}}$ (since $\ddot{\mathbb {H}}$ satisfies $\langle \widetilde{\textsc {L}}\rangle$). We obtain $(S,T) \in \ddot{\mathbb {W}}$ (Proposition 7). Consequently, the collection $\ddot{\mathbb {W}}$ satisfies $\langle \widetilde{\textsc {U}}\rangle$. $\Box$

Therefore, the completion $\langle \widetilde{\textsc {L}}\rangle$ is the unique property that makes the distinction between the collections $\ddot{\mathbb {W}}$ and $\ddot{\mathbb {X}}$. Observe also the differences between $\ddot{\mathbb {W}}$ and $\ddot{\mathbb {H}}$: the collection $\ddot{\mathbb {W}}$ satisfies $\langle \widetilde{\textsc {Y}}\rangle$, but it no longer satisfies $\langle \widetilde{\textsc {L}}\rangle$. Nevertheless, as discussed before, the collection $\ddot{\mathbb {W}}$ strictly contains the collection $\ddot{\mathbb {H}}$.

Let us consider now the three following completions on $\ddot{\mathbb {S}}$.

For any $(R,S) \in \ddot{\mathbb {S}}$, $T \in \mathbb {S}$,

• $- \!\!\! >$ If $(R,S) \in \ddot{\mathcal {K}}$ and $(S \cap T,T)$ $\in \ddot{\mathcal {K}}$, then $(R, S \cup T) \in \ddot{\mathcal {K}}$.                 $\langle \widetilde{\textsc {Z}} 1 \rangle$

• $- \!\!\! >$ If $(R,S) \in \ddot{\mathcal {K}}$ and $(R,S \cup T)$ $\in \ddot{\mathcal {K}}$, then $(S \cap T,T) \in \ddot{\mathcal {K}}$.                 $\langle \widetilde{\textsc {Z}} 2 \rangle$

• $- \!\!\! >$ If $(R,S \cup T) \in \ddot{\mathcal {K}}$ and $(S \cap T,T)$ $\in \ddot{\mathcal {K}}$, then $(R,S) \in \ddot{\mathcal {K}}$.                 $\langle \widetilde{\textsc {Z}} 3 \rangle$

We set $\ddot{\mathbb {Z}} = \langle \ddot{\mathbb {C}}; \widetilde{\textsc {Z}} 1, \widetilde{\textsc {Z}} 2, \widetilde{\textsc {Z}} 3 \rangle$.

It has been shown that this set of completions allows for a characterization of dyads [12]. More precisely, it has been proved that we have $\ddot{\mathbb {X}} = \ddot{\mathbb {Z}}$.

The following theorem may be derived from Theorem 5 and from arguments used in four proofs given in [12] (Proofs of Prop. 1, 2, 3 and Th. 2).

Theorem 6

We have $\ddot{\mathbb {W}} = \langle \ddot{\mathbb {C}}; \widetilde{\textsc {Z}} 1, \widetilde{\textsc {Z}} 2 \rangle$.

Thus, Theorem 6 provides another characterization of contractibility by means of only two global properties.

8 Collapsible Pairs

In this section, we show that the three completions $\langle \widetilde{\textsc {X}} \rangle$, $\langle \widetilde{\textsc {Y}} \rangle$, $\langle \widetilde{\textsc {T}}\rangle$ allow us to describe collapsibility.

Let $(X,Y) \in \ddot{\mathbb {S}}$. If $\alpha$ is a vertex disjoint from Y, we say that $(\alpha X, \alpha Y)$ is a cone pair. We denote by $\ddot{\mathbb {\triangle }}$ the collection composed of all cone pairs.

Observe that we have $\ddot{\mathbb {C}} \subseteq \ddot{\mathbb {\triangle }}$. In [11], it was shown that the collection $\ddot{\mathbb {\triangle }}$ is closed under duality, but not the collection $\ddot{\mathbb {C}}$.

In the previous sections, we have often considered $\ddot{\mathbb {C}}$ as the starting collection of our completion systems. In the following, we will replace $\ddot{\mathbb {C}}$ by $\ddot{\mathbb {\triangle }}$ in order to obtain an exact characterization of collapsibility.

We set $\ddot{\mathbb {E}} = \langle \ddot{\mathbb {\triangle }}; \widetilde{\textsc {X}}, \widetilde{\textsc {T}} \rangle$. Each couple of $\ddot{\mathbb {E}}$ is a collapsible pair.

Proposition 12

We have $(X,Y) \in \ddot{\mathbb {E}}$ if and only if Y collapses onto X.

Proof

• i) Suppose X is an elementary collapse of Y. If $X = \emptyset$, we are done. Otherwise, there exists a cell D, $D \not = \emptyset$, such that $Y = X \cup \alpha D$ and $X \cap \alpha D = \alpha D^\circ$, where $\alpha$ is a vertex disjoint from D. The couple $(\alpha D^\circ , \alpha D)$ being a cone pair, we have $(\alpha D^\circ , \alpha D) \in \ddot{\mathbb {E}}$. By $\langle \widetilde{\textsc {X}} \rangle$, since $X \cap \alpha D = \alpha D^\circ$, we obtain $(X,X \cup \alpha D) \in \ddot{\mathbb {E}}$. Thus, $(X,Y) \in \ddot{\mathbb {E}}$. By induction, we have $(X,Y) \in \ddot{\mathbb {E}}$ whenever Y collapses onto X.

• ii) If $(\alpha X, \alpha Y) \in \ddot{\mathbb {\triangle }}$, then $\alpha Y$ collapses onto $\alpha X$. Furthermore:

  • If T collapses onto $S \cap T$, then $S \cup T$ collapses onto S.

  • If T collapses onto S, and S collapses onto R, then T collapses onto R. By induction on $\langle \widetilde{\textsc {X}} \rangle$ and $\langle \widetilde{\textsc {T}} \rangle$, the complex Y collapses onto X if $(X,Y) \in \ddot{\mathbb {E}}$. $\Box$

Thus, we have $(\emptyset , X) \in \ddot{\mathbb {E}}$ if and only if X collapses onto $\emptyset$. In other words, the kernel of $\ddot{\mathbb {E}}$ is precisely made of all collapsible complexes.

The following corollary is a direct consequence of Proposition 12.

Corollary 3

We have $\ddot{\mathbb {E}} = \langle \ddot{\mathbb {I}}; \textsc {I}{}^- \rangle = \langle \ddot{\mathbb {I}}; \textsc {O}{}^+ \rangle = \langle \ddot{\mathbb {I}}; \textsc {O}{}^+, \textsc {I}{}^- \rangle$.

In addition, the following proposition shows that $\ddot{\mathbb {E}}$ satisfies the property $\langle \widetilde{\textsc {Y}} \rangle$.

Proposition 13

We have $\ddot{\mathbb {E}} = \langle \ddot{\mathbb {\triangle }}; \widetilde{\textsc {X}}, \widetilde{\textsc {Y}}, \widetilde{\textsc {T}} \rangle$.

Proof. Let $(S,S \cup T) \in \ddot{\mathbb {E}}$. The complex $S \cup T$ collapses onto S (Proposition 12). Thus, T collapses onto $S \cap T$. Therefore $(S \cap T, T) \in \ddot{\mathbb {E}}$ (Again by Proposition 12). It means that the collection $\ddot{\mathbb {E}}$ satisfies the property $\langle \widetilde{\textsc {Y}} \rangle$. Thus $\ddot{\mathbb {E}} = \langle \ddot{\mathbb {\triangle }}; \widetilde{\textsc {X}}, \widetilde{\textsc {Y}}, \widetilde{\textsc {T}} \rangle$. $\Box$

The dunce hat [16] provides an example of a complex X that is contractible, but not collapsible. Since X is contractible, there exists a complex Y, which is collapsible, and which collapses onto X (a consequence of Proposition 3 and Theorem 3). Thus, we have $(X,Y) \in \ddot{\mathbb {E}}$ and $(\emptyset ,Y) \in \ddot{\mathbb {E}}$, but $(\emptyset , X) \not \in \ddot{\mathbb {E}}$. This shows that the collection $\ddot{\mathbb {E}}$ does not satisfy the property $\langle \widetilde{\textsc {L}} \rangle$. By considering the dual of the dunce hat in a cell, we obtain an example which shows that the collection $\ddot{\mathbb {E}}$ does not satisfy the property $\langle \widetilde{\textsc {U}} \rangle$.

Thanks to Proposition 12, we easily derive the following.

Proposition 14

We have $\ddot{\mathbb {H}} = \langle \ddot{\mathbb {\triangle }}; \widetilde{\textsc {X}}, \widetilde{\textsc {T}}, \widetilde{\textsc {L}}\rangle$.

Proof. Let $\ddot{\mathbb {K}} = \langle \ddot{\mathbb {\triangle }}; \widetilde{\textsc {X}}, \widetilde{\textsc {T}}, \widetilde{\textsc {L}}\rangle$. Clearly, we have $\ddot{\mathbb {\triangle }} \subseteq \ddot{\mathbb {H}}$. Furthermore, we have $\ddot{\mathbb {H}} = \langle \ddot{\mathbb {C}}; \widetilde{\textsc {X}}, \widetilde{\textsc {T}}, \widetilde{\textsc {U}}, \widetilde{\textsc {L}}\rangle$ (Theorem 4). Thus $\ddot{\mathbb {K}} \subseteq \ddot{\mathbb {H}}$. Now, let $(X,Y) \in \ddot{\mathbb {H}}$. By Theorem 3, there exists a complex Z such that Z collapses onto X and Z collapses onto Y. The collection $\ddot{\mathbb {K}}$ contains the collection $\langle \ddot{\mathbb {\triangle }}; \widetilde{\textsc {X}}, \widetilde{\textsc {T}} \rangle$. Thus, by Proposition 12, we have $(X,Z) \in \ddot{\mathbb {K}}$ and $(Y,Z) \in \ddot{\mathbb {K}}$. By $\langle \widetilde{\textsc {L}} \rangle$, it means that $(X,Y) \in \ddot{\mathbb {K}}$. $\Box$

9 Conclusion

In a previous work, it was shown that only five completions $\langle \widetilde{\textsc {X}} \rangle$, $\langle \widetilde{\textsc {Y}} \rangle$, $\langle \widetilde{\textsc {T}}\rangle$, $\langle \widetilde{\textsc {U}}\rangle$, and $\langle \widetilde{\textsc {L}}\rangle$, were sufficient to describe the whole collection $\ddot{\mathbb {X}}$ made of all acyclic pairs of complexes. Furthermore, it has been found that a subset of these completions permits to characterize the collection $\ddot{\mathbb {H}}$ made of all homotopic pairs.

In this paper, we show that another subset of these completions corresponds to a collection $\ddot{\mathbb {W}}$, the couples of which are linked by a contractibility relation. These couples, we called contractible pairs, may be generated by two local transforms, perforations and fillings, completed by collapses. We also show that a certain collection $\ddot{\mathbb {E}}$ provides an exact characterization of all collapsible pairs.

Thus, these five completions allow us to describe, in a unified framework, the four remarkable nested collections composed of all collapsible pairs, homotopic pairs, contractible pairs, and acyclic pairs. Not only these completions may act as generators of these collections, but also they provide structural and global properties of them.