It is also noted that a geodesically bounded completeR-tree has the fixed point property for continuous mappings

(1)

W. A. KIRK

Received 10 June 2004

We show that ifUis a bounded open set in a complete CAT(0) spaceX, and if f :U→Xis nonexpansive, then f always has a fixed point if there existsp∈Usuch thatx /∈[p,f(x)) for allx∈∂U. It is also shown that ifKis a geodesically bounded closed convex subset of a completeR-tree with int(K)= ∅, and if f :K →X is a continuous mapping for whichx /∈[p,f(x)) for some p∈int(K) and allx∈∂K, then f has a fixed point. It is also noted that a geodesically bounded completeR-tree has the fixed point property for continuous mappings. These latter results are used to obtain variants of the classical fixed edge theorem in graph theory.

1. Introduction

A metric spaceXis said to be a CAT(0)space(the term is due to M. Gromov—see, e.g., [1, page 159]) if it is geodesically connected, and if every geodesic triangle inX is at least as “thin” as its comparison triangle in the Euclidean plane. It is well known that any complete, simply connected Riemannian manifold having nonpositive sectional curvature is a CAT(0) space. Other examples include the classical hyperbolic spaces, Euclidean buildings (see [2]), the complex Hilbert ball with a hyperbolic metric (see [6]; also [12, inequality (4.3)] and subsequent comments), and many others. (On the other hand, if a Banach space is a CAT(κ) space for someκ∈R, then it is necessarily a Hilbert space and CAT(0).) For a thorough discussion of these spaces and of the fundamental role they play in geometry, see Bridson and Haefliger [1]. Burago et al. [3] present a somewhat more elementary treatment, and Gromov [8] a deeper study.

In this paper, it is shown that ifUis a bounded open set in a complete CAT(0) spaceX, and if f :U→Xis nonexpansive, thenf always has a fixed point if there existsp∈Usuch thatx /∈[p,f(x)) for allx∈∂U. (In a Banach space, this condition is equivalent to the classical Leray-Schauder boundary condition: f(x)−p=λ(x−p) forx∈∂Uandλ >1.) It is then shown that boundedness ofU can be replaced with convexity and geodesic boundedness ifX is anR-tree. In fact this latter result holds for any continuous mapping. Three variants of the classical fixed edge theorem in graph theory are also obtained.

Precise definitions are given below.

2000 Mathematics Subject Classification: 54H25, 47H09, 05C05, 05C12 URL:http://dx.doi.org/10.1155/S1687182004406081

(2)

2. Preliminary remarks

Let (X,d) be a metric space. Recall that ageodesic pathjoiningx∈Xtoy∈X(or, more briefly, a geodesic from x to y) is a mapc from a closed interval [0,l]⊂RtoX such thatc(0)=x,c(l)=y, andd(c(t),c(t))= |t−t|for allt,t∈[0,l]. In particular,c is an isometry and d(x,y)=l. The image α of c is called ageodesic (ormetric)segment joiningxand y. When unique, this geodesic is denoted [x,y]. The space (X,d) is said to be ageodesic spaceif every two points ofXare joined by a geodesic, andXis said to beuniquely geodesicif there is exactly one geodesic joiningxandyfor eachx,y∈X. A subsetY_⊆Xis said to beconvexifY includes every geodesic segment joining any two of its points.

For complete details and further discussion, see, for example, [1] or [3].

Denote byM_κ²the following classical metric spaces:

(1) ifκ=0 thenM²0is the Euclidean planeE²;

(2) ifκ >0 thenM_κ²is obtained from the classical sphereS²by multiplying the spher- ical distance by 1/^√κ;

(3) ifκ <0 thenM_κ²is obtained from the classical hyperbolic planeH²by multiplying the hyperbolic distance by 1/^√−κ.

Ageodesic triangle∆(x1,x2,x3) in a geodesic metric space (X,d) consists of three points inX(theverticesof∆) and a geodesic segment between each pair of vertices (theedgesof

∆). Acomparison trianglefor geodesic triangle∆(x1,x2,x3) in (X,d) is a triangle∆(x1,x2, x3) :=∆( ¯x1, ¯x2, ¯x3) inM_κ² such thatd_R²( ¯xi, ¯xj)=d(xi,xj) fori,j∈ {1, 2, 3}. Ifκ >0 it is further assumed that the perimeter of ∆(x1,x2,x3) is less than 2D_κ, whereD_κ denotes the diameter of M_κ². The triangle inequality assures that comparison triangles always exist.

