Multivalued Maps As a Tool in Modeling and Rigorous Numerics

Tomasz Kaczynski^{∗} Département de mathématiques Université de Sherbrooke

April 10, 2008

Abstract

Applications of the fixed point theory of multivalued maps can be classified into several areas: (1) Game theory and mathematical economics; (2) Discontinuous differential equations and differential inclusions; (3) Computing homology of maps; (4) Conley index methods in chaotic dynamics; (5) Digital imaging and computer vision. We briefly recall the history of the most classical and well developed areas of applications (1) and (2), where a multivalued map is used as a generalization of a single-valued continuous map, and we survey the more recent applications (3), (4), and (5), where a multivalued map plays a role of a numerical tool.

Contents

1 Introduction: A brief history of mv maps 2 1.1 MV maps as generalizations . . . . . . . . . . . . . . . . . . . 3 1.2 MV maps as approximations . . . . . . . . . . . . . . . . . . . 5

2 Cubical sets and maps 9

3 Homology of maps 11 3.1 Chain selector approach . . . . . . . . . . . . . . . . . . . . . 11 3.2 Graph projection approach . . . . . . . . . . . . . . . . . . . . 14

4 Chaotic dynamics 15

5 Digital imaging 20

∗supported by the NSERC of Canada discovery grant

1 Introduction: A brief history of mv maps

A multivalued map (shortly, an mv map) F : X\overrightarrow{→}Y is a function from a set X to 2^{Y}, the power set of Y. If A ⊂ X, we denote by F (A) the union ⋃{F (x) : x ∈ A} ⊂ Y and not a subset of 2^{Y}. The graph of F is the set

Gr(F) := {(x, y) ∈ X × Y | y ∈ F (x)}.

The inverse map F^{−1} : Y \overrightarrow{→}X is defined by the property

x ∈ F^{−1}(y) ⟺ y ∈ F (x).

Consequently, given A ⊂ Y, F^{−1}(A) = {x ∈ X : F (x) ∩ A ≠ ∅}.

Given F : X\overrightarrow{→}Y where X ⊂ Y, a fixed point of F is a point x ∈ X with x ∈ F (x). Given a positive integer n, F^{n} denotes the n’th superposition of F defined recursively by F^{n}(x) := F (F^{n−1}(x)). A periodic point of F is a fixed point of F^{n} for some n.

If X and Y are topological spaces, there are two natural extensions of the concept of continuity to the context of mv maps: F is upper semicontinuous, shortly (usc), if F^{−1}(A) is closed for any closed A ⊂ Y or, equivalently, if the set {x ∈ X | F (x) ⊂ U} is open for any open U ⊂ Y. It is called lower semicontinuous, shortly (lsc), if the set F^{−1}(U) is open for any open U ⊂ Y. If F is single-valued (i.e. its values are singletons so it can be viewed as a map F : X → Y) and either definition is equivalent to the continuity. An advantage of usc maps over lsc maps is that, under some additional compactness assumptions, their graphs are closed.

We shall briefly discuss the history of mv maps from the perspective of the author’s studies and contributions to this area, focusing on their applications rather than on the theory. We divide those applications into two groups. In classical applications, an mv map F is used as a generalization of a singlevalued continuous map f aimed at problems where that first kind of maps is insufficient. The properties of mv maps required for those applications are proved by approximating them with single-valued maps. In more recent applications described next and surveyed in a greater detail in subsequent sections, an mv map F plays a role of a numerical tool, namely, a finitely representable enclosure of a continuous single-valued map f which permits solving problems concerning f. Thus the relation between a single-valued and mv map is reversed: This is now a continuous map which is approximated by mv maps. Also the approach to the selection property is reversed: A lot of effort in the study of mv lsc maps goes to proving the existence of their continuous single-valued selections under additional assumptions on their values, e.g. assuming that they convex or aspherical. A pioneer result of that type is the Michael Selection Theorem [62]. In our context, we don’t need to prove the existence of a continuous selection: by construction of F, our initial f is a selection of F.

1.1 MV maps as generalizations

The fixed point theory of multivalued maps goes back to works of von Neuman [80], Kakutani [57], Eilenberg-Montgomery [21], and Ky Fan [24] in the context of equilibrium problems in game theory and market economy [6]. A model example of such an application is the Nash Equilibrium Theorem [70]. Most commonly, it is derived from minimax inequalities (see [6, 11]), but we follow here the proof based on the Ky-Fan fixed point theorem given in [55], the author’s isolated contribution to this topic.

Consider n compact convex subsets K_{i} of a locally convex space 𝔼, K := K_{1} × K_{2} × ⋯ K_{n}, and n continuous functions f_{i} : K → ℝ such that the set

{y ∈ K_{i} | f_{i}(x_{1}, …, x_{i−1}, y, x_{i+1}, … x_{n}) ≥ r}

is convex for any r ∈ ℝ and any x ∈ K. In game theory, the set K_{i} is interpreted as the set of possible strategies of the i’th player and f_{i} is his gain function. Let

K_{−i} := K_{1} × ⋯ × K_{i−1} × K_{i+1} × ⋯ × K_{n},
x_{−i} := (x_{1}, …, x_{i−1}, x_{i+1}, …, x_{n}).

A strategy y ∈ K_{i} permits the i’th player maximize his gain under the condition that the remaining players have chosen their strategies x_{−i} ∈ K_{−i} if and only if

f_{i}(x_{1}, …, x_{i−1}, y, x_{i+1}, … x_{n}) = max_{z∈K_{i}} f_{i}(x_{1}, …, x_{i−1}, z, x_{i+1}, … x_{n}).

Denote the set of such gaining strategies y ∈ K_{i} by M_{i}(x_{−i}). A Nash equilibrium is a set of strategies \overline{x} ∈ K satisfying

\overline{x}_{i} ∈ M_{i}(\overline{x}_{−i}), i = 1, 2, … n.

This is equivalent to the fixed point problem \overline{x} ∈ F (\overline{x}) for the mv map F : K\overrightarrow{→}K given by

F (x) := M_{1}(x_{−1}) × M_{2}(x_{−2}) × ⋯ × M_{n}(x_{−n}).

The assumptions on f_{i} imply that F is an usc map with compact convex values, hence the existence of its fixed point is guaranteed by Ky-Fan Fixed Point Theorem [24]. The hypotheses on the set K and the space 𝔼 can be generalized as in [55, 47] or further using [9].

From the point of view of social recognition, game theory is perhaps the most successful area of applications of mv maps because it resulted in the unique case of the Nobel price granted to a mathematician, John Nash in 1994, for its impact in economics. Moreover, the Nash equilibrium theorem is perhaps the only theorem explicitly stated in a Hollywood-made film (Beautiful Mind). On the other hand, game theory has received critics that its results on equilibriums are mostly static: they enhance understanding conditions under which equilibrium may be achieved but do not tell how to construct a process starting from a non-equilibrium point and convergent to equilibrium solution. Early attempts of computing fixed points of mv maps are commented further. In the last decade, the emergence of internet auctioning and pricing has induced progress in computer implementations of this theory [71], but it seems that there is still little interaction between game theory and dynamical systems communities. An author’s wish is that perhaps the development of mv maps as a tool in discrete dynamics, discussed later on, could possibly become helpful also in this area.

The incorporation of algebraic topology methods in the fixed point theory of multivalued maps was initiated by Eilenberg and Montgomery in [21] and developed further by Granas [40, 41, 43] and Jaworowski [45, 46] in 1959. Two generations of their followers continued to develop degree and index theories for various classes of mv maps. There is a vast bibliography on this topic in [42] and in [38]. Same of the early (1960s to 1970s) contributions are those of Browder [14], Ma [59], Gorniewicz [36], Fitzpatrick and Petryshyn [26], more recent ones can be found e.g. in [10, 28, 30, 35, 39, 58]. The initial condition of the convexity of the values F (x) assumed in Kakutani and Ky Fan papers is now generalized to various types of contractibility or acyclicity conditions, and compactness assumptions are partially relaxed.

Algorithms computing fixed points of continuous and multivalued maps go back to the works of Todd [78], Allgower and Georg [1, 2]. Since smooth methods are not available in the context of mv maps, the main technique is based on the Browder continuation theorem [13] and simplicial methods, which amount to construction of paths of simplices by reflection in a face through which a “Browder path” exits the simplex. Unfortunately, the computational complexity of those algorithms is much higher than of those based on smooth Newton-Ralphson methods, hence the practical implementation of algorithms computing fixed points had to wait for the current progress in computer science. We refer to the previously mentioned [71].

