# Full text of "Moving closer: contractive maps on discrete metric spaces and graphs"

## See other formats

MOVING CLOSER: CONTRACTIVE MAPS ON DISCRETE METRIC SPACES AND GRAPHS FABIO ZUCCA Abstract. We consider discrete metric spaces and we look for nonconstant contractions. We introduce the notion of contractive map and we characterize the spaces with nonconstant contrac- tive maps. We provide some examples to discussion the possible relations between contractions, contractive maps and constant functions. Finally we apply the main result to the subgraphs of a nonoriented, connected graph. Keywords: discrete metric space, contractive map, contraction, fixed point, nonoriented graph AMS subject classification: 47H09, 54E99. 1. Introduction Let us consider the following question: a group of people, living in the same country, but in different places, want to move in such a way that the distance among any two of them strictly decreases. Unfortunately they cannot all fit into one single house. Hence, the constraints are: (i) anyone can either move from his place to another one's (no matter what the owner of the "destination house" does) or stay where he is, (ii) they cannot all move to the same place. Is it possible for them to move? This question is a particular case of a more interesting problem involving discrete, possibly infinite, metric spaces (we will come back to the original problem in Section [3] at the end of the paper). We say that a couple {X,d) is a metric space if X is a set and d is real function, called distance, defined on X x X such that (1) d{x, y) = if and only if x = y (for all x, y G X) and (2) d{x, y) < d{x, z) + d{y, z) for all x,y,z G X. We do not require the distance to be finite; if d{x, y) = oo we imagine that x and y belong to two disjoint components of the space (see below a more detailed discussion on this, in the case of a graph). From (2), with y = x, and (1) we have that = d{x,x) < 2d{x,z) (for all x,z ^ X) hence d is nonnegative. Moreover, again from (2), using z = x, and (1), we have that d{x,y) < d{x,x) + d{y,x) = d{y,x) (for all x,y G X), thus, by symmetry, we have d(x, y) = d{y, x). For some basic properties of metric spaces see for instance [U Chapter 2]. An example of a discrete metric space is given by a (nonoriented) graph (see for instance [T]). Roughly speaking, a graph is a (finite or infinite) collection of points, called vertices, along with a set of pairs of vertices, called edges. We say that it is possible to move (in one step) from a vertex x 1 2 3 4 5 6 7 — — »"< — — >"< — ~T — ■>i< -S>J< >l< — >^ — — >^ — -Ju ^ >'< >'< >'< 0' 1' 2' 3' 4' 5' 6' T Figure 1 The graph NUN. to a vertex y if and only if (x, y) is an edge. A path is a concatenation of edges, and the minimum number of steps required to go from x to y, say d{x,y), is called natural distance from x to y. To be precise, in order to have an actual distance we have to assume that if we can move in one step from X to y then we can also go back in one step, that is, if (x, y) is an edge then (y, x) is an edge (in this case the graph is called nonoriented) . If we can go, in a finite number of steps, from x to y and back then we say that x and y communicate. The set of vertices which communicate with x is called the connected component containing x; if there is only one connected component, we say that the graph is connected. Of course, if two vertices belong to two disjoint connected components then the distance between them is infinite. In Figure [1] there is an example of an infinite graph which is connected if the dashed arrow is an edge and it has two connected components otherwise (the double arrows mean that you can move forth and back between the points, thus the graph is nonoriented). The central concept in this paper is the one of contractive map (see also [2, 3j). Definition 1.1. Let {X,d) and {Y, p) be two metric spaces; a function f : X Y is contractive if and only if for any x,y X, such that x^y, we have p{f{x),f{y)) < d{x,y). The map is called a contraction if there exists k <1 such that p{f{x),f{y)) < kd{x,y) for all x,y G X. Roughly speaking a map is contractive if it (stricly) reduces the distances between points; if the ratio of reduction has an upper bound which is (stricly) smaller than 1, then we have a contraction. Clearly, any contraction is a contractive map and the two classes coincide on finite metric spaces. We are (mainly) interested in the case X = Y and d = p. Observe that in our original problem, if we denote by f{x) the new position of the person who was at x before, what we are looking for are nonconstant, contractive maps. Any constant map is trivially contractive; when the converse is true? The main result Theorem 12.11 characterizes all the discrete metric spaces, satisfying a certain property (see (|2.1|) below)), which have nonconstant contractive maps. As a simply consequence of Theorem 12.11 we will see that every contractive map on a graph with the natural distance is a constant function if and only if the graph is connected. 2 2. Main results and examples Let us consider a discrete metric space {X, d) (which is a metric space such that for any given point x G X it is possible to find e > such that d{x, y) > e for all y G X \ {x}) and let us assume that (the existence of the minimum is implicitly assumed). Roughly speaking, according to equa- tion (|2.ip . the distance either equals or it is at least do; this implies that if d{x,y) < do then X = y. We define, once and for all, do := d(xo,yo) and we introduce the equivalence relation ~ defined by x ~ y if and only if there exists {xi}f^Q such that xq = x, Xn = y and d{xi, Xj+i) = do for any z = 0, 1, . . . , n — 1 (if n > 0). Hence, two points x and y are equivalent if and only if we can reach y from x by performing a finite number of jumps of length do. We denote by [x], the equivalence class induced hy x £ X, that is, [x] := {y : y ~ x}. As usual, the quotient space X/^ is the set of the equivalence classes. It is easy to show that, for any x,y & X such that x ^ y, we have y G [x] if and only if there exists z G [x] satisfying d{y, z) = do. We denote by d^^ the metric on X/r. defined by d^([x], [y]) := mi^,(,[^]^y,fz[y] d{x,y). Examples of discrete metric spaces satisfying equation (|2.ip are finite metric spaces and (nonori- ented) graphs with their natural distance; in the last case we have do = 1 and the quotient space X/ ^ is the set the connected components of the graph. We are ready to state and prove the main result of this paper. Theorem 2.1. Let {X,d) be a metric space satisfying equation (|2.1|) ; then TFAE (i) there exists a nonconstant contractive map on X; (ii) there exists x (z X such that [x] ^ X; (Hi) for every x & X , we have [x] ^ X ; Moreover there is a one-to-one map from the set of contractive maps Cm{X) into the set Cm{X/ ^] X) of contractive maps from X/ ^ to X. 3xo, yo ^ X such that < d{xo, yo) = min{(i(x, y) : x,y & X,x ^ y} (2.1) (iv) #X/^ > 1. Proof (i) =^ {ii). If / is contractive and d{x,y) = do then d{f{x),f{y)) < do which implies, by equation (j2.ip . f{x) = f{y); hence f\[x], the function / restricted to the class [x], is a constant function for any x G X. Hence, if / is nonconstant we have [x] ^ X. {Hi) (i). We have that Y := X \ [xq] / 0; let us define a function / by 3 where d{xQ,yo) = do- It is just a matter of easy computation to show that this is a nonconstant contractive map (indeed for any x £ [xq], y £Y we have d{x, y) > do)- {a) {iv). It is an easy consequence of the fact that for all y,x £ X , y ^ [x] if and only if [y\ 7^ [x] which, in turn, is equivalent to [y\ PI [x] = 0. Finally, it is easy to show that, given a contractive map /, the map (pif) is well defined by 4>{f){[x\) := f{x) (since / is constant on every class [x]). It is straightforward to show that (p is injective and, clearly, being / a contractive map, d{(l){f){[x]), (p{f){[y])) = d{f{x),f{y)) = d{f{x'),f{y')) < d{x',y') for ah x' ~ a; and y' ~ y. This implies that d{(j){f){[x]), ^{f){[y])) < d^{[x], [y]), thus (/>(/) is a contractive map from X/^ to X. □ Let us observe that if the range of the distance Ran((i) is a finite set (take for instance X finite) then any contractive map / is actually a contraction and there is no € N such that the n-th iteration /("^ is a constant map for ah n > no and = Indeed, d(/(")(x), /(")(y)) < k"'d{x,y) < k"" maxx'^y'£x d{x' ,y'), hence if no > \og{do/ maxx'^y'(zx d{x' ,y'))/ log{k) then is constant (say, = Xoo for ah x G X). If n > no then /("^(x) = /("o)(/(n-no)(a:)) = Xoo- Clearly fixoo) = /(/^""H^oo)) = /^""^/(s^oo)) = Xoo, that is, Xoo is (the unique) fixed point of /. Indeed, it is possible to prove (see [U Theorem 9.3]) that for any contraction / in a (complete) metric space there exists Xqo = lim„, /("^(x) exists and it is the unique fixed point for /, that is, f{xoo) = Xoo- A generic contractive map / has at most one fixed point, since x = /(x), y = f{y) and X ^ y implies ^ d{x,y) = d{f{x),f{y)) < d{x,y) which is a contradiction. Nevertheless, if Ran((i) is not a finite set then the set of fixed points of / might be empty as Example 12.31 shows. In the language of our original problem, x is a fixed point if and only if the member of the group living at x does not move. Moreover if ^X/^ = 1 then the three classes of contractive maps Cm{X), contractions Ct{X) and constant functions Cnst{X) coincide. Corollary 2.2. Let {X, d) he a metric space such that there are just two couples satisfying equa- tion (|2.1|) (namely (xo,yo) o,nd {yo,xo)); if #X > 2 then there exists a non constant contractive map. Example 2.3. Consider X = N and define the distance as follows 'l (x,y) G {(0,1),(1,0)} 2 ix,y) e {(0,2), (2,0), (1,2), (2,1)} d{x, y):= {l + 1/i (x, y) G {(i, i + l),{i + l,i)} 2 + (l + l/2) + --- + (l + l/i) (x,y) € {(0,i + l),(l,i + l),(i + l,0),(i + l,0)} ^(l + l/i) + --- + (l + l/i) (x,y) e {(i,i + l),(j + l,i)} where 2 < i < j ( see Figure [21 for a picture of a finite portion of this space along with the distances between "consecutive" points). In this case it is easy to prove that the following is a contracting • 3/2 • 4/3 • — 5/4 • 6/5 '2 3 4 5 Figure 2: The metric space of Example |2.3l map without fixed points fix) X G {0,1} 1 x = i>2. In the following we compare the relations between Cm{X), Ct{X) and Cnst{X). Clearly Cra{X) 5 Ct{X) ^ Cnst{X); we provide examples to show that, even if equation (j2.ip holds, all cases are possible. Given A C X, by we mean the usual characteristic function of A (which equals 1 on A and elsewhere). The reader is encouraged to verify that, in the following examples, the spaces we define are indeed metric spaces. Example 2.4. Let X := {0, 1, 2} and d he defined by d{0, 1) = 0) := 1, d{l, 2) = d{2, 1) := 2, d{0,2) = d{2,0) := 3 and otherwise; then f{x) := X{2}{x) ^ nonconstant contraction. Another example (in the infinite case) is the following. Let X = N and define the distance by ifx = y, d{x,y) := <^ 1 G{(0,1),(1,0)}, ,2 i/(x,y) 0{(O,1),(1,O)}, x/y, then f{x) := X{o,i}<=(^) « nonconstant contraction. In the previous examples Cm{X) = Ct{X) / Cnst{X) since the range of the distance is finite. Example 2.5. Let X :- d{x,y) : and let d be defined as follows fO ifx = y, 1 if{x,y)e{{0,l),{l,0)}, 1 + i if 1 < X < y or X = 0, y > 1, 1 + ^ if 1 < y < X or y = 0, X > I. In this case it is easy to check that this is a distance and that fix): lO if xe {0,1}, [ X + 1 if X > 1, is a contractive map which is not a contraction while fix) tfx^2, 1 ifx = 2, is a (nonconstant) contraction with k equal to 2/3. Hence Cm{X) ^ Ct{X) ^ Cnst{X). In Theorem 12.11 to prove that every contractive map is a constant map, we require that all the points belong to the same class, that is, we can reach y from x with a finite number of consecutive steps of length do (for any choice oi x^y ^ X, x ^ y). To prove an analogous result for contractions we do not need such a strong property: we simply require that any two different points can be joined by a sequence of consecutive steps whose lengths are arbitrarily close to do- The following result is used in Example 12.71 to construct a space where every contraction is a constant map but there are nonconstant contractive maps. Proposition 2.6. // equation (j2.ip holds and for all € X, e > 1 there exists {xi}'^^-^ € X such that, and ^(xj, Xj+i) < edo for all i = 0,1, ... n — 1 then any contraction from X into itself is constant. Proof. Suppose that d{f{x),f{y)) < kd{x,y) for all x,y G X where k < 1. Define e := 2/{k + 1); it is clear that for alH = 0, 1, . . . , n — 1 we have that 2k d{f{xi),f{xi+i)) < kdoe = -^rpy^o < 4 which implies /(xj+i)) = and f{xi) = /(xj+i). Thus f{x) = f{x'). □ Example 2.7. Let X := N and let d he defined as follows '0 ifx = y. d{x,y) :-- 1 i/(x,y) G {(0,1),(1,0)}, 1 + J ifx = 0,y>l, tl + i i/y = 0, x>l. It is easy to check that this is a distance and that the hypotheses of Proposition \2.6\ are satisfied (since liuiy-^oo d{x,y) = 1 = d^, we can always take n = 2 and xi € N sufficiently large). Hence in this case any contraction is a constant function. Nevertheless I X + 1 if x > 1, is a (nonconstant) contractive map. Hence Cm{X) ^ Ct{X) = Cnst{X). Let us consider now a nonoriented graph along with its natural distance d. li AQ X, dA '^s the natural distance restricted to A x A and d^ := m.va.{dA{x,y) : x,y ^ A,x ^ y}, then condition (ii) of Theorem 12.11 is equivalent to the existence, given any couple of vertices x,y € A, of a finite sequence {x =: xq, . . . , x„ := y} of vertices in A such that dA{xi, Xj+i) = do for alH = 0, . . . , n — 1. In particular if := 1 then any contractive map on A is constant if and only if yl is a connected subgraph. By taking A = X we have that there are no nonconstant, contractive maps on X if and only if X is a connected graph. 3. Conclusions We come back to our original question: may the group of people move according to the rules (i) and (ii) as stated in Section [l]? We may reasonably suppose that the group is finite and with cardinality strictly greater than 2 (if there are just 2 people then any contractive map is constant and they cannot move). Hence the metric space is finite and equation (j2.ip is fulfilled. Moreover one can assume that to different couples of places correspond different distances (i.e. if {x,y) / (xi,yi) and (x,y) ^ {yi,xi) then d{x,y) ^ d{xi,yi) unless x = y and xi = yi). Under these assumptions, according to Corollarv 12.21 we know that the group can move. Moreover, since the contractive map in this case is a contraction, there exists one (and only one) person who does not move at all (this is the fixed point of the contraction). References [1] B.BoUobas, Modern graph theory, Graduate Texts in Mathematics, 184. Springer- Verlag, New York, 1998. [2] M. Geraghty, On contractive mappings, Proc. Amer. Math. Soc. 40 (1973), 604608. [3] W. A. Kirk, B. Sims (Eds.), Handbook of Metric Fixed Point Theory, Kluwer Academic, 2001. [4] W. Rudin, Principles of mathematical analysis (3rd ed.), International Series in Pure and Apphed Mathematics, McGraw-Hill, New York, 1976. F. ZUCCA, DiPARTIMENTO DI MATEMATICA, POLITECNICO DI MiLANO, PiAZZA LEONARDO DA ViNCI 32, 20133 MiLANO, Italy. E-mail address: fabio.zucca@polimi.it 7