A geodesic metric space is said to be a CAT(κ) space if all geodesic triangles of appro- priate size satisfy the following CAT(κ) comparison axiom.

CAT(κ). Let∆be a geodesic triangle inXand let∆⊂M_κ²be a comparison triangle for∆. Then∆is said to satisfy the CAT(κ)inequalityif for allx,y∈∆and all comparison points ¯x, ¯y∈∆,

d(x,y)≤d( ¯x, ¯y). (2.1)

Of particular interest in this note are the complete CAT(0) spaces, often called Hadamard spaces. These spaces are uniquely geodesic and they include, as a very special case, the following class of spaces.

Definition 2.1. AnR-tree is a metric spaceTsuch that

(i) there is a unique geodesic segment (denoted by [x,y]) joining each pair of points x,y∈T;

(ii) if [y,x]∩[x,z]= {x}, then [y,x]∪[x,z]=[y,z].

Proposition2.2. The following relations hold.

(1)IfXis aCAT(κ)space, then it is aCAT(κ)space for everyκ≥κ.

(2)Xis aCAT(κ)space for allκif and only ifXis anR-tree.

(3)

One consequence of (1) and (2) is that any result proved for CAT(0) spaces automati- cally carries over to any CAT(κ) spaces forκ <0, and, in particular, toR-trees.

3. Fixed point theorems

We use the following continuation principle due to Granas in the proof of our first result.

Theorem3.1 [7]. LetUbe a domain in a complete metric spaceX, letf,g:U→Xbe two contraction mappings, and suppose there existsH:U×[0, 1]→Xsuch that

(a)H(·, 1)= f,H(·, 0)=g;

(b)H(x,t)=xfor everyx∈∂Uandt∈[0, 1];

(c)there existsα <1such thatd(H(x,t),H(y,t))≤αd(x,y)for everyx,y∈Uandt∈ [0, 1];

(d)there exists a constantM≥0such that for everyx∈Uandt,s∈[0, 1],

dH(x,t),H(x,s)≤M|s−t|. (3.1) Then f has a fixed point if and only ifghas a fixed point.

We will also need the following lemma due to Crandall and Pazy.

Lemma3.2 [4]. Let {zn} be a subset of a Hilbert spaceH and let{rn} be a sequence of positive numbers. Suppose

zn−zm,rnzn−rmzm

≤0, form=1, 2,. . . . (3.2) Then ifr_nis strictly decreasing,z_nis increasing. Ifz_nis bounded,lim_n_→∞z_nexists.

Theorem3.3. LetUbe a bounded open set in a completeCAT(0)spaceX, and suppose f : U→Xis nonexpansive. Suppose there existsp∈Usuch thatx /∈[p,f(x))for allx∈∂U.

Then f has a fixed point inU.

WhenXis a Hilbert space,Theorem 3.3holds under the even weaker assumption that f is a lipschitzian pseudocontractive mapping. This has been known for some time (see [13]). Our proof is patterned after Precup’s Hilbert space proof [10] for nonexpansive mappings. We observe here that the CAT(0) inequality is suﬃcient.

Proof ofTheorem 3.3. Lett∈(0, 1) and foru∈U let ft(u) be the point of the segment [p,f(u)] with distancetd(p,f(u)) fromp. Letx,y∈Uand consider the comparison triangle ¯∆=∆( ¯p, ¯x, ¯y) of∆(p,x,y) inE². If ¯ft(x) and ¯ft(y) denote the respective comparison points of ft(x) and ft(y) in ¯∆, then by the CAT(0) inequality,

dft(x),ft(y)≤f¯t(x)−f¯t(y)=tx¯−y¯ =td(x,y). (3.3) Therefore f_t is a contraction mapping ofU→X. Moreover, ifB(p;r)⊂U, then f_t:U→ B(p;r) fortsuﬃciently small. Thus fthas a fixed point fortsuﬃciently small. Now let λ∈(0, 1). We applyTheorem 3.1to show that fλhas a fixed point. Define the homotopy H:U×[0, 1]→Xby settingH(x,t)=f_λt(x). ThenH(·, 1)=f_λandH(·, 0) is a constant map. IfH(x,t)=x for somex∈∂U andt∈[0, 1], then f_λt(x)=x andx∈[p,f(x)).

(4)

Since this is not possible, condition (b) ofTheorem 3.1holds. Condition (c) holds upon takingαto beλ. Finally,

dH(x,t),H(x,s)≤ |s−t|dp,f(x), (3.4) for allt,s∈[0, 1], and sinceUis bounded, condition (d) holds. Therefore, byTheorem 3.1, fλ has a unique fixed point, and it follows that ft has a unique fixed pointxt for each t∈(0, 1).