The mainstream of applications of mv maps in 1980s to 1990s has been initially motivated by the problem of differential equations (DEs) with discontinuous right-hand sides which gave birth to the existence theory of differential inclusions (DIs). Here is a simple model for this type of application. Consider the initial value problem

u′(t) = f(t, u), a.e. t ∈ I = [−a, a], u(0) = u_{0}.  (1)

If f : I × ℝ → ℝ is discontinuous with bounded jumps, measurable in t, one looks for solutions in the sense of Filippov [25] which are solutions to the differential inclusion

u′(t) ∈ φ(t, u), a.e. t ∈ I, u(0) = u_{0},  (2)

where

φ(t, x) = [lim inf_{y→x} f(t, y), lim sup_{y→x} f(t, y)].  (3)

One next defines the multivalued Nemystkii operator N_{φ} : 𝕃^{1}\overrightarrow{→}𝕃^{1} on the space of integrable functions on I by the formula

N_{φ}(u)(t) := {v ∈ 𝕃^{1} | v(t) ∈ φ(t, u(t)) a.e. t}.

One proves that N_{φ} is usc with non-empty convex values. Next, problem (2) is reduced to the fixed point problem u ∈ F (u) where F : 𝕃^{1}\overrightarrow{→}𝕃^{1} is given by F := N_{φ} ∘ L^{−1} where L^{−1} is the inverse of the derivative operator Lu = u′ given by

L^{−1}(v)(t) := u_{0} + ∫_{0}^{t} v(s) ds.

Finally, a variety of fixed point theorems for mv maps with non-empty convex values in functional spaces is available to conclude the existence of a solution. We used a first order DE as a model for simplicity of presentation but this approach is most commonly used with respect to second order boundary value problems for ODEs or PDEs. This approach can be generalized to systems of DEs in ℝ^{d} by replacing the formula (3) defining φ with the convex hull of the set of limit points of f(t, y) as y → x. The library of literature on this topic is huge, so we just point out [15, 22, 29, 30, 33, 37, 48, 49, 73] as examples, and also refer to the monographs [7, 18, 38] and bibliography therein. Note that DIs such as (2) may serve not only studying discontinuous DEs but also continuous implicit DEs of the type

y′′ = g(t, y, y′, y′′),

see, for example [23, 34, 48, 72], and for studying bifurcation problems for implicit DEs with delays [56]. The dynamical approach to systems of DEs of type (2) distinct from functional analysis approach is developed in [66], and a method of proving chaos for systems of discontinuous DEs is proposed in [19].

1.2 MV maps as approximations

In all applications discussed until now, mv maps appeared as generalizations of continuous single-valued maps. In 1990s, new applications of the Conley index theory [16, 66, 74] to rigorous computer-assisted proofs in chaotic dynamics [63, 64] exposed mv maps in an entirely different light. Those maps became a rigorous numerical tool for solving problems concerning continuous single-valued maps. Moreover, it appears that this philosophy is applicable to a variety of other problems related to computation of homology maps and to implementation of homological fixed point theorems. We now discuss the general philosophy of this approach and in Section 3.2 we show concrete applications.

Consider a continuous map f : X → Y, where hypotheses on X and Y can be stated later. Let M be a class of mv maps F : X\overrightarrow{→}Y satisfying some additional assumptions, and which contains single-valued-continuous maps. An mv map G is a submap of F if G(x) ⊂ F (x) for all x ∈ X. In particular, if f is a single-valued map which is a submap of F, it is called a selector of F and F is called its mv representation. A property P of mv maps is called inheritable in the class M if it carries over from F ∈ M to all submaps G of F which are in M. In particular, it carries over to single-valued selections f of F. This concept is due to Mrozek [68].

The clue in applications of mv maps to chaotic dynamics is that dynamical concepts, discussed in Section 4, such as isolating neighborhood of F, index pair for F and N, disjoint decomposition of an index pair, transition graph and transition matrix, are inheritable properties. For example an index pair constructed for F is also an index pair for its single-valued continuous selection f.

A reader used to view mv maps as generalizations of single-valued maps might ask

Why do wish to exchange the classical study of dynamics of f for that of a more general class of maps, if the single-valued dynamics is complicated enough?

Figure 1: MV cubical representation of a continuous function f.

We claim that it is the opposite: The dynamics of F may be simpler! The idea is illustrated in Figure 1. First, in most of applications to dynamics, f is a Poincaré map which cannot be explicitly computed, we only know how to find its arbitrary close approximations. If X is a cubical set defined in Section 2, a natural approach is to choose a sufficiently fine grid in X and construct a so called mv cubical representation F of f covering the graph of f with finite union of cubes in the product space. This is a finitely represented thus a combinatorial object, so associated structures from the theory of dynamical systems such as isolating neighborhoods and index pairs of F are computable by explicit algorithms. Since these structures are inheritable, the computation is valid for f.

Next, note that the fixed point property is not inheritable. However, if M is a class of usc mv maps with non-empty acyclic values, then, for example, the property

• The Lefschetz number L(F) of F is non-zero.

(see Theorem 4.1, Section 4) is inheritable because, as we will see it in Section 3, any acyclic valued submap of F induces the same homomorphism in homology as F. In particular, if L(F) ≠ 0 and f is a selection of F, then L(f) ≠ 0, hence f has a fixed point. Again, one may ask

Why do we want to reduce an easy problem of finding the homology of f to a more general problem of finding the homology of an mv map F?

In Section 3, we show that it is the opposite: The homology map F_{∗} of F may be easier to compute! A mv cubical representation F of f used for constructing isolating neighborhoods and index pairs is a combinatorial object, so it is not surprising that there is an explicit algorithm computing its homology map F_{∗}, provided we fix the grid scale so that the values of F are acyclic. Moreover, the same F_{∗} serves computing the Conley index for F [50, 52] and, consequently, for f, because the property

• C(S) is the Conley index of S, where S = Inv_{F} (N),

is inheritable.

In Section 5, we outline the most recent advances [3, 4] in topological analysis of digital images and multidimensional data sets inspired by discrete multivalued dynamical systems. The object of the study is a scalar function f : X → ℝ on a multidimensional data set X. The goal is to extract features which help to understand measured data and allow to represent it in a structure that is easy to process. In the case of a two-dimensional data set X, f can be geometrically interpreted as a height field. The features of interest are critical points of f, that is, peaks, pits, and saddles. Once the critical points are extracted, different techniques are used to analyze relationships between them and to trace structures such as ridge and ravine lines, and isolines. In the case of data of higher dimensions, the geometric interpretation of critical points is more complex but those points play equally important role in further investigation, such as the construction of the level Figure 2: A graphical display of the graph returned by the MCG algorithm. White is the highest value of f and black is the lowest. Three types of nodes corresponding to minima, maxima, and saddles are displayed at centers of critical regions. The surrounding black area is the global minimum and its connections are not displayed.

sets given by f = c. The smooth Morse theory [61] has inspired researchers in imaging science, however, in its rigorous applications such as [20], one spends a lot of effort on forcing, by local deformation of data, the main hypothesis of the Morse theory stating that critical points of f must be isolated and non-degenerate. This way one adjusts the finite input to the theory, with the aim at validating practical implementations. There is a discrete Morse index theory due to Forman [27], but it also deforms the data, and its goals are different than those in the image analysis. In [3, 4], an effort is made to establish a discrete analogy of the Morse theory for a function f defined on pixels (mathematically, elementary cubes) while keeping the original geometry, that is, without forcing the isolation and non-degeneracy of critical points. Following e.g. [82] where critical regions of continuous functions were considered, we want to introduce such regions on the discrete data level, considering for example surfaces of lakes as local minima, and craters of volcanos (thus, sets with the topology of a circle) as local maxima.

The main results obtained in [3, 4] are the algorithms detecting and classifying critical components, and constructing the so-called Morse connections graph , whose nodes are critical components and edges display the existence of trajectories connecting them. A computer experimentation was done in [4] on planar images, an example of output is shown at Figure 2.

