Completions and Ramifications

Abstract

We investigate ramifications, which are simplicial complexes constructed with a very simple inductive property: if two complexes are ramifications, then their union is a ramification whenever their intersection is a ramification. We show that the collection of all ramifications properly contains the collection of all collapsible complexes and that it is properly contained in the collection of all contractible complexes. We introduce the notion of a ramification pair, which is a couple of complexes satisfying also an inductive property. We establish a strong relation between ramification pairs and ramifications. In particular, the collection of ramification pairs is uniquely determined by the collection of ramifications. Also we provide some relationships between ramification pairs, collapsible pairs, and contractible pairs.

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 simplicial complexes are simple homotopy equivalent if one of them may be obtained from the other by a sequence of elementary collapses and expansions.

Simple homotopy plays a fundamental role in combinatorial topology [1,2,3]. 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 [4,5,6].

In this paper, we investigate ramifications, which are simplicial complexes constructed with a very simple inductive property: if two complexes are ramifications, then their union is a ramification whenever their intersection is a ramification.

It could be seen that the collection of all trees satisfies the above property. Also, any complex of arbitrary dimension is a ramification whenever it is collapsible, i.e., whenever it reduces to a single vertex with a sequence composed solely of collapses.

Our main results include the following:

• We show that the collection $\mathbb {R}$ of all ramifications properly contains the collection $\mathbb {E}$ of all collapsible complexes. Also we show that $\mathbb {R}$ is properly contained in the collection $\mathbb {H}$ of all contractible complexes, i.e., all complexes that are homotopy equivalent to a single vertex.

• We introduce the notion of a ramification pair, which is a couple of complexes satisfying also an inductive property. We show there is a strong relation between the collection of all ramification pairs $\ddot{\mathbb {R}}$ and $\mathbb {R}$. In particular, $\ddot{\mathbb {R}}$ is uniquely determined by $\mathbb {R}$.

• We show that $\ddot{\mathbb {R}}$ properly contains the collection of all collapsible pairs, and that $\ddot{\mathbb {R}}$ is properly contained in the collection of all contractible pairs.

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, which allow us to formulate inductive properties (Sect. 4). We investigate the containment relations between the collections $\mathbb {E}$, $\mathbb {R}$, and $\mathbb {H}$ in Sect. 5. Then, we introduce the collection $\ddot{\mathbb {R}}$ of ramification pairs and give the fundamental relation between $\ddot{\mathbb {R}}$ and $\mathbb {R}$ (Sect. 6). In Sect. 7, we make clear the relations between $\ddot{\mathbb {R}}$, collapsible pairs, and contractible pairs. Note that the paper is self contained. Nevertheless, for the sake of place, several proofs are not included, these proofs may be found in an online archive [11].

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 finite simplicial complexes. Note that $\emptyset \in \mathbb {S}$ and $\{ \emptyset \} \in \mathbb {S}$, $\emptyset$ is the void complex, and $\{ \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 Simple Homotopy

We 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$.

Let $\alpha = \{\emptyset , \underline{\alpha }\}$ be an arbitrary vertex. We observe that $(\emptyset , \underline{\alpha })$ is a free face for $\alpha$. Thus $\alpha$ collapses onto $\emptyset$, that is, the void complex. It follows that a complex is contractible if and only if it is homotopic to a single vertex. Also a non-void complex is collapsible if and only if it collapses onto a single vertex.

Remark 1

We observe that a complex $X \in \mathbb {S}$, $X \not = \emptyset$, is an elementary collapse of a complex Z, if and only if we have $Z = X \cup \gamma D$ and $X \cap \gamma D = \gamma D^\circ$, where D, $D \not = \emptyset$, is a cell, and $\gamma$ is a vertex disjoint from D. See also [1], p. 247.

Let $X,Y \in \mathbb {S}$, and $\alpha$ be a vertex disjoint from $X \cup Y$. We can check that:

• 1) If $x,y \in X \setminus Y$, then (x, y) is a free pair for X iff (x, y) is a free pair for $X \cup Y$.

• 2) If $x \in X \setminus Y$ is a facet of X, then $(x, \underline{\alpha } \cup x)$ is a free pair for $\alpha X \cup Y$.

• 3) If $x,y \in X$, then 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$.

By induction, we have the following results which will be used in this paper.

Proposition 1

Let $X,Y \in \mathbb {S}$. The complex X collapses onto $X \cap Y$ if and only if $X \cup Y$ collapses onto Y.

Proposition 2

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

The complex $\alpha X \cup Y$ collapses onto $\alpha (X \cap Y) \cup Y$.

In particular, the complex $\alpha X$ collapses onto $\emptyset$. Thus any cone is collapsible.

Proposition 3