Now denote byxn,n∈N, the pointxt fort=1−1/n. Form,n∈N,m,n >1, consider the comparison triangle ¯∆=∆(0, ¯f(xm), ¯f(xn)) of∆(p,f(xm),f(xn)) inE², and let

¯

x_m, ¯x_ndenote the respective comparison points ofx_m,x_n. Then, using the fact that f is nonexpansive in conjunction with the CAT(0) inequality,

f¯xm

−f¯xn=dfxn ,fxm

≤dxn,xm

≤x¯n−x¯m. (3.5) Consequently, ifrm=(m−1)⁻¹andrn=(n−1)⁻¹,

rnx¯n−rmx¯m, ¯xn−x¯m

=f¯xn

−f¯xm

, ¯xn−x¯m

−x¯n−x¯m²≤0. (3.6)

Since{rn}is strictly decreasing,{x¯n}converges byLemma 3.2. Since d(xn,xm)≤d( ¯xn, x¯m),{xn}converges as well, necessarily to a fixed point of f. It is noteworthy that in the preceding result the domainUisnotassumed to be convex.

An entirely diﬀerent approach yields a stronger result ifXis anR-tree. For this result we do require convexity of the domain, but the boundedness assumption is relaxed, and the result holds for continuous mappings. We begin with the following fact, which illus- trates that compactness is not necessary for continuous mappings to have fixed points in completeR-trees. This fact may be known, perhaps as a special case of more abstract theory, but it does not seem to be readily found in the literature.

Theorem3.4. SupposeXis a geodesically bounded completeR-tree. Then every continuous mapping f :X→Xhas a fixed point.

Proof. Foru,v∈Xwe let [u,v] denote the (unique) metric segment joininguandvand let [u,v)=[u,v]\{v}. We associate with each pointx∈X a pointϕ(x) as follows. For eacht∈[x,f(x)], letξ(t) be the point ofXfor which

x,f(x)∩

x,f(t)=

x,ξ(t). (3.7)

(It follows from the definition of anR-tree that such a point always exists.) Ifξ(f(x))= f(x) takeϕ(x)=f(x). Otherwise it must be the case thatξ(f(x))∈[x,f(x)). Let

A= t∈

x,f(x):ξ(t)∈[x,t] ; B=

t∈

x,f(x):ξ(t)∈

t,f(x) . (3.8)

(5)

ClearlyA∪B=[x,f(x)]. Sinceξ is continuous, bothAandBare closed. AlsoA= ∅ as f(x)∈A. However, the fact that f(t)→ f(x) ast→ximpliesB= ∅(becauset∈A impliesd(f(t),f(x))≥d(t,x)). Therefore there exists a pointϕ(x)∈A∩B. Ifϕ(x)=x, then f(x)=xand we are done. Otherwisex=ϕ(x) and

x,f(x)∩

x,fϕ(x)=

x,ϕ(x). (3.9)

Now let x0∈X and letx_n=ϕⁿ(x0). Assuming that the process does not terminate upon reaching a fixed point of f, by construction, the points{x0,x1,x2,. . .}are linear and thus lie on a subset ofX which is isometric with a subset of the real line, that is, on a geodesic. SinceXdoes not contain a geodesic of infinite length, it must be the case that

∞ i=0

dxi,xi+1

<∞, (3.10)

and hence that{x_n}is a Cauchy sequence. Suppose lim_n_→∞x_n=z. Then

nlim→∞fxn

=f(z) (3.11)

by continuity, and in particular{f(xn)}is a Cauchy sequence. However, by construction, dfxn

,fxn+1

=dfxn ,xn+1

+dxn+1,fxn+1

. (3.12)

Since limn→∞d(f(x_n),f(x_n+1))=0, it follows that limn→∞d(f(x_n),x_n+1)=d(f(z),z)=0

and f(z)=z.

Theorem3.5. Let(X,d)be a complete R-tree, supposeK is a closed convex subset ofX which does not contain a geodesic ray, supposeint(K)= ∅, and suppose f :K→Xis con- tinuous. Suppose there existsp0∈int(K)such thatx /∈seg[p0,f(x))for everyx∈∂K. Then

f has a fixed point inK.