There are some related open questions yet to be answered. One is related to the robustness of the construction with respect to the changes of scale. Another one is related to extensions of the Maxwell-Euler formula, often used as in digital imaging as a “quality check”, in the context of the discussed work.

2 Cubical sets and maps

We first describe the topological structure we shall work with. In numerical analysis and geometric modeling one considers representations of the space ℝ^{d} by various types of polyhedral grids which are particular cases of cellular complexes. One may often limit considerations to cubical grids. With appropriate units we may assume here that each cube is unitary that is it has sides of length 1 and vertices with integer coordinates. When a passage to a finer grid is necessary, we shall consider the rescaling isomorphisms x ↦ kx, k ∈ ℤ, on a unit grid rather than partitions to fractional grids.

An elementary cube Q is a finite product

Q = I_{1} × I_{2} × ⋯ × I_{d} ⊂ ℝ^{d}

where I_{i} is an interval of the form I = [k, k + 1] or I = [k, k] for some k ∈ ℤ. For short, [k] := [k, k]. The corresponding elementary cell is the set

Q^{∘} := I^{∘}_{1} × I^{∘}_{2} × … × I^{∘}_{d}.

where [k, k + 1]^{∘}:= (k, k + 1) and [k]^{∘}:= [k]. The set of all elementary cubes in ℝ^{d} is denoted by K and those of dimension k by K_{k}. Given P, Q ∈ K, if P ⊂ Q, then P is a face of Q. In the analysis of digital images, we interpret pixels as elements of K_{max} := K_{d}, that is, as elementary cubes of maximal dimension. The faces of a pixel are not distinguished in a digital image but we need to consider them to extract topological information.

A set Y ⊂ ℝ^{d} is representable if it is a finite union of elementary cells. A cubical set is a closed representable set, equivalently, a finite union of elementary cubes. Given a cubical set X, we let K(X) := {Q ∈ K | Q ⊂ X} and K_{k}(X) := {Q ∈ K(X) | dim Q = k}. If Q ∈ K(X) is not a proper face of some P ∈ K(X), then it is a called maximal cube in X. The set of such cubes is denoted by K_{max}(X). A cubical set X is called full if all maximal cubes in X are pixels, that is, if K_{max}(X) = K_{d}(X).

Given a finite subset X of K, the support or polytope of X is the cubical set X ⊂ ℝ^{d} given by

X = |X | = ⋃ X .

Similarly, if Y, A, N, … are sets of elementary cubes, their supports are denoted respectively by Y, A, N, . . .. A natural extension of the concept of neighborhood of a set A ⊂ ℝ^{d} to the combinatorial setting is the wrap of A given by

wrap(A) = {P ∈ K_{max} | P ∩ A ≠ ∅}.

Its support is denoted by wrap(A) = |wrap(A)|. In particular, if A = |A| for some A ⊂ K, we put wrap(A) := wrap(A) and wrap(A) := wrap(A).

Let X and Y be cubical sets. A combinatorial multivalued map F : X \overrightarrow{→}Y is a function from X = K_{max}(X) to subsets of Y = K_{max}(Y). Such a function is called a combinatorial enclosure of a continuous function f : X → Y, if

wrap(f(Q)) ⊂ F(Q)

for all Q ∈ X.

By definition, F is a map on a finite set, so it carries no topology. The continuity concept can be introduced for related maps defined on X. A cubical multivalued map F : X\overrightarrow{→}Y is a function from X to subsets of Y (i.e. for every x ∈ X, F (x) ⊂ Y) which has the following properties.

1. For all x ∈ X, F (x) is a cubical set;

2. For all Q ∈ K(X), F |_{Q^{∘}} is constant; i.e. if x, x′ ∈Q^{∘}, then F (x) = F (x′).

Proposition 2.1 Assume F : X\overrightarrow{→}Y is a cubical map. Then

(a) F is lsc if and only if for any P, Q ∈ K(X) such that P is a face of Q,

F (P^{∘}) ⊂ F (Q^{∘}).

(b) F is usc if and only if for any P, Q ∈ K(X) such that P is a face of Q,

F (Q^{∘}) ⊂ F (P^{∘}).

The above proposition shows how to construct lsc and usc maps if their values on maximal cells are given. Given a combinatorial map F : X \overrightarrow{→}Y, we define two multivalued maps ⌊F⌋, ⌈F⌉ : X\overrightarrow{→}Y by

⌊F⌋(x) := ⋂ {|F(Q)| | x ∈ Q ∈ K_{max}(X)} ,  (4)
⌈F⌉(x) := ⋃ {|F(Q)| | x ∈ Q ∈ K_{max}(X)} .  (5)

Theorem 2.2 The multivalued maps ⌊F⌋ and ⌈F⌉ are cubical. The first one is lower semicontinuous, the second one upper semicontinuous.

Lsc cubical maps are those which we need for computing homology via the chain selector (acyclic carrier theorem) in the next section. Usc cubical maps are used in the Vietoris-Begle theorem discussed next and they are closer to continuous maps in the sense that their graphs are closed.

3 Homology of maps

Although various algorithms and programs for computing homology of polyhedra have been known for decades, there were no advances made in programming homology of continuous maps until recently. This is partially due to the fact that continuous maps require first a suitable approximation, so computing their homology is not only a symbolic computation task but also numerical analysis task. An additional difficulty lies in the fact that the classical definition of the homomorphism induced by a continuous map in homology based on barycentric subdivisions and simplicial approximations is extremely heavy in practical implementation.

We present here two modern approaches to computing homology of a continuous map between cubical sets via its multivalued representation. One, based on the constructive proof of the Chain Selector Theorem 3.1, is a geometric implementation of the well known Acyclic Carrier Theorem [69, Theorem 3.13] and is inspired by [75]. The proof of this theorem and of all related statements can be found in [51]. The other one, based on graph projections, is related to the Vietoris Mapping Theorem [79, 8]. The method has been originally proposed in [5] and its practical implementation is due to [65]. Both methods are implemented in [17]. The generalization to maps on other types of spaces is commented at the end of this section.

We start from defining the chain complex structure in a cubical set X ⊂ ℝ^{d}. The group C_{k}(X) of k-chains is the free abelian group generated by K_{k}(X). Its elements are finite sums of the form

c = α_{1}Q̂_{1} + α_{2}Q̂_{2} … α_{m}Q̂_{m},

where {Q_{1}, Q_{2}, …, Q_{m}} ⊂ K_{k}(X) and Q̂ : K_{k} → ℤ denote the dual of Q. We denote the set of all duals of elementary cubes by K̂. We use the “hat” notation to distinguish the algebraic object Q̂ from the geometric object Q. Obviously, for k < 0 and k > d the set K_{k} = ∅ and C_{k} = 0. The boundary map ∂_{k} : C_{k}(X) → C_{k−1}(X) is defined on the dual of each elementary cube Q ∈ K_{k}(X) as an alternating sum of its (k −1)–dimensional faces. The exact alternation formula is given in [51, Chapter 2]. The cubical chain complex of X is C(X) := {C_{k}(X), ∂_{k}}_{k∈ℤ}.

3.1 Chain selector approach