Let $X,Y \in \mathbb {S}$, $Z \preceq X$, let $\alpha$ be a vertex disjoint from $X \cup Y$.

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

In particular, if X is collapsible, then $\alpha X \cup Y$ collapses onto $X \cup Y$.

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 [7] for more details.

Let $\textbf{S}$ be a given collection and let $\mathcal {K}$ be an arbitrary subcollection of $\textbf{S}$. Thus, we have $\mathcal {K}\subseteq \textbf{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 {\textbf{K}}$ be a binary relation on $2^\textbf{S}$, thus $\scriptstyle {\textbf{K}}$ $\subseteq 2^\textbf{S} \times 2^\textbf{S}$. We say that $\scriptstyle {\textbf{K}}$ is finitary, if $\textbf{F}$ is finite whenever $(\textbf{F}, \textbf{G}) \in \; \scriptstyle {\textbf{K}}$.

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

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

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

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

Theorem 1

(from [7]). Let $\langle \textrm{K} \rangle$ be a completion on $\textbf{S}$ and let $\textbf{X} \subseteq \textbf{S}$. There exists, under the subset ordering, a unique minimal collection that contains $\textbf{X}$ and that satisfies $\langle \textrm{K} \rangle$.

If $\langle \textrm{K} \rangle$ is a completion on $\textbf{S}$ and if $\textbf{X} \subseteq \textbf{S}$, we write $\langle \textbf{X}; \textrm{K} \rangle$ for the unique minimal collection that contains $\textbf{X}$ and that satisfies $\langle \textrm{K} \rangle$. We say that $\langle \textbf{X}; \textrm{K} \rangle$ is a completion system and that $\textbf{X}$ is the starting collection of $\langle \textbf{X}; \textrm{K} \rangle$.

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

5 Ramifications

5.1 Definition

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

We define the two completions $\langle \textsc {R} \rangle$ and $\langle \textsc {D} \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 {R} \rangle$

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

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

We have the general result [7]:

A non-void complex is a dendrite iff it is acyclic in the sense of homology.

We set $\mathbb {R} = \langle \mathbb {C}; \textsc {R} \rangle$. Each element of $\mathbb {R}$ is a ramification. Thus, the collection $\mathbb {R}$ is the unique minimal collection that contains $\mathbb {C}$ and that satisfies the property $\langle \textsc {R} \rangle$. Also, the collection $\mathbb {R}$ is the very collection that may be obtained by starting from $\mathcal {K} = \mathbb {C}$, and by iteratively adding to $\mathcal {K}$ all the sets $S \cup T$ such that S, $T \in \mathcal {K}$ and $S \cap T$ $\in \mathcal {K}$.

Note that the notion of a ramification corresponds to the buildable complexes introduced by J. Jonsson [3]. Here, we have a formulation in terms of completions.

The collection of all cones provides a basic example of ramifications. If a cone $\alpha Z$ has more than one facet, then it may be split in two distinct cones $\alpha X$ and $\alpha Y$ such that $\alpha Z = \alpha X \cup \alpha Y$. Since $\alpha X \cap \alpha Y$ is a cone, and $\alpha Z$ is a cell whenever $\alpha Z$ has a single facet, it follows by induction that any cone is a ramification.

5.2 Ramifications and Collapsible Complexes

Let us denote by $\mathbb {E}$ the collection of all complexes X such that $\emptyset$ expands onto X, i.e., such that X is collapsible. This collection may be described by completions. See Sec. 6 of [7] and Sec. 8 of [10]. Now let us consider the alternative definition of an elementary collapse given in Remark 1. If $X \in \mathbb {S}$, $X \not = \emptyset$, is an elementary collapse of Z, then we have $Z = X \cup Y$, where Y and $X \cap Y$ are cones. Since cones are ramifications, and since the void complex is a ramification, we can again prove by induction that any collapsible complex is a ramification. Thus, we have $\mathbb {E} \subseteq \mathbb {R}$. See [7] and [10] (Sec. 8). See also [3] (Def. 3.14 and Prop. 5.17) where a slightly different definition of a collapsible complex is used.

The Bing’s house [13] is a classical example of an object that is contractible but not collapsible, see Fig. 1(a). This two dimensional object is made of two rooms. Two tunnels allow to enter to the upper room by the lower face, and to the lower room by the upper face. Two small walls are attached to the tunnels in order to make this object acyclic.

In [7], it was noticed that the Bing’s house B is a ramification. Let us consider the two complexes $B_1$ and $B_2$ of Fig. 1(b) and (c). We have $B = B_1 \cup B_2$. If B is correctly triangulated, then we can see that $B_1$, $B_2$, and $B_1 \cap B_2$ are all collapsible. Since $\mathbb {E} \subseteq \mathbb {R}$, these three complexes are ramifications. Thus, the Bing’s house B is a ramification. But the Bing’s house is not collapsible, in fact there is nowhere we can start a collapse sequence. In consequence, the inclusion $\mathbb {E} \subseteq \mathbb {R}$ is strict.

Fig. 1.

(a): A Bing’s house B with two rooms, (b): An object $B_1 \subseteq B$, (c): An object $B_2 \subseteq B$. We have $B = B_1 \cup B_2$, the object $B_1 \cap B_2$ is outlined in (b) and (c).

5.3 Ramifications and Contractible Complexes

Now, let us consider the collection $\mathbb {H}$ made of all contractible complexes. We have $\mathbb {H} \subseteq \mathbb {D}$, this inclusion is strict (see [10]).

It was shown (Prop. 5.17 of [3]) that any buildable complex (or any ramification) is contractible. The arguments given for the proof are based on the Hurewicz theorem (Th. 4.32 of [15]). It follows that these arguments do not allow to build an effective sequence of collapses and expansions that transform any ramification into the void complex. In fact, it is undecidable to determine whether a finite simplicial complex is contractible or not (for example see [16], Appendix). Thus, such an effective sequence cannot, in general, be given.

Fig. 2.

(a): The dunce hat, the three edges of the triangle have to be identified with the arrows, (b): a triangulation D of the dunce hat, (c): a subcomplex of D.

In the extension of this paper (Appendix A of [11]), we provide a direct proof that permits to build such a sequence. We illustrate an aspect of this proof with the decomposition $B = B_1 \cup B_2$ of the Bing’s house given Fig. 1.

Let $\alpha$ be a vertex disjoint from B. Since $B_1$ is collapsible, B expands onto the complex $C = \alpha B_1 \cup B_2$ (Proposition 3, by replacing collapses by expansions). Now, we can collapse C onto the complex $D = \alpha (B_1 \cap B_2) \cup B_2$ (Proposition 2). Since $B_1 \cap B_2$ is collapsible, the complex D collapses onto $B_2$ (Proposition 3), which is collapsible.

Thus, the sequence $B \nearrow \alpha B_1 \cup B_2 \searrow \alpha (B_1 \cap B_2) \cup B_2 \searrow B_2 \searrow \emptyset$ gives an homotopic deformation between B and $\emptyset$; the symbol $\nearrow$ stands for expansions and the symbol $\searrow$ for collapses. Now, let us consider a complex $B' = B'_1 \cup B'_2$ where $B'_1$ and $B'_2$ are two copies of B such that $B'_1 \cap B'_2$ is a ramification. The complex $B'$ is a ramification but, since $B'_1$ and $B'_2$ are not collapsible, the above sequence is no longer valid. Furthermore, this process may be iterated by considering two copies of $B'$, and so on. In the extension [11], we handle this problem by proposing an inductive construction which, at each step, allows us to perform the above sequence.

Thus, we have $\mathbb {R} \subseteq \mathbb {H}$. Are there contractible complexes that are not ramification? This question corresponds to a conjecture formulated by J. Jonsson [3] (Problem 5.21). We give a positive answer to this question in the Appendix B of the extension of this paper [11]. The counter-example is given by the dunce hat [14] which is another classical example of an object that is contractible but not collapsible, see Fig. 2(a). See also Appendix A of this paper where the contractibility of this object is shown. Note that we only proved that a specific triangulation of the dunce hat is not a ramification. This leaves open the question for any triangulation of this complex.

The following proposition summarizes the facts given in this section.

Proposition 4

We have $\mathbb {E} \subsetneq \mathbb {R} \subsetneq \mathbb {H} \subsetneq \mathbb {D}$.

6 Ramification Pairs

In the last section, we mentioned some previously published results related to ramifications. As far as we know these are the only ones that may be found in the literature. By providing counter-examples, and by giving an appropriate homotopic deformation, we also clarified the link between ramifications, collapsible and contractible complexes. Now, in order to achieve a better understanding of these objects, we will extend the collection $\mathbb {R}$ to a collection $\ddot{\mathbb {R}}$, which is composed of couples of complexes. It should be noted that the following completion $\langle \widetilde{\textsc {R}} \rangle$ has already been introduced in a previous paper [8]. Nevertheless, it was always associated with another completion (its dual), so that all the following results are new. Note that all the proofs of the results given in this section may be found in the extension [11].

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

We define the completion $\langle \widetilde{\textsc {R}} \rangle$ on $\ddot{\mathbb {S}}$: For any (S, T), $(S',T')$ in $\ddot{\mathbb {S}}$,

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

We set $\ddot{\mathbb {R}} = \langle \ddot{\mathbb {C}} \cup \ddot{\mathbb {I}}; \widetilde{\textsc {R}} \rangle$, where $\ddot{\mathbb {I}} = \{ (X,X) \; | \; X \in \mathbb {S} \}$.

Each couple of $\ddot{\mathbb {R}}$ is a ramification pair.

In fact, the collection $\ddot{\mathbb {R}}$ may be generated with a smaller starting collection. We have $\ddot{\mathbb {R}} = \langle \ddot{\mathbb {C}}^{\#}; \widetilde{\textsc {R}} \rangle$, where $\ddot{\mathbb {C}}^{\#} = \ddot{\mathbb {C}} \cup \{(\{\emptyset \}, \{\emptyset \}) \}$, see the extension [11].

Fig. 3.

Four couples (S, T), $(S',T')$, $(S \cap S', T \cap T')$, $(S \cup S', T \cup T')$, that are ramification pairs; S and $S'$ are two simple open curves, $S \cap S'$ is made of two vertices.

The four couples given in Fig. 3 correspond to the four couples appearing in the definition of the completion $\langle \widetilde{\textsc {R}} \rangle$. In this specific illustration, we observe that, if (X, Y) is one of these four couples, then Y collapses onto X (under an appropriate triangulation).

We introduce the notion of a $\varDelta$-form, the symbol $\varDelta$ corresponds to a binary relation over $\ddot{\mathbb {S}}$ and $\mathbb {S}$.

Let $(X,Y) \in \ddot{\mathbb {S}}$ and $Z \in \mathbb {S}$. We write $\varDelta (X,Y,Z)$ if there exists a vertex $\alpha$, disjoint from Y, such that $Z = \alpha X \cup Y$. In this case, we write $\alpha (X,Y)$ for the complex Z, and we say that $\alpha (X,Y)$ is a $\varDelta$-form. We also say that $\alpha (X,Y)$ is a $\varDelta$-form of (X, Y) or a $\varDelta$-form of Z.

If $Z \in \mathbb {S}$ and $\alpha$ is an arbitrary vertex, it may be seen that there exists a unique couple $(X,Y) \in \ddot{\mathbb {S}}$ such that $Z = \alpha (X,Y)$. We have:

$X = \{x \in Z \; | \; x \cap \underline{\alpha } = \emptyset$ and $x \cup \underline{\alpha } \in Z \}$ and $Y = \{x \in Z \; | \; x \cap \underline{\alpha } = \emptyset \}$.

The complex X is the so-called link of the face $\underline{\alpha }$ in Z, and Y is the so-called deletion of $\underline{\alpha }$ from Z, see [3]. Thus, we have:

$\alpha (X,Y) = \alpha (X',Y')$ if and only if $(X,Y) = (X',Y')$.

Note that we have $X = \emptyset$ and $Y = Z$ whenever $\alpha$ is disjoint from Z.

We now clarify the correspondence between $\ddot{\mathbb {R}}$ and $\mathbb {R}$ induced by $\varDelta$-forms:

• 1) If $(X,Y) \in \ddot{\mathbb {S}}$, then, up to a renaming of the vertex $\alpha$, the couple (X, Y) has a unique $\varDelta$-form $Z = \alpha (X,Y)$. Thus, up to this renaming, there is a unique complex in $\mathbb {S}$ which is the $\varDelta$-form of a couple in $\ddot{\mathbb {S}}$.

• 2) If $Z \in \mathbb {S}$, and for a given $\alpha$, there is a unique couple (X, Y) such that $Z = \alpha (X, Y)$. Now, for all possible choices of $\alpha$, we observe that there are precisely $k+1$ different such couples, where k is the number of vertices included in Z (we have to consider the case where $\alpha$ is disjoint from Z). Thus, in general, there are several different couples in $\ddot{\mathbb {S}}$ which are the $\varDelta$-forms of a complex in $\mathbb {S}$.