Proof. SinceKis a closed convex subset of a CAT(0) space, the nearest point projectionP ofXontoKis nonexpansive (see, e.g., [1, page 176]). Therefore the mappingP◦f :K→ Kis continuous and has a fixed point byTheorem 3.4. Ifx∈K then it must be the case that f(x)=xbecauseP◦f(x)∈∂K. On the other hand, ifx∈∂K, thenP◦f(x)=x implies thatxis on the segment joiningp0and f(x), which is a contradiction.

Another consequence ofTheorem 3.4 is an analog of Ky Fan’s best approximation theorem for geodesically boundedR-trees. This theorem actually includesTheorem 3.4;

howeverTheorem 3.4is used in the proof.

Theorem3.6. Let(X,d)be a complete R-tree, supposeK is a closed convex subset ofX which does not contain a geodesic ray, and suppose f :K→X is continuous. Then there existsx0∈Ksuch that

dx0,fx0

≤dx,fx0

(3.13) for everyx∈K.

(6)

Proof. IfP is the nearest point projection ofXontoK, then any pointx0for whichP◦

f(x0)=x0satisfies the conclusion.

Remark 3.7. The analog ofTheorem 3.4does not hold for CAT(0) spaces, even for nonexpansive mappings. Ray [11] has shown that a closed convex subset of a Hilbert space has the fixed point property for nonexpansive mappings if and only if it is linearly bounded.

4. Applications in graph theory

Agraphis an ordered pair (V,E) whereV is a set andEis a binary relation onV (E⊆ V×V). Elements ofEare callededges. We are concerned here with (undirected) graphs that have a “loop” at every vertex (i.e., (a,a)∈Efor eacha∈V) and no “multiple” edges.

Such graphs are calledreflexive. In this caseE⊆V×V corresponds to a reflexive (and symmetric) binary relation onV.

Given a graphG=(V,E), a path ofGis a sequencea0,a1,. . .,a_n₋1,. . .with (a_i+1,a_i)∈ Efor each i=0, 1, 2,. . . . Acycle is a finite path (a0,a1,. . .,an−1) with (a0,an−1)∈E. A graph is connectedif there is a finite path joining any two of its vertices. A finite path (a0,a1,. . .,a_n₋1) is said to have length n. Finally, atree is a connected graph with no cycles.

LetG=(V,E) be a graph andG1=(V1,E1) a subgraph ofG. A mapping f :V1→V is said to beedge preserving if (a,b)∈E1 implies (f(a),f(b))∈E. For such a mapping we simply write f :G1→G. There is a standard way ofmetrizingconnected graphs; let each edge have length one and take distanced(a,b) between two verticesaandb to be the length of the shortest path joining them. With this metric, the edge-preserving mappings becomenonexpansivemappings. (In a reflexive graph an edge-preserving map may collapse edges between distinct points since loops are allowed.)

The classical fixed edge theorem in graph theory due to Nowakowski and Rival [9] as- serts that an edge preserving mapping defined on a connected graph which has no cycles or infinite paths always leaves some edge of the graph fixed. Although the focus in this area has shifted to other fixed structures in graphs other than trees, it seems worthwhile to illustrate how the preceding result can be applied in graph theory. In [5] the fixed edge theorem is extended as follows.

Theorem4.1 [5]. Let Gbe a reflexive graph which is connected, contains no cycles, and contains no infinite paths. SupposeFis a commuting family of edge-preserving mappings of Ginto itself. Then, either

(a)there is a unique edge inGthat is left fixed by each member ofF, or (b)some vertex ofGis left fixed by each member ofF.

We now useTheorem 3.5to give another variant of the fixed edge theorem. LetGbe a graph and letG1be a subgraph ofG. A vertexp0∈G1is said to be interior if given any vertexx∈G, the path joiningp0andx contains a point p1∈G1 for which p1=p0. A pointp∈G1is said to be a boundary point ofG1ifpis not an interior vertex.

Proposition4.2. LetGbe a connected reflexive graph which contains no cycles, and let G1 be a connected subgraph ofGwhich contains an interior vertex p0, and which contains no infinite path. Let f :G1→Gbe an edge-preserving mapping, and supposepdoes not lie

(7)

on the path joiningp0and f(p)for any boundary pointp∈G1. Then f either leaves some vertex ofG1fixed or leaves a unique edge ofG1fixed.

Proof. Since a connected graph with no cycles is a tree, one can construct from the graph GanR-treeTby identifying each (nontrivial) edge with a unit interval of the real line and assigning the shortest path distance to any two points ofT. It is easy to see that with this metricTis complete and thatG1induces a subtreeT1inT. It is now possible to extendf aﬃnely on each edge to the corresponding unit interval ofT1, and the resulting mapping