A cubical multivalued map F : X\overrightarrow{→}Y is called acyclic valued if for every x ∈ X the set F (x) is nonempty and acyclic, that is, if H̃_{∗}(F (x) = 0. The following theorem enables algorithms for computing homology of a map. Its explicit proof given in [5, 51] directly serves for the algorithm design.

Theorem 3.1 (Chain Selector Theorem) Assume F : X\overrightarrow{→}Y is a lsc acyclic valued cubical map. Then there exists a chain map φ : C(X) → C(Y) satisfying the following two conditions:

|φ(Q̂)| ⊂ F (Q^{∘}) for all Q ∈ K(X),  (6)
φ(Q̂) ∈ K̂_{0}(F (Q)) for any vertex Q ∈ K_{0}(X).  (7)

The above theorem permits now to give the following definition. Let F : X\overrightarrow{→}Y be a lsc acyclic valued cubical map. Let φ : C(X) → C(Y) be a chain selector of F. The homology map F_{∗} : H_{∗}(X) → H_{∗}(Y) of F is defined by

F_{∗} := φ_{∗}.

This definition is inheritable and functorial in the class of acyclic valued maps, in the sense of the following theorem.

Theorem 3.2 Let X, Y, Z be cubical sets.

1. If F, G : X\overrightarrow{→}Y are two lsc acyclic valued cubical maps and F is a submap of G, then F_{∗} = G_{∗};

2. If I : X\overrightarrow{→}X is an lsc acyclic-valued cubical representation of the identity map on X, then I_{∗} = id_{H_{∗}(X)};

3. Let F : X\overrightarrow{→}Y and G : Y \overrightarrow{→}Z be lsc acyclic valued cubical maps. If G ∘ F also is acyclic valued, then

(G ∘ F)_{∗} = G_{∗} ∘ F_{∗} ,

where G ∘ F (x) := G(F (x)).

Let now X and Y be cubical sets and let f : X → Y be a continuous function. A cubical representation to f or simply a representation to f is a lsc multivalued cubical map F : X\overrightarrow{→}Y such that

f(x) ∈ F (x)  (8)

for every x ∈ X. The minimal cubical representation M_{f} of f is given by

M_{f}(x) := ch (f(ch (x))),  (9)

where

ch (A) := ⋃{Q | Q ∈ K, Q^{∘} ∩A ≠ ∅}  (10)

is the closed hull of a set A ⊂ ℝ^{d}.

It is easily proved that M_{f} is in fact a representation of f and that it is minimal in the sense that given any other representation F of f, M_{f} is a submap of F. If f admits an acyclic valued representation F, the homomorphism f_{∗} : H_{∗}(X) → H_{∗}(Y) induced by f in homology is given by f_{∗} = F_{∗}. Unfortunately, this is not the case in general. In order to overcome the lack of acyclic valued representation we could introduce subdivisions of the unitary cubical grid. However, that would require a generalization of all what we have done until now to fractional grids. That is not necessary. Instead, we take a natural approach based on rescaling the domain of the function to a larger size by changing units.

Given a positive integer k, the corresponding scaling by the factor k is the linear coordinate preserving isomorphism Λ^{k} : ℝ^{d} → ℝ^{d} defined by

Λ^{k}(x) := (kx_{1}, kx_{2}, … kx_{d}).

It is easy to see that Λ^{k} maps cubical sets onto cubical sets. Let X ⊂ ℝ^{d} be a cubical set and let k ∈ ℤ. Define Λ_{X}^{k} := Λ^{k}|_{X}. The scaling of X by k is

X^{k} := Λ_{X}^{k}(X) = Λ^{k}(X).

The inverse of the map Λ_{X}^{k} : X → X^{k} is Λ_{X}^{1/k} : X^{k} → X. Scalings, their compositions, and inverses are convenient maps in the sense that their minimal cubical representations are acyclic valued, so they induce homomorphisms in homology. Moreover since these maps are isomorphisms of cubical sets, the induced homology maps are also isomorphisms. Note that we can compute the inverse ((Λ_{X}^{k})_{∗})^{−1} directly from M_{Λ_{X}^{1/k}} thus avoiding computation of the inverse of a homomorphism.

Given a continuous map f : X → Y and a scaling factor k put

f^{k} := f ∘ Λ_{X}^{1/k} : X^{k} → Y.

Proposition 3.3 Let X and Y be cubical sets and f : X → Y be continuous. Then there exists a scaling factor k such that M_{f^{k}} is acyclic valued. This scaling factor depends only on ϵ(δ), the modulus of equicontinuity of f on the compact set X.

We can now give the formula for the homology map of a continuous function on cubical set.

Theorem 3.4 Let f : X → Y be a continuous function where X and Y are cubical sets. Let k be a scaling factor such that M_{f^{k}} is acyclic valued. Then, the homology map of f_{∗} : H_{∗}(X) → H_{∗}(Y) is given by

f_{∗} = M_{(f^{k})_{∗}} ∘ M_{(Λ_{X}^{k})_{∗}}.  (11)

We conclude this section with the following remark. In [51], the homology theory is developed for the category Cub of cubical sets with continuous maps as morphism. The construction of homology map f_{∗} by means of the formula (11) and the chain selector provided by Theorem 3.1 is presented there as the definition of f_{∗}. It is proved there that so obtained homology is a functor from Cub to Ab_{∗}, the category of graded abelian groups. Direct proofs of homology axioms, in particular, the homotopy property, are provided. This functor is next extended to the category Pol of topological polyhedra which is defined in [51] as the class of topological spaces which are homeomorphic to cubical sets. Since any polyhedron is homeomorphic to a cubical set, this class contains, in particular all polyhedra.

3.2 Graph projection approach

We present here the most recent approach to computing homology of a map based on the following classical result. First, a continuous surjective map g : X → Y is called a Vietoris map if g^{−1}(y) is acyclic for all y ∈ Y. This definition is dependent on a choice of homology theory being used. For Ȟ, the Čech homology with field coefficients, we have the following

Theorem 3.5 (Vietoris Mapping Theorem) Let X and Y be compact spaces and g : X → Y a Vietoris map. Then g_{∗} : Ȟ_{∗}(X) → Ȟ_{∗}(Y) is an isomorphism.

The original Vietoris result [79] was used by Eilenberg and Montomery [21], improved and generalized by Begle [8], and is now often referred to as the Vietoris-Begle Theorem. In the context of general topological compact spaces, it requires a homology theory satisfying the continuity axiom (e.g. Čech or Alexander-Spanier). However, we only use it here for maps on cubical sets: in this context, the theorem holds for any integer-coefficient homology. In fact, one could use as well the Combinatorial Vietoris Theorem proved for cubical homology in [54].

Let f : X → Y be a continuous map and F : X \overrightarrow{→}Y its combinatorial enclosure. We consider the corresponding usc cubical representation of f given F = ⌈F⌉(x) : X\overrightarrow{→}Y. Consider the graph Gr(F) ⊂ X × Y of F and the two projections p : Gr(F) → X, q : Gr(F) → Y,

p(x, y) := x and q(x, y) = y, for all (x, y) ∈ Gr(F).

Then F (x) = q(p^{−1}(x)) for all x ∈ X, so F can be represented as a composition

F = q ∘ p^{−1}.

Since F (x) = {x} × p^{−1}(x) ≅ p^{−1}(x), we get the following corollary of Theorem 3.5.

Corollary 3.6 If F is acyclic valued then

p_{∗} : H_{∗}(Gr(F)) → H_{∗}(X)

is an isomorphism.

This allows us to define F_{∗} by the formula

F_{∗} := q_{∗} ∘ (p_{∗})^{−1}

The main feature of this formula is that X, Y, and Gr(F) are cubical sets and coordinate projections p and q are very simple maps. They belong to the class of cubical (single-valued) maps studied in [54] whose features are similar to those of simplicial maps: they map elementary cubes onto elementary cubes of possibly lower dimension. Consequently, their homology maps can be computed by an explicit combinatorial formula [54, Definition 4.6].

As it was the case with the chain selector approach discussed in Section 3.1, the hypothesis that F is acyclic valued may require the passage to a finer grid scale. We will not go again through the details of rescaling technique but rather outline the algorithm computing f_{∗} for the map f : X → Y. Since F is a cubical map, the hypothesis that F is acyclic valued is equivalent to the hypothesis

p^{−1}(Q^{∘}) is acyclic valued for all Q ∈ K(X).  (12)

Algorithm 3.7 Computing f_{∗}

1. Fix a grid scale in X × Y;

2. Construct the combinatorial enclosure F of f;

3. Compute the graph Z = Gr(⌈F⌉) and the projections p : Z → X, and q : Z → Y;

4. Verify the condition (12): If it fails, take a smaller grid scale in X and go back to 2;

5. Compute the homology maps p_{∗} : Z → X and q_{∗} : Z → Y;

6. Compute the inverse (p_{∗})^{−1};

7. Compute and return the composition q_{∗} ∘ (p_{∗})^{−1}.

Note that condition (12) can be verified in practice without explicit com-

putation of homology groups of p^{−1}(Q^{∘}). For example, one may apply the technique of elementary collapses (c.f. [51, 53]). One may also improve the efficiency of the algorithm by a preprocessing, also involving elementary collapses, which allows one to replace the graph Z = Gr(⌈F⌉) by another set Z in X × Y whose dimension is the same as the dimension of X. The details of the algorithm outlined above, together with all the technicalities which make its implementation efficient are presented in [65].

4 Chaotic dynamics

Although the discovery that solutions of differential equations may behave chaotically goes back to Poincaré in 1890s, that area of research idled for several decades in mid 1900s. It has been awake probably, among others, thanks to the invention of the computer which enabled high precision numerical simulations of flow trajectories. The pioneer work in that computer-aided area of dynamical systems is that of Edward N. Lorenz of 1963 who numerically studied the system of differential equations arising from meteorology

\{ \begin{matrix}ẋ & = & σ(y − x) \\ ẏ & = & rx − y − xz \\ ż & = & xy − bz \end{matrix}  (13)

where σ, r, and b are parameters. Since then, efforts were made to rigorously state what does chaos mean and to rigorously prove that the Lorenz equations are chaotic indeed. It took over 30 years before the conjecture was proved in parallel by Mischaikow and Mrozek [63] and by Hassard and Zhang [44], in different settings. A topological in concept, rigorous proof given by [63, 64] served as a general model of techniques for proving chaos in other dynamical systems. In this paper, we are interested in ingredients of this proof related to the use of mv maps. Rather than presenting the proof of chaos which is long and involved both numerically and in amount of concepts which need to be introduced, we will describe methods of showing the existence of periodic orbits of various periods.

Figure 3: Chaotic region of the Lorenz system projected to XY and XZ planes.

The first step is to identify a Poincaré section which is a surface X ⊂ ℝ^{3} located transversally to the numerically observed bundle of trajectories visible on Figure 3, indicating a possible presence of a chaotic attractor. A flow trajectory passing through any x ∈ X must return to X multiple times. This permits defining the Poincaré map f : X → X which assigns to any x ∈ X the first return point f(x) ∈ X. The periodic points of f, that is, solutions of the equation x = f^{n}(x) for some n ∈ N determine cycles of the flow crossing X. In this way, the problem passes from continuous-time to discrete-time dynamics. Proving chaos means, among other criterions, proving that f has periodic points of arbitrary prime periods. Next, the surface X can be parameterized using an appropriately scaled cubical grid discussed in Section 2 and a numerical analysis with rigorous bounds serves constructing a combinatorial enclosure F : X \overrightarrow{→}X of F such that the usc mv cubical map F = ⌈F ⌉ : X\overrightarrow{→}X has acyclic values.

We shall now introduce some dynamical notions in the setting of usc mv combinatorial maps F : X\overrightarrow{→}X. First, A full trajectory through a maximal elementary cube Q ∈ X under F is a sequence (Q_{n})_{n∈ℤ} of elementary maximal cubes such that Q_{n} = Q and

Q_{n+1} ∈ F(Q_{n}) for all n ∈ ℤ.

Let N be a finite subset of X. The maximal invariant set in N under F is

Inv_{F}(N) := {Q ∈ N | ∃ a full trajectory (Q_{n})_{n∈ℤ} through Q in N } .

A finite N ⊂ K_{max} is an isolating neighborhood if

wrap(Inv_{F}(N)) ⊂ N

Note that maximal invariant sets S = Inv_{f}(N) of continuous maps are not explicitly known and the aim of the Conley index theory is to study their properties without knowing them, but Inv_{F}(N) is computable by a very simple and fast algorithm due to Szymczak [76]. An isolating neighborhood should be guessed on a basis of empirical experience but there is again a simple algorithm in [76] which confirms or disapproves the guess.

An index pair in dynamics of f is, roughly speaking, a pair (P_{1}, P_{0}) where N = cl (P_{1} \ P_{0}) is a refined isolating neighborhood, and P_{0} is an exist set in the sense that the trajectories of f cannot leave N otherwise then passing through P_{0}. The next step is to give a constructive definition of an index pair (P_{1}, P_{0}) for F, where P_{0} ⊂ P_{1} ⊂ N and of a target pair (Q_{1}, Q_{0}) in X for F, so that the following postulates could be satisfied

1. The pair of corresponding supports (P_{1}, P_{0}) is an index pair for the selector f in the sense of [51, Chapter 10];

2. The inclusion ι : (P_{1}, P_{0}) ↪ (Q_{1}, Q_{0}) is excisive, that is, it induces an isomorphism in homology.

The definition of index and target pairs is by means of an algorithm constructing it and since it is technically involved, we refer to [51]. Since F is acyclic valued, the homomorphism

f_{∗} = F_{∗} : H_{∗}(P_{1}, P_{0}) → H_{∗}(Q_{1}, Q_{0})

is well defined. The index map f_{P ∗} is defined for f by

f_{P ∗} := ι_{∗}^{−1} ∘ F_{∗} : H_{∗}(P_{1}, P_{0}) → H_{∗}(P_{1}, P_{0}).

This map serves for defining the Conley index of f but we will not go that far: In order to show the existence of periodic points, it is enough to use the following corollary of the Lefschetz fixed point theorem for maps on spaces due to Bowszyc [12]:

Theorem 4.1 (Relative Lefschetz Fixed Point Theorem) Let

f_{P ∗} : H_{∗}(P_{1}, P_{0}) → H_{∗}(P_{1}, P_{0})

be the index map for (P_{1}, P_{0}). If

L(f_{P ∗}) := ∑_{k}(−1)^{k}tr f_{P ∗k} ≠ 0,

then Inv (cl (P_{1} \ P_{0}), f) contains a fixed point of f.

Let us note that the Lefschetz theorem for general classes of compact spaces holds for homologies satisfying the continuity axiom (e.g. Čech or Alexander–Spanier) but we use it in context of cubical sets in which no additional assumptions on homology theory or field coefficients are needed. Here is a simple consequence of this theorem. If for a fixed integer n > 0,

∑_{k}(−1)^{k}tr f_{P ∗k}^{n} ≠ 0,

then Inv (cl (P_{1} \ P_{0}), f) contains a periodic orbit of period n. The main problem is the following

The number n need not be the minimal period.

We need another tool which would allow us to prove that if x is a fixed point of f^{n} in some specific set, then it cannot be a fixed point of f^{k} for k < n. For this, we need the following two definitions.

A disjoint decomposition of an index pair P = (P_{1}, P_{0}) is a family of disjoint cubical sets {N^{i} | i = 1, ..., n} such that

cl (P_{1} \ P_{0}) = ⋃_{i=1}^{n} N^{i}.

Given a disjoint decomposition {N^{i}}, the associated cubical transition graph is a directed graph with nodes N^{i} and directed edges

N^{i} → N^{j} ⟺ F(N^{i}) ∩ N^{j} ≠ ∅.

For example, the arrow N_{1} → N_{1} is present in the transition graph if and only if N_{1} ∩ F(N_{1}) ≠ ∅. Hence, if there is no such arrow in the graph, F cannot have a fixed point in N_{1}. Any periodic point of f in this set detected by Theorem 4.1 must have minimal period at least 2.

In the setting of cubical grids and combinatorial enclosures, there are algorithms constructing disjoint decomposition and related transition graph of a given index pair.

Figure 4: An index pair P = (P_{1}, P_{0}) for the Hénon map: P_{1} is the union of all squares and P_{0} of the dark squares.

Example 4.2 A simplified model for the Poincaré map is the Hénon map f : ℝ^{2} → ℝ^{2} given by

f(x, y) = (1 + y/5 − ax^{2}, 5bx).

Numerical study of this map was done in [77]. A proper grid scale, and a candidate for isolating neighborhood N are found empirically. The algorithm computing index pairs returns result P = (P_{1}, P_{0}) shown in Figure 4. The information on F also gives the decomposition {N^{i}} and the transition graph:

N^{1}  N^{3} ⟶ N^{4}
↑↓ ↗ ↑  ↓
N^{2}  N^{6} ⟵ N^{5}
↑  ↙
N^{8} ⟵ N^{7}

The graph shows a possibility of periodic points of minimal periods 2, 4, 6, and 8. Their existence is confirmed by the study of f_{P ∗k}^{n} via Theorem 4.1 and the use of the homology program in CHomP [17]. With a different initial choice of a grid scale and a different guess of an isolating neighborhood one may obtain periodic points of different periods. For more delicate arguments showing that the dynamics of the Hénon map is chaotic indeed, we refer the reader to [51, 77].

5 Digital imaging

In digital imaging, the values of functions f : ℝ^{d} → ℝ are only known at finitely many grid points. Our approach, inspired by the combinatorial multivalued maps discussed in previous sections, is to define combinatorial maps on highest dimensional grid cells rather that on vertices. Thus we consider functions on discrete sets

f : X → ℝ, where X ⊂ K_{max}.

This approach is very natural, if we view the smallest objects in an image, d-pixels, as elementary cubes in the cubical grid K_{max}. If a function f is given on a polytope X = |X | ⊂ ℝ^{d}, we may define the discretization of f on X by taking its values at the barycenter of each maximal elementary cube.

The first goal in [3, 4] has been to establish a discrete analogy of a flow φ of a gradient field ∇f for a function f defined on pixels (mathematically, elementary cubes) while keeping the original geometry, that is, without forcing the data to obey the hypotheses of the Morse theory on isolation and non-degeneracy of critical points. The concept of a discrete dynamical system generated by an mv map F : X → X introduced in [52] seems to be suitable here and there are several natural choices for its construction but all of them lead to the same problem, well known in digital imaging:

In the continuous case, the critical points of f are equilibrium points of the flow and hence fixed points of the generator F. Thus it seems that critical regions of f should be connected level sets of f and, at the same time, fixed points of F. This works well with the maximum and minimum regions, which may be defined simply as connected regions of pixels with the same value of f but surrounded by pixels with a strictly greater, respectively, strictly smaller, value of f. But a difficulty is in defining saddle regions. Any attempt of construction a single-level saddle region ends up with examples of such regions directly adjacent to minimum or maximum regions. This is illustrated in Figure 5.

The conclusion is that we cannot decide if a given pixel is regular or critical, without examining the nature of surrounding pixels. This leads to an algorithm detecting non-regular pixels building their critical components in [3] using the concepts of exit and entrance sets. The criterion of regularity of an initial pixel Q, inspired by the Ważewski principle [81], is whether or not, in a certain type of isolating block of the pixel, the entrance and exit sets are deformation retracts of the block. If the pixel is tested non-regular, this criterion is reapplied to its component C(Q) build up by the recurrent algorithm. Since this paper is focused on multivalued maps and describing

2 0 4 0 2 1 3 4 0 4 0 4  1 1 1 1 -1 0 0 1 -1 1 1 1 (a)  (b)

Figure 5: (a) Adjacent center pixels with values of f 1 and 3 are both saddles and form a component which is not a level set of f but it has a property of a 4-ridge saddle; (b) Adjacent non-regular pixels with the value 0. The one on the left is a “non-isolated saddle”, the one on the right is a “non-isolated minimum”.

the algorithmic definition of critical components would send us to a field, we refer the reader to [3]. Once the critical components are properly defined, one may define the generator of a dynamical system on regular pixels.

Let X ⊂ K_{max}. Consider a function f : X → ℝ and Q ∈ X^{d} such that wrap(Q) ⊂ X^{d}. The upper wrap of Q is the set of all elementary cubes in wrap(Q) with higher values of f than f(Q), that is

\overline{wrap} (Q) := \{P ∈ wrap(Q) | f(P) > f(Q)\} .

Analogously, the lower wrap and zero wrap are the sets

\underline{wrap} (Q) := \{P ∈ wrap(Q) | f(P) < f(Q)\} .,
wrap_{0}(Q) := {P ∈ wrap(Q) | f(P) = f(Q)} .

The upper and lower wraps are analogies of the exit and entrance sets from the Conley index theory.

We want to introduce a generator of a dynamical system that would exhibit the dynamical properties analogous to those of the gradient flow of f. First, we need to take account the fact different types of adjacency between neighboring elementary cubes, e.g. via a vertex, edge or a face, result in different metric spacing between their centers. We define the distance dist (Q, P) between two elementary cubes as the distance between their centers. If Q, P ∈ X^{d} intersect at a common face of dimension k, then

dist (Q, P) = \sqrt{d − k}.

The directional derivative of f at Q in the direction of an adjacent cell P is

∂_{P} f(Q) = \frac{f(P) − f(Q)}{dist (Q, P)}.

By convention, ∂_{Q}f(Q) = 0. The following differences between the smooth and discrete settings have to be taken account of.

1. In the smooth case, while the gradient ∇f points the direction of the steepest (or fastest) ascent, its inverse −∇f shows the direction of the steepest descent. In the discrete case, we don’t have such symmetry so we need to consider two different types of trajectories, steepest ascent trajectory and steepest descent trajectory. In particular, we have to deal with a discrete multivalued dynamical semi-systems (DMSS), i.e. a system of positive-time iterates of a map F whose inverse may have empty-values.

2. In the smooth case, a trajectory cannot pass through a critical point. In the discrete case, if we want to make our construction of fast trajectories robust, we should take account of trajectories passing through the nearest neighborhood (the wrap) of a saddle component as if it passed through it. Thus we cannot require that F(Q) = {Q} for a critical elementary cube Q but only Q ∈ F (Q). Moreover, in the case of a saddle component, there may be several ascending directions to consider and one should take account of one steepest direction in each ascending component, the same for descending directions.

Given a critical elementary cube Q, we consider the decomposition of the support of \overline{wrap} (Q) to k connected components and that of \underline{wrap} (Q) to l connected components. This corresponds to the decomposition:

\overline{wrap} (Q) = ⋃_{i=1}^{k} \overline{wrap} _{i}(Q)

and

\underline{wrap} (Q) = ⋃_{i=1}^{l} \underline{wrap} _{i}(Q)

We put

m_{i}(Q) = min_{P ∈\underline{wrap} _{i}(Q)} ∂_{P} f(Q) and M_{i}(Q) = max_{P ∈\overline{wrap} _{i}(Q)} ∂_{P} f(Q).

Given f : X → ℝ, the ascending system is generated by the map F : X \overrightarrow{→}X defined on Q ∈ X as follows. Let first

F_{+}^{∗}(Q) = ⋃_{i=1}^{k} \{P ∈ \overline{wrap} _{i}(Q) | ∂_{P} f(Q) = M_{i}(Q)\} .

If Q is regular, we put F_{+}(Q) = F_{+}^{∗}(Q). If Q is critical and C its critical component, we put F_{+}(Q) = C ∪ F_{+}^{∗}(Q).

The descending system is generated by the map F_{−} : X \overrightarrow{→}X defined on cells Q ∈ X as follows. Let first

F_{−}^{∗}(Q) = ⋃_{i=1}^{l} \{P ∈ \underline{wrap} _{i}(Q) | ∂_{P} f(Q) = m_{i}(Q)\} .

If Q is regular, we put F_{−}(Q) = F_{−}^{∗}(Q). If Q is critical and C its critical component, we put F_{−}(Q) = C ∪ F_{−}^{∗}(Q).

This two-step construction induces the following

Proposition 5.1 Let F be either F+ or F_{−}. An elementary cube Q ∈ X is critical if and only if it is a fixed point of F, that is Q ∈ F(Q).

The analogies of stable and, respectively, unstable manifolds from the smooth Morse theory [61] in discrete mv dynamical semi-systems F are backward and forward orbits given by

F(C, ℤ_{−}) := ⋃ {P | ∃ trajectory (Q_{k})_{k∈[−n,0]}, n ∈ ℕ,
Q(−n) = P, Q(0) = Q, Q ∈ C};
F(C, ℤ_{+}) := ⋃ {P | ∃ trajectory (Q_{k})_{k∈[0,n]}, n ∈ ℕ,
Q(0) = Q, Q(n) = P, Q ∈ C};

The above formulas are equivalent to

\begin{aligned}F(C, ℤ_{+}) & = & ⋃_{Q∈C,n≥1} F^{n}(Q); \\ F(C, ℤ_{−}) & = & ⋃_{Q∈C,n≥1} F^{−n}(Q). \end{aligned}

Theorem 5.2 [4, Proposition 2.14 and Corollary 2.16] Let X be finite and let F be either F_{+} or F_{−}. If C and D are critical components such that F(C, ℤ_{−}) ∩ F(C, ℤ_{+}) ≠ ∅, then there exists a trajectory connecting C to D in the sense that it is issued at a cell in C and ends at a cell in D.

The transversality property for stable and unstable manifolds of a Morse function [61] does not generalize to DMSS, however the covering property does. Here is its analogy.

Theorem 5.3 [4, Theorem 2.17] Let X be finite and let F be either F_{+} or F_{−}. Let {C_{i}}_{i=1,2,...k} be the set of all critical components in X^{d}. Then

⋃_{i=1}^{k} F(C, ℤ_{−}) = X = ⋃_{i=1}^{k} F(C, ℤ_{+}).

Let now C and D be two critical components of f : X → ℝ. We say that there is an upward connection from C to D, denoted C ↗ D, if

F_{+}(C, ℤ_{+}) ∩ F_{+}(C, ℤ_{−}) ≠ ∅.

There is a downward connection from C to D, denoted C ↘ D, if

F_{−}(C, ℤ_{+}) ∩ F_{−}(C, ℤ_{−}) ≠ ∅.

We now define the Morse Connection Graph as follows. The Morse Connections Graph MCG_{f} = (V_{f}, E_{f}) is a graph whose nodes V_{f} and edges E_{f} are defined as follows:

V_{f} = {critical components of f};
E_{f} = {(C_{i}, C_{j}) ∈ V_{f} × V_{f} | C_{i} ↗ C_{j} or C_{i} ↘ C_{j}}

An additional information about the dynamics on X can be extracted by distinguishing two types of edges in Morse connections graph: The upward connection edges and the downward connection edges respectively defined by

E_{f}^{+} = {(C_{i}, C_{j}) ∈ V_{f} × V_{f} | C_{i} ↗ C_{j}}

and

E_{f}^{−} = {(C_{i}, C_{j}) ∈ V_{f} × V_{f} | C_{i} ↘ C_{j}} .

The algorithm constructing Morse Connections Graph and experimentation on two-dimensional image data are presented in [4]. The Morse Connections Graph algorithm itself is dimension independent but an experimentation in higher dimensional has not been done yet at the time of writing this paper.

An interesting direction of further study is related to the formula:

pits – passes + peaks = 2

holding for a Morse function on the 2-sphere. This formula was discovered by Maxwell [60] but is commonly called Euler formula due to its similarity to the Euler characteristics of a polyhedron. It is used in a number of works about digital elevation models as a criterion of correctness of the extracted critical points. The Morse index [61] enables its generalization to manifolds of arbitrary dimensions. It will be useful to have this formula generalized to critical regions (of possibly non-trivial topology and possibly multiple saddles) in our discrete setting.

References

[1] E.L. Allgower and K. Georg, Simplicial and continuation methods for approximating fixed points and solutions to systems of equations, SIAM Rev. 22 (1980), 28–85.

[2] E.L. Allgower and K. Georg, Numerical Continuation Methods, Springer-Verlag 1990.

[3] M. Allili, D. Corriveau, S. Derivière, and T. Kaczynski, Detecting critical regions in multidimensional data sets via the Conley index approach, Res. rap. Dep. Math. Univ. Sherbrooke, 2007–52.

[4] M. Allili, D. Corriveau, S. Derivière, T. Kaczynski, and A. Trahan, Discrete dynamical system framework for construction of connections between critical regions in lattice height data, J. Math. Imaging & Vision 28 (2) (2007), 99–111.

[5] M. Allili and T. Kaczynski, An algorithmic approach to the construction of homomorphisms induced by maps in homology, Trans. Amer. Math. Soc., 352 (2000), 2261–2281.

[6] J.P. Aubin, Mathematical Methods of Game Theory and Economic Theory, North Holland, New York 1979.

[7] J.P. Aubin and A. Celina, Differential Inclusions, Springer-Verlag Berlin Heidelberg 1984.

[8] E. Begle, The Vietoris mapping theorem for bicompact spaces, Ann. Math., 51 (1950), 534–543.

[9] H. Ben-El-Mechaiekh, The Ky Fan fixed point theorem on star-shaped domains, Math. Reports Royal Soc. Canada, 27, 4 (2005), 97-100.

[10] H. Ben-El-Mechaiekh and P. Deguire, Approximation of non-convex setvalued maps, Comptes Rendus Acad. Sci. Paris 312 (1991), 379-384.

[11] H. Ben-El-Mechaiekh and R. Dimand, The von Neumann minimax theorem revisited, in Fixed Point Theory and Applications, Banach Center Publ., Warszawa 2007, pp 23–34.

[12] C. Bowszyc, Fixed point theorems for the pairs of spaces, Bull. Acad. Pol. Sc., Ser. Sc. Math., Astr. et Phys., (16) 1968, 845–850.

[13] F. E. Browder, On continuity of fixed points under deformations of continuous mappings, Summa Brasilia Math. 4 (1960), 183-191.

[14] F. E. Browder, The fixed point theory of multi-valued mappings in topological vector spaces, Math. Ann. 177 (1968), 283–301.

[15] K.C. Chang, The obstacle problem and partial differential equations with discontinuous nonlinearities, Comm. Pure Appl. Math. 33 (1980), 117–146.

[16] C. Conley, Isolated invariant sets and the Morse index, CMBS Lecture Notes 38, AMS Providence 1978.

[17] Computational Homology Project (CHomP), Homology Software, http://chomp.rutgers.edu .

[18] K. Deimling, Multivalued Differential Equations, W. De Gruyter, 1992.

[19] S. Derivière, Contribution à l’étude des attracteurs des systèmes dynamiques en dimension finie. Ph. D. Thesis, Université de Rouen 2004.

[20] H. Edelsbrunner, J. Harer, and A.J. Zomorodian, Hierarchical Morse-Smale complexes for piecewise linear 2-manifolds. In AMC Symposium on Computational Geometry, Discrete & Compu. Geom. 30 (1) (2003), 87–107.

[21] S. Eilenberg and D. Montgomery, Fixed point theorems for multi-valued transformations, Amer. J. Math. (68) (2) (1946), 214-222.

[22] L. Erbe and W. Krawcewicz, Existence of solutions to boundary value problems for impulsive second order differential inclusions, Rocky Mtn J. Math., 22 (1992), 1–20.

[23] L.H. Erbe, W. Krawcewicz and T. Kaczynski. Solvability of two-point boundary value problems for systems of nonlinear differential equations of the form y′′ = g(t, y, y′, y′′). Rocky Mtn. J. Math., 20 (4) (1990), 899-907.

[24] K. Fan, Fixed-point and minimax theorems in locally convex linear topological spaces, Proc. Natn. Acad. Sci. USA 38 (1952), 121–126.

[25] A.F. Filippov, Differential equations with discontinuous right hand side, Math. Sbornik 51, 99–128, english transl. Trans. AMS 42 (1964), 199– 232.

[26] P.M. Fitzpatrick and W. V. Petryshyn, A degree theory, fixed point theorems, and mapping theorems for multivalued noncompact mappings, Trans. AMS 194 (1974), 1–25.

[27] R. Forman, Morse theory for cell complexes, Advances in Math. 134 (1998), 90–145.

[28] G. Fournier and D. Violette, A fixed point index for compositions of acyclic maps in Banach spaces, Ann. Polon. Math. 47 (1987), 381–410.

[29] M. Frigon, Applications de la théorie de la tranversalité topologique à des problèmes non linéiares pour des équations différentielles ordinaires, Dissert. Math. 286 (1990).

[30] M. Frigon, Théoreèmes d’existence de solutions d’inclusions différentielles, in Topological Methods in Differential Equations and Inclusions, eds. M. Frigon and A. Granas, NATO ASI Series, Ser. C: Math. and Phys. Sci. 472, Kluwer Acad. Publ. Dordrecht 1995, 51–87.

[31] M. Frigon, Fixed point results for compact maps on closed subsets of Fréchet spaces and applications to differential and integral equations, Bull. Soc. Math. Bel. S. Stevin, 9 (2002) 23–37.

[32] M. Frigon, L. Górniewicz, and T. Kaczynski, Differential inclusions and implicit equations on closed subsets of ℝ^{n}, in World Congeress of Nonlinear Analysts ’92, ed. V. Lakshmikantham, W. de Gruyter, Berlin - New York 1996, 1797–1806.

[33] M. Frigon, A. Granas, and Z. Guennoun, A note on the Cauchy problem for differential inclusions, Topol. Meth. Nonlinear Anal. 1 (1993), 315– 321.

[34] M. Frigon and T. Kaczynski, Boundary value problems for systems of implicit differential equations, J. Math. Anal. Appl. 179 (2) (1993), 317– 326.

[35] K. Gȩba, A. Granas, T. Kaczynski, and W. Krawcewicz, Homotopie et équations non linéaires dans les espaces de Banach, C.R. Acad. Sci. Paris, 300, série I, (10) (1985), 303-306.

[36] L. Górniewicz, Homological Methods in Fixed Point Theory of Multi-Valued Maps, Dissert. Math. 129, PWN Warszawa 1976.

[37] L. Górniewicz, Topological approach to differential inclusions, in Topological Methods in Differential Equations and Inclusions, eds. M. Frigon and A. Granas, NATO ASI Series, Ser. C: Math. and Phys. Sci. 472, Kluwer Acad. Publ. Dordrecht 1995, 129–190.

[38] L. Górniewicz, Topological Fixed Point Theory of Multivalued mappings, Kluwer Acad. Publ. Dordrecht 1999.

[39] L. Gorniewicz, A. Granas and W. Kryszewski, On the homotopy method in the fixed point index theory of multi-valued mappings of compact absolute neighborhood retracts, J. Math. Anal. Appl. 161 (1991), no. 2, 457–473.

[40] A. Granas, Sur la notion de degré topologique pour une certaine classe de transformations mulivalentes dans les espaces de Banach, Bull. Acad. Polon. Sci. 7 (1959), 181–194.

[41] A. Granas, Theorem on antipodes and theorems on fixed points for certain class of multivalued mappings in Banach spaces, Bull. Acad. Polon. Sci. 7 (1959), 271-275.

[42] A. Granas and J. Dugundji, Fixed Point Theory, Springer-Verlag, New York 2003.

[43] A. Granas and J. W. Jaworowski, Some theorems on multi-valued maps of subsets of the Euclidean space, Bull. Acad. Polon. Sci. 7 (1959), 277– 283.

[44] B. Hassard and J. Zhang, Existence of a homoclinic orbit of the Lorenz system by precise shooting, SIAM J. Math. Anal., 25 (1994), 179-196.

[45] J.W. Jaworowski, Theorem on antipodes for multivalued mappings ans a fixed point theorem, Bull. Acad. Polon. Sci. 4 (1956), 187–192.

[46] J.W. Jaworowski, Some consequences of the Vietoris mapping theorem, Fund. Math. 45 (1958), 261-272.

[47] T. Kaczynski, Quelques théorèmes de points fixes dans des espaces ayant suffisamment de fonctionnelles linéaires , C.R. Acad. Sci. Paris, 296, série I, 1983, 873-874.

[48] T. Kaczynski, On differential inclusions of second order, in Proc. Equadiff Conf. Xanti 1987, eds. C.M. Dafermos, G. Ladas, P. Papanicolau, Marcel Dekker, New York and bassel 1989.

[49] T. Kaczynski, Unbounded multivalued Nemytskii operators in Sobolev spaces and their applications to discontinuous nonlinearity, Rocky Mountains J. Math. 22 (2) (1992), 635–643.

[50] T. Kaczynski, Conley index for set-valued maps: From theory to computation, In Conley Index Theory, Banach Center Publ. 47, Warszawa (1999), 57–65.

[51] T. Kaczynski, K. Mischaikow, and M. Mrozek, Computational Homology, Appl. Math. Sci. Series 157, Springer-Verlag, New York 2004.

[52] T. Kaczynski, M. Mrozek, Conley index for discrete multivalued dynamical systems, Topology and Its Appl. 65 (1995), 83–96.

[53] T. Kaczynski, M. Mrozek, and M. Slusarek, Homology computation by reduction of chain complexes, Computers & Math. Appl. 34 (4) (1998), 59–70.

[54] T. Kaczynski, M. Mrozek, and A. Trahan, Ideas from Zariski topology in the study of cubical sets, cubical maps, and their homology, Canad. J. Math., 59 (5) (2007), 1008–1028.

[55] T. Kaczynski and V. Zeidan, An application of Ky-Fan fixed point theorem to an optimization problem, Nonlinear Anal TMA, 13 (3), (1989), 259-261.

[56] T. Kaczynski and H. Xia, Hopf bifurcation for implicit neutral functional differential equations, Canad. Math. Bull. 36 (3) 1993, 286-295.

[57] S. Kakutani, A generalization of Brouwer’s fixed point theorem, Duke math. J. 8 (1941), 457–459.

[58] W. Kryszewski, Topological and approximation methods in the degree theory of set-valued maps, Dissert. Math. 336 (1994).

[59] T. Ma, Topological degrees of set-valued compact fields in locally convex spaces, Dissert. Math. 92 PWN, Warszawa 1972.

[60] J. C. Maxwell, On hills and dales, The London, Edinburg and Dublin Philosophical Magazine and Journal of Science, 40 (1870), 421–425.

[61] Y. Matsumoto, An Introduction to Morse Theory Mathematical Monographs 208, Amer. Math. Soc. 2002.

[62] E. Michael, Continuous selections, I, Ann. Math., 63 (1956), 361-382.

[63] K. Mischaikow and M. Mrozek, Chaos in Lorenz equations: A computer assisted proof, Bull. Amer. Math. Soc. (N.S.), 33 (1995), 66–72.

[64] K. Mischaikow and M. Mrozek, Chaos in Lorenz equations: A computer assisted proof, Part II: Details, Mathematics of Computation, 67, (1998), 1023–1046.

[65] K. Mischaikow, M. Mrozek, and P. Pilarczyk, Graph approach to the computation of the homology of continuous maps, Foundations of Comput. Math., 5 (2005), 188–229.

[66] M. Mrozek, A cohomological index of Conley type for multivalued admissible flows, J. Diff. Equ. 84 (1990), 15–51.

[67] M. Mrozek, Leray functor and cohomological index for discrete dynamical systems, Trans. AMS 318 (1990), 149–178.

[68] M. Mrozek, Inheritable properties and computer assisted proofs in dynamics, In Scientific Computing and validated numerics, eds. G. Alefeld, A. Frommer and B. Lang, Vol. 90, Akademie Verlag, Berlin 1996, pp. 245–257.

[69] J.R Munkres, Elements of Algebraic Topology, Addison-Wesley 1984.

[70] J. Nash, Non-cooperative games, Ann. Math. 54 (1951), 286–295.

[71] N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani (editors), Algorithmic Game Theory, Cambridge Univ Press 2007.

[72] W.V. Petryshyn, Solvability of various boundary value problems for the equation x′′ = f(t, x, x′, x′′) − y, Pacific. J. Math. 122 (1986), 169-195.

[73] T. Pruszko, Some Applications of topological degree theory to multivalued boundary value problems, Dissert. Math. 229 (1984).

[74] J. Robbin and D. Salamon, Dynamical systems, shape theory, and the Conley index, Ergodic Theory and Dynamical Systems, 8* (1988), 375– 393.

[75] H.W. Siegberg and G. Skordev, Fixed point index and chain approximation, Pacific J. Math. 102 (2) (1982), 455–486.

[76] A. Szymczak, A combinatorial procedure for finding isolating neighbourhoods and index pairs, Proc. Roy. Soc. Edinburgh Sect. A 127 (5) (1997), 1075–1088.

[77] A. Szymczak, Index pairs: From dynamics to combinatorics and back, Ph.D. thesis, Georgia Inst. Tech., Atlanta 1999.

[78] M.J. Todd, The Computation of Fixed Points and Applications, Lecture Notes in Econ. and Math. Systems 124, Springer-Verlag, Berlin-Heidelbeg 1976.

[79] L. Vietoris, Über die höheren Zusammenhang kompacter Räume und eine Klasse von zusammenhangstreuen Abbildungen, Math. Ann. 97 (1927), 454-472.

[80] J. von Neuman, Über ein ökonomisches Gleichungssystem und eine Verallgemeinerung des Brouwerschen Fixpunktsatzes, Ergebn. Math. Kolloq. 8 (1937), 73-83.

[81] T. Ważewski, Une méthode topologique de l’examen du phénomène asymptotique relativement aux équations différentielles ordinaires, Rend. Accad. Nazionale dei Lincei, Cl. Sci. fisiche, mat. e naturali, Ser. VIII, III (1947), 210–215.

[82] G.H Weber, G. Scheuermann, B. Hamann, Detecting critical regions in scalar fields, In IEEE TCVG Symposium on Visualization IEEE (2003), 1–11.

Département de mathématiques Université de Sherbrooke Sherbrooke, Qc, Canada J1K 2R1 tomasz.kaczynski@usherbrooke.ca