Proposition 5

Let $\alpha (X',Y')$ and $\alpha (X'',Y'')$ be two $\varDelta$-forms.

• 1) We have $\alpha (X' \cup X'',Y' \cup Y'') = \alpha (X',Y') \cup \alpha (X'',Y'')$.

• 2) We have $\alpha (X' \cap X'',Y' \cap Y'') = \alpha (X',Y') \cap \alpha (X'',Y'')$.

By induction on $\mathbb {R}$ and $\ddot{\mathbb {R}}$, Proposition 5 leads to the following relation between these two collections.

Theorem 2

Let $(X,Y) \in \ddot{\mathbb {S}}$ and let $Z \in \mathbb {S}$ such that $\varDelta (X,Y,Z)$.

We have $(X,Y) \in \ddot{\mathbb {R}}$ if and only if $Z \in \mathbb {R}$.

Replacing X by $\emptyset$ in the previous theorem, we obtain the corollary:

Corollary 1

We have $\mathbb {R} = \{X \in \mathbb {S} \; | \; (\emptyset , X) \in \ddot{\mathbb {R}} \}$.

Let us consider an arbitrary collection $\ddot{\mathbb {K}} \subseteq \ddot{\mathbb {S}}$. We define the kernel of $\ddot{\mathbb {K}}$ as the collection $\mathbb {K} = \{X \in \mathbb {S} \; | \; (\emptyset , X) \in \ddot{\mathbb {K}} \}$. We consider the two properties:

• If $(X,Y) \in \ddot{\mathbb {K}}$, then we have $Z \in \mathbb {K}$ whenever $\varDelta (X,Y,Z)$. ($\nabla$)

• If $Z \in \mathbb {K}$, then we have $(X,Y) \in \ddot{\mathbb {K}}$ whenever $\varDelta (X,Y,Z)$. ($\varDelta$)

We say that $\ddot{\mathbb {K}}$ is a $\nabla$-structure if $\ddot{\mathbb {K}}$ satisfies ($\nabla$).

We say that $\ddot{\mathbb {K}}$ is a $\varDelta$-structure if $\ddot{\mathbb {K}}$ satisfies both ($\nabla$) and ($\varDelta$).

Now, let us start from an arbitrary collection $\mathbb {K} \subseteq \mathbb {S}$.

We define $\ddot{\mathbb {K}}^+ = \{ (X,Y) \in \ddot{\mathbb {S}} \; | \; \alpha (X,Y) \in \mathbb {K}$ for some vertex $\alpha \}$.

By construction, the kernel of $\ddot{\mathbb {K}}^+$ is precisely $\mathbb {K}$ and $\ddot{\mathbb {K}}^+$ is a $\varDelta$-structure.

If $\ddot{\mathbb {K}} \subseteq \ddot{\mathbb {S}}$ and the kernel of $\ddot{\mathbb {K}}$ is $\mathbb {K}$, then we have $\ddot{\mathbb {K}} = \ddot{\mathbb {K}}^+$ whenever $\ddot{\mathbb {K}}$ is a $\varDelta$-structure. Thus, a $\varDelta$-structure is uniquely determined by its kernel.