f˜is a nonexpansive mapping ofT1→T. Alsop∈∂T1if and only ifpis a boundary point ofG1, and by assumptionp /∈[p0, ˜f(p)) for such a pointp. Therefore ˜f has a fixed point zbyTheorem 3.5. Eitherzis a vertex ofG, orzlies properly on the unit interval joining the vertices of some edge (a,b) ofG. In this case (since the fixed point set of ˜f is convex) the only way f can fail to leave some vertex ofGfixed is forzto be the midpoint of the metric interval [a,b], with f(a)=band f(b)=a. In this case (a,b) is the unique fixed

edge of f.

Theorem 3.4similarly leads to an extension of the fixed edge theorem.

Proposition4.3. LetG=(V,E)be a reflexive graph which is connected, contains no cycles, and contains no infinite paths. Suppose f :V→2^Vhas the property that f(a)is a path inG for eacha_∈V, and alsof(a)_∪f(b)is a path for each(a,b)_∈E. Then some edge(a,b)_∈E lies in the path f(a)∪f(b).

Proof. Construct anR-treeT as in the preceding proof and define ˜f by choosing ˜f(a) and ˜f(b) to be endpoints of f(a)∪f(b) with ˜f(a)∈ f(a) and ˜f(b)∈f(b), and extend f˜aﬃnely to obtain a mapping ˜f : [a,b]→[ ˜f(a), ˜f(b)]. Then ˜f is continuous and by Theorem 3.4 f˜has a fixed point which lies on some edge (a,b) ofG. Clearly this implies

that (a,b)⊂f(a)∪f(b).

The preceding result reduces to the classical fixed edge theorem if f :V→V. Finally, fromTheorem 3.6one can obtain the following.

Proposition4.4. LetGbe a connected reflexive graph which contains no cycles, letG1be a connected subgraph ofGwhich contains no infinite path, and let f :G1→Gbe an edge- preserving mapping. Then either some edge ofG1is fixed, or there exists a vertexainG1such thatalies on the path joiningband f(a)for eachb∈G1.

References

[1] M. R. Bridson and A. Haefliger,Metric Spaces of Non-Positive Curvature, Grundlehren der Mathematischen Wissenschaften, vol. 319, Springer-Verlag, Berlin, 1999.

[2] K. S. Brown,Buildings, Springer-Verlag, New York, 1989.

[3] D. Burago, Y. Burago, and S. Ivanov,A Course in Metric Geometry, Graduate Studies in Mathe- matics, vol. 33, American Mathematical Society, Rhode Island, 2001.

[4] M. G. Crandall and A. Pazy,Semi-groups of nonlinear contractions and dissipative sets, J. Func- tional Analysis3(1969), 376–418.

[5] R. Esp´ınola and W. A. Kirk,Fixed point theorems inR-trees with applications to graph theory, preprint, 2004.

(8)

[6] K. Goebel and S. Reich,Uniform Convexity, Hyperbolic Geometry, and Nonexpansive Mappings, Monographs and Textbooks in Pure and Applied Mathematics, vol. 83, Marcel Dekker, New York, 1984.

[7] A. Granas,Continuation method for contractive maps, Topol. Methods Nonlinear Anal.3(1994), no. 2, 375–379.

[8] M. Gromov,Metric Structures for Riemannian and Non-Riemannian Spaces, Progress in Math- ematics, vol. 152, Birkh¨auser Boston, Massachusetts, 1999.

[9] R. Nowakowski and I. Rival,Fixed-edge theorem for graphs with loops, J. Graph Theory3(1979), no. 4, 339–350.

[10] R. Precup,Continuation results for mappings of contractive type, Semin. Fixed Point Theory Cluj-Napoca2(2001), 23–40.

[11] W. O. Ray,The fixed point property and unbounded sets in Hilbert space, Trans. Amer. Math. Soc.

258(1980), no. 2, 531–537.

[12] S. Reich and I. Shafrir,Nonexpansive iterations in hyperbolic spaces, Nonlinear Anal.15(1990), no. 6, 537–558.

[13] J. Reinermann and R. Sch¨oneberg,Some results and problems in the fixed point theory for non- expansive and pseudocontractive mappings in Hilbert-space, Fixed Point Theory and Its Ap- plications (Proc. Sem., Dalhousie Univ., Halifax, Nova Scotia, 1975) (S. Swaminathan, ed.), Academic Press, New York, 1976, pp. 187–196.

W. A. Kirk: Department of Mathematics, The University of Iowa, Iowa City, IA 52242-1419, USA E-mail address:[email protected]