Returning to the case of ramifications pairs, Theorem 2 shows that we have $\ddot{\mathbb {R}} = \ddot{\mathbb {R}}^+$. Thus, the kernel of $\ddot{\mathbb {R}}$ is precisely the collection $\mathbb {R}$, and the collection $\ddot{\mathbb {R}}$ is a $\varDelta$-structure.

Informally, since $\ddot{\mathbb {R}}$ is a $\varDelta$-structure, we recover a property that is satisfied by the neighborhood (the link) of each vertex of an arbitrary ramification. If we pick any vertex $\alpha$ in a ramification Z (for example a Bing’s house), then the couple (X, Y) such that $Z = \alpha (X,Y)$ may be recursively decomposed by $\langle \widetilde{\textsc {R}} \rangle$, until an elementary couple.

7 Ramifications and the Five Completions

In previous works, we tried to build a framework, based on completions, for unifying certain notions of combinatorial topology. It turns out that five completions, acting on $\ddot{\mathbb {S}}$, appear to be particularly relevant for this purpose. In this section, we wish to relate ramifications to these completions.

We recall the five completions (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$

The largest collection is obtained by considering all the five completions.

Let $\ddot{\mathbb {D}} = \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 {D}}$ is a dyad or an acyclic pair.

In [8], we proved that $\ddot{\mathbb {D}}$ is a $\varDelta$-structure and that the kernel of $\ddot{\mathbb {D}}$ is precisely the collection $\mathbb {D}$ of dendrites.

In this section, we focus our attention on collections based on a subset of the five above completions. These completions are chosen because the kernel of $\ddot{\mathbb {D}}$ is $\mathbb {D}$, which corresponds to the remarkable collection made of all acyclic complexes. In particular, it includes all contractible complexes. We will use the following fact.

Proposition 6

Let $\ddot{\mathbb {K}}$ be a $\nabla$-structure and $\ddot{\mathbb {L}}$ be a $\varDelta$-structure. Let $\mathbb {K}$ and $\mathbb {L}$ be the kernels of $\ddot{\mathbb {K}}$ and $\ddot{\mathbb {L}}$, respectively. If $\mathbb {K} \subseteq \mathbb {L}$, then we have $\ddot{\mathbb {K}} \subseteq \ddot{\mathbb {L}}$.

Furthermore, if $\mathbb {K} \subsetneq \mathbb {L}$, then $\ddot{\mathbb {K}} \subsetneq \ddot{\mathbb {L}}$.

Proof

Suppose $\mathbb {K} \subseteq \mathbb {L}$. Let $(X,Y) \in \ddot{\mathbb {K}}$. Since $\ddot{\mathbb {K}}$ is a $\nabla$-structure, $\alpha (X,Y) \in \mathbb {K}$. Thus $\alpha (X,Y) \in \mathbb {L}$. But since $\ddot{\mathbb {L}}$ be a $\varDelta$-structure, we have $(X,Y) \in \ddot{\mathbb {L}}$.

By the very definition of a kernel, if $\ddot{\mathbb {K}} = \ddot{\mathbb {L}}$, then we must have $\mathbb {K} = \mathbb {L}$. $\square$

7.1 Ramification Pairs and Collapsibility

We denote by $\ddot{\mathbb {E}}$ the collection of all couples $(X,Y) \in \ddot{\mathbb {S}}$ such that the complex Y collapses onto X. Thus, the kernel of $\ddot{\mathbb {E}}$ is precisely the collection $\mathbb {E}$ made of all collapsible complexes. It has been shown [10] that $\ddot{\mathbb {E}}$ has an exact characterization with a subset of the five above completions. We have $\ddot{\mathbb {E}} = \langle \ddot{\mathbb {\triangle }}; \widetilde{\textsc {X}}, \widetilde{\textsc {T}} \rangle$, where $\ddot{\mathbb {\triangle }}$ is the collection composed of all all couples of cones $(\alpha X, \alpha Y)$, with $(X,Y) \in \ddot{\mathbb {S}}$.

Let $(X,Y) \in \ddot{\mathbb {E}}$. Let $Z = \alpha (X,Y)$. Since Y collapses onto X, the complex $Z = \alpha X \cup Y$ collapses onto the cone $\alpha X$, which is collapsible. Thus Z is collapsible, i.e., $Z \in E$. It means that $\ddot{\mathbb {E}}$ is a $\nabla$-structure. Since $\mathbb {E} \subsetneq \mathbb {R}$ (Proposition 4) then, by Proposition 6, we have $\ddot{\mathbb {E}} \subsetneq \ddot{\mathbb {R}}$.

Now, we consider the collection $\ddot{\mathbb {E}}^+$, which is a $\varDelta$-structure. By definition of a collection $\ddot{\mathbb {K}}^+$, a couple (X, Y) is in $\ddot{\mathbb {E}}^+$ if and only if $\alpha (X,Y) = \alpha X \cup Y$ is collapsible. Thus, the kernel of $\ddot{\mathbb {E}}^+$ is also the collection $\mathbb {E}$ and, by Proposition 6, we have $\ddot{\mathbb {E}} \subseteq \ddot{\mathbb {E}}^+$. One may ask whether we have $\ddot{\mathbb {E}} = \ddot{\mathbb {E}}^+$. A positive answer would imply that $\ddot{\mathbb {E}}$ is a $\varDelta$-structure. In fact this equality does not hold.

We have the following counter-example. Let Y be the complex depicted Fig. 2(c), and let X be the closed curve that is outlined. It may be seen that Y collapses onto X. The first steps of a possible sequence of elementary collapses are depicted by arrows. Let $X' = X \cup \{ \{ 1 \}, \{1,3 \} \}$, let $\alpha$ be a new vertex, and let $Z = \alpha X' \cup Y$. We observe that $( \{ \alpha , 1 \}, \{ \alpha , 1 , 3 \})$ is a free pair for Z. Thus Z collapses onto $Z' = \alpha X \cup Y$. But, since Y collapses onto X, $Z'$ collapses onto $\alpha X$, thus Z collapses onto $\alpha X$. Since the cone $\alpha X$ is collapsible, the complex Z is collapsible. Thus $\alpha (X',Y) \in \mathbb {E}$, it means that $(X', Y) \in \ddot{\mathbb {E}}^+$. But Y does not collapse onto $X'$ since there is nowhere to start the collapse. Thus $(X', Y) \not \in \ddot{\mathbb {E}}$.

In consequence the inclusion $\ddot{\mathbb {E}} \subseteq \ddot{\mathbb {E}}^+$ is strict. The collection $\ddot{\mathbb {E}}$ is a $\nabla$-structure but not a $\varDelta$-structure.

Again, since the kernel of $\ddot{\mathbb {E}}^+$ is a proper subset of the kernel of $\ddot{\mathbb {R}}$, by Proposition 6, we may assert that $\ddot{\mathbb {E}}^+ \subseteq \ddot{\mathbb {R}}$ and that this inclusion is strict. Thus, starting from $\ddot{\mathbb {E}}$, we have build a new collection $\ddot{\mathbb {E}}^+$ which allows us to be closer to $\ddot{\mathbb {R}}$.

7.2 Ramification Pairs and Contractibility

We consider the collection $\ddot{\mathbb {W}}$ such that a couple (X, Y) is in $\ddot{\mathbb {W}}$ if and only if $\alpha (X,Y) = \alpha X \cup Y$ is contractible. By construction $\ddot{\mathbb {W}}$ is a $\varDelta$-structure, the kernel of $\ddot{\mathbb {W}}$ is precisely the collection $\mathbb {H}$ made of all contractible complexes. Again, it has been shown (Theorem 5 of [10]) that $\ddot{\mathbb {W}}$ admits an exact characterization with a subset of the five above completions. We have $\ddot{\mathbb {W}} = \langle \ddot{\mathbb {C}}; \widetilde{\textsc {X}}, \widetilde{\textsc {Y}}, \widetilde{\textsc {T}}, \widetilde{\textsc {U}} \rangle$.

We see that $\ddot{\mathbb {W}} \subseteq \ddot{\mathbb {D}}$, this inclusion is strict [10].

Since $\mathbb {R}$ is a proper subset of $\mathbb {H}$, by Proposition 6, we have $\ddot{\mathbb {R}} \subseteq \ddot{\mathbb {W}}$, and this inclusion is strict.

7.3 Properties Related to the Five Completions

The following theorem summarizes the results given above.

Theorem 3

We have $\ddot{\mathbb {E}} \subsetneq \ddot{\mathbb {E}}^+ \subsetneq \ddot{\mathbb {R}} \subsetneq \ddot{\mathbb {W}} \subsetneq \ddot{\mathbb {D}}$.

We emphasize that the collections $\ddot{\mathbb {E}}$, $\ddot{\mathbb {W}}$, $\ddot{\mathbb {D}}$, have an exact characterization based on the five completions. It means that these collections are fully described by global properties. The collections $\ddot{\mathbb {E}}$ and $\ddot{\mathbb {E}}^+$ are closely related since they have the same kernel $\mathbb {E}$ which is made of all collapsible complexes. Also it is worth pointing out that each couple in the collections $\ddot{\mathbb {E}}$, $\ddot{\mathbb {E}}^+$, $\ddot{\mathbb {W}}$, may be obtained by a sequence of local operations. Collapses/expansions and perforations/fillings (introduced in [10]) are sufficient for that purpose.

In the above sections, completions appeared as components of certain completion systems $\langle \textbf{X}; \textrm{K} \rangle$. Here, we consider a completion as a property by itself.

Proposition 7

The collection $\ddot{\mathbb {R}}$ satisfies the properties $\langle \widetilde{\textsc {X}} \rangle$ and $\langle \widetilde{\textsc {U}} \rangle$.

Proof

• 1) Let S, $T \in \mathbb {S}$ such that $(S \cap T,T) \in \ddot{\mathbb {R}}$. Since $\ddot{\mathbb {I}} \subseteq \ddot{\mathbb {R}}$, we have $(S \cap T,T)$, (S, S), $(S \cap T,S \cap T)$ $\in \ddot{\mathbb {R}}$. Thus, by $\langle \widetilde{\textsc {R}} \rangle$, we obtain $(S, S \cup T) \in \ddot{\mathbb {R}}$; the collection $\ddot{\mathbb {R}}$ satisfies $\langle \widetilde{\textsc {X}}\rangle$.

• 2) Let $(R,S),(S,T),(R,T) \in \ddot{\mathbb {S}}$ such that $(R,S) \in \ddot{\mathbb {R}}$ and $(R,T) \in \ddot{\mathbb {R}}$. Since $\ddot{\mathbb {I}} \subseteq \ddot{\mathbb {R}}$, we have (R, T), (S, S), $(R \cap S = R,T \cap S =S)$ $\in \ddot{\mathbb {R}}$. Thus, by $\langle \widetilde{\textsc {R}} \rangle$, we obtain $(S,T) \in \ddot{\mathbb {R}}$; the collection $\ddot{\mathbb {R}}$ satisfies $\langle \widetilde{\textsc {U}}\rangle$. $\square$

Now we give two counter-examples which show that the collection $\ddot{\mathbb {R}}$ does not satisfy the properties $\langle \widetilde{\textsc {L}}\rangle$ and $\langle \widetilde{\textsc {T}}\rangle$.

The complex D represents the triangulation of the dunce hat given Fig. 2(b).

• 1) The complex D is contractible. By Theorem 5 of [1] (and also by Proposition 6 of [9]), there exists Y such that Y collapses onto D and Y is collapsible. It follows that $(D,Y) \in \ddot{\mathbb {R}}$ and $(\emptyset , Y) \in \ddot{\mathbb {R}}$. But, since D is not a ramification, we have $(\emptyset ,D) \not \in \ddot{\mathbb {R}}$. Thus $\ddot{\mathbb {R}}$ does not satisfy $\langle \widetilde{\textsc {L}}\rangle$.

• 2) Let Y be the complex depicted Fig. 2(c), and let X be the closed curve that is outlined. We have pointed out, in Sect. 7.1, that Y collapses onto X. Let $X' = X \cup \{ \{ 1 \}, \{1,3 \} \}$. We see that $X'$ collapses onto X. Thus, $(X, Y) \in \ddot{\mathbb {R}}$, $(X, X') \in \ddot{\mathbb {R}}$. Since $\ddot{\mathbb {R}}$ satisfies $\langle \widetilde{\textsc {U}} \rangle$, we have $(X', Y) \in \ddot{\mathbb {R}}$. Let $\gamma$ be the vertex corresponding to the label “1". We have $\gamma X \cap Y = X'$. Since $\ddot{\mathbb {R}}$ satisfies $\langle \widetilde{\textsc {X}} \rangle$, we obtain $(\gamma X, \gamma X \cup Y) \in \ddot{\mathbb {R}}$. But $D = \gamma X \cup Y$. We obtain $(\gamma X, D) \in \ddot{\mathbb {R}}$. Since $\gamma X$ is a cone, we have $(\emptyset , \gamma X) \in \ddot{\mathbb {R}}$. But we have not $(\emptyset , D) \in \ddot{\mathbb {R}}$. Thus $\ddot{\mathbb {R}}$ does not satisfy $\langle \widetilde{\textsc {T}}\rangle$.

Thus, we proved the following. Note that the question remains open for the property $\langle \widetilde{\textsc {Y}} \rangle$.

Proposition 8

The collection $\ddot{\mathbb {R}}$ satisfies none of the properties $\langle \widetilde{\textsc {L}} \rangle$ and $\langle \widetilde{\textsc {T}} \rangle$.

8 Conclusion

In this paper, we extended the collection $\mathbb {R}$ of ramifications to a collection $\ddot{\mathbb {R}}$ of ramification pairs. We followed an approach developed in earlier papers, where we make a relation between a collection $\ddot{\mathbb {K}}$ of couple of complexes and a collection $\mathbb {K}$ of complexes; $\mathbb {K}$ is the kernel of $\ddot{\mathbb {K}}$ and $\ddot{\mathbb {K}}$ is a structure on $\mathbb {K}$.

It’s turn out that $\ddot{\mathbb {R}}$ has a noticeable property with respect to its kernel $\mathbb {R}$. In particular $\ddot{\mathbb {R}}$ is uniquely determined by $\mathbb {R}$.

We made a comparison between $\ddot{\mathbb {R}}$ and two others collection $\ddot{\mathbb {E}}$ and $\ddot{\mathbb {W}}$. The kernel $\mathbb {E}$ of $\ddot{\mathbb {E}}$ corresponds to collapsible complexes and the kernel $\mathbb {H}$ of $\ddot{\mathbb {W}}$ consists of all contractible complexes. We showed that $\ddot{\mathbb {E}} \subsetneq \ddot{\mathbb {R}} \subsetneq \ddot{\mathbb {W}}$.

The collection $\ddot{\mathbb {E}}$ is not uniquely determined by $\mathbb {E}$. Thus, from $\mathbb {E}$, we built an extension $\ddot{\mathbb {E}}^+$ of $\ddot{\mathbb {E}}$. We showed that $\ddot{\mathbb {E}} \subsetneq \ddot{\mathbb {E}}^+ \subsetneq \ddot{\mathbb {R}}$. Thus, starting from $\ddot{\mathbb {E}}$, we obtained a new collection $\ddot{\mathbb {E}}^+$ which allows us to be closer to $\ddot{\mathbb {R}}$.

Appendix

In this appendix, we present a sequence of expansions and collapses which shows the contractibility of the dunce hat. We give this sequence for the reader who wants to better understand this object which is used several times in this paper for crucial counter-examples.

Let D be the triangulation of the dunce hat of Fig. 2(b). Let X be the cell whose facet is the set $\{3,5,6 \}$, thus $X \cap D$ is the closed curve that is highlighted in (c). Let $\gamma$ be the vertex corresponding to the label “1”, and let $E = \gamma X \cup D$.

The pair $( \{3,5,6\}, \{ \gamma , 3, 5 ,6 \})$ is a free pair for E, thus D is an elementary collapse of E. Let F be the complex given Fig. 2(c) and let $G = F \cup X$. It may be seen that E collapses onto G. First we remove the pair $( \{1,3,5\}, \{1,3,5,6\})$, then the pair $(\{ 1,5 \}, \{1,5,6 \})$, then the pair $( \{ 1,6 \}, \{1,6,3\}$. Now we observe that the complex G collapses onto the cell X, the first steps of a collapse sequence are represented Fig. 2(c). Since X is collapsible, the following sequence shows the contractibility of D:

$$D \nearrow E \searrow G \searrow X \searrow \emptyset $$