Universal maps on trees

Carl Eberhart and J.B. Fugate Department of Mathematics University of Kentucky Lexington, Kentucky 40506 January 10, 1997
A map f : R ! S of continua R and S is called a universal map from R to S if for any map g : R ! S , f (x) = g(x) for some point x 2 R. When R and S are trees, we characterize universal maps by reducing to the case of light minimal universal maps. The characterization uses the notions of combinatorial map and folded subedge of R. MOS Subject Classi cation Primary: 54H25 Secondary: 54F20 Key Words: minimal universal, combinatorial, tree, xed point property

Abstract

A map or mapping is a continuous function. A continuum is a compact, connected metric space. If X and Y are topological spaces, then a map f : X ! Y is universal provided that if g : X ! Y is a map, then there is a point x 2 X at which f and g agree, i. e., f (x) = g (x). The notion is due to Holsztynski 2], who showed the following property. 1.1 Property If X is connected, Y is an arc, and f : X ! Y is a surjection, then f is universal. We prove this by establishing a related property. 1.2 Property Suppose that X is connected, and Y contains an arc ab whose complement is the union of two disjoint open sets U and V with U n U fag and V n V fbg. If h; k : X ! Y are maps with h(X ) ab k(X ), then h and k agree somewhere. Proof: Assume that h and k do not agree anywhere. Order ab so that a < b. Now let L = k 1 (U ) fx 2 X jk(x) 2 ab and k(x) < h(x)g and let W = k 1 (V ) fx 2 X jk(x) 2 ab and h(x) < k(x)g. Then L and W are disjoint nonempty open sets whose union is X . This contradicts the connectedness of X and so h and k must agree somewhere. 2

1 Introduction.

Proof of 1.1: Let g : X ! Y be a map. Apply 1.2 with g = h and f = k. 2

Thus X has the xed point property if and only if the identity map on X is universal. Moreover, if f : X ! Y is universal, then Y has the xed point property (if g : Y ! Y is a map, then f and gf must agree at some x 2 X . Hence f (x) is a xed point of g .) Also, universal maps (to T1 spaces) must be surjections (otherwise, there would be a constant map g which never agrees with f ). Universal mappings are used in xed point theory. A topological space has the xed point property provided that every map f : X ! X has a xed point (i.e., f (x) = x for some x 2 X .

It follows quickly from 1.1 and this last remark that the universal maps to an arc are completely characterized as the surjective maps to the arc. Hollzstnski 3] characterized the universal maps to an n-ball as the AH-essential mappings (also see 4]). We wish to thank the referee for these references and also for their helpful location of errors in the rst (and second) versions of this manuscript. One can pose the general problem: 1.3 Problem: Suppose X and Y are continua and Y has the xed point property. Characterize the universal mappings from X to Y . A tree is a continuum which is the union of a nite collection of arcs, and contains no simple closed curve. It is well-known that trees have the xed point property, and in fact universal mappings on trees have been studied by Marsh 5, 6]. In 5], he introduced the notion of a umapping of trees and showed that all u-mappings are universal. The list of ve properties which he used to de ne u-maps does not characterize universal maps on trees, and the goal of this paper is to completely characterize universal maps on trees (see Theorem 6.3). We now establish some terms and notation. Let R be a tree. Then between any pair of points x and y in R there is a unique arc which we denote by xy . The order of a point p 2 R, denoted by ordR(p), is the number (necessarily nite) of components of the complement of the point. A point p 2 R is an endpoint of R or branchpoint of R according to whether ordR (p) = 1 or ordR(p) 3. A point of R is a vertex of R if it is either an endpoint or a branchpoint of R. We use the notation ER, BR , and VR to denote the set of endpoints, branchpoints, and vertices of R respectively. If x; y 2 VR, then xy is called an edge of R provided xy contains no vertex other than x and y . If also x or y is an endpoint, then we call xy a terminal edge of R. 2

1.4 De nition If x and y are distinct points of R with x 62 ER, then by Cx(y) we mean the closure of the component of R n fxg which contains y ; clearly, Cx(y ) is a subtree of R with a onepoint boundary in R. More generally, a branch of R is any subtree of R with a one point boundary
in R.

2 A reduction of the problem to the light case.

In this section, we will show that we can assume that we are working with a light minimal universal map. The following lemma will be used several times in the paper. First, we introduce some convenient terminology. 2.1 De nition Let f : R ! S be a map of trees. Then a map g : R ! S is said to miss f provided that for all x 2 R, f (x) 6= g (x). Thus f is universal if and only if no map from R into S misses f .

2.2 Lemma Suppose that f : R ! S is a map of trees which is not universal and F = fx ; ; xng is a nite subset of R. Then there is a map g : R ! S such that g misses f and g (F ) ES . Proof. Let g0 : R ! S be a map which misses f . For each i = 1; ; n, let Ki be a closed connected set containing xi in its interior such that f (Ki) and g 0(Ki) are disjoint. Since F is nite, we can also choose the sets Ki so that they are pairwise disjoint. Let ei be an endpoint of S such that the arc from ei to g 0(Ki) is disjoint from f (Ki). Then ei g 0(xi ) g 0(Ki) is a tree and hence an absolute retract; so we can de ne a map hi : Ki ! ei g 0(xi ) g 0(Ki ) so that hi (t) = g 0(t) for t in the boundary of Ki and hi (xi ) = ei . Then the map g : R ! S given by g (x) = hi (x) if x lies in the interior of Ki and g (x) = g 0(x) otherwise is the desired map. 2
1

In what follows, we will say that the map g constructed as in 2.2 is endpoint valued on F . A map is light if the point inverses are totally disconnected and monotone if the point inverses are connected. Let f : X ! Y be a map of continua. Let M denote the decomposition space whose points are the components of point inverses of f , and let m denote the natural mapping from X onto M . Then m is monotone and the induced map l : M ! Y is light. This factorization is called the monotone-light factorization of f . It is shown in 8] page 165] that if X is a tree, then so is M . We shall refer to M as the middle space of f . If g : X ! Y is a map which is constant on the components of point inverses under f , then there is a unique map g ^ : M ! Y such that g=g ^m. We shall describe this by saying g factors through the middle space of f .

2.3 Lemma Suppose f; g : 0; 1] ! S are maps which miss each other, with f non-constant. Then there is a map h : 0; 1] ! S which misses f , agrees with g at 0 and 1, and factors through the middle space of f .
h( 0; 1]) = g (0). Otherwise, let A be an arc in g ( 0; 1]) from g (0) to g (1), and let I be the middle space of the map f . Since f is nonconstant, I is an arc. Let : 0; 1] ! I be the natural map and let p : I ! A be a homeomorphism with p( (0)) = g (0) and p( (1)) = g (1). Then h = p is the

Proof. Assume for the moment that g( 0; 1]) and f ( 0; 1]) are disjoint. If g(0) = g(1), let

required map. Now in case g ( 0; 1]) and f ( 0; 1]) overlap, we can partition 0; 1] into nitely many subintervals a; b] such that f ( a; b]) and g ( a; b]) are disjoint for each subinterval a; b]. Apply the above construction to each subinterval and let h be the join of the maps obtained. 2 3

2.4 Theorem Suppose that f : R ! S is a map of trees which is not universal. Then there is a map g : R ! S which misses f and factors through the middle space of f . Proof. By 2.2, there is a map g0 : R ! S such that g0 misses f and g0(VR) ES . There are

nondegenerate connected subsets of trees have nonempty interior and so there are only countably many nondegenerate components of point inverses of f . Further choose the Ti 's so that distinct Ti's are disjoint. For each i, modify g 0 on Ti as follows: First note that f (Ti) and g 0(Ti) are disjoint trees in S , and g0(Ti) contains an endpoint e of S . Since g0(Ti) is an absolute retract, there is a map gi : Ti ! g 0(Ti) such that gi (t) = g 0(t) for t in the boundary of Ti and gi (Ci) = feg. Then the map l which is g 0 o of the union of the Ti's and, for each i, is gi on Ti , misses f and is constant on each component of a point inverse of f which contains a vertex. We now modify l, using 2.3. Note that any component of a point inverse of f on which l is not constant is contained in the interior of an edge of R. For each such edge pi qi of R, let ai bi be the arc such that pi ai and bi qi are components in pi qi of f 1 (f (pi )) and f 1 (f (qi )) respectively. Apply 2.3 to each ai bi to obtain maps hi : ai bi ! S which miss f on ai bi , agree with l at ai and bi , and are constant on the components of point inverses of f lying in ai bi. The map g which is l o of the union of the ai bi and, for each i, is hi on ai bi is the desired mapping. 2
factorization is universal.

only nitely many components Ci of point inverses of f which contain a vertex of R. For each such Ci , choose a subtree Ti of R containing Ci in its interior such that the boundary points of Ti in R are components of point inverses of f and f (Ti) is disjoint from g 0(Ti). We can do this because

2.5 Theorem A map of trees is universal if and only if the light factor of its monotone-light

Proof. Let f : R ! S be a map of trees and f = lm be the monotone light factorization of f . It is readily checked that if the composition of two maps is universal, then the second map is also; so l must be universal if f is. For the converse, note rst that since l is light and m is monotone, the components of the point inverses of f are precisely the point inverses of m. Suppose that f is not universal and let g be a map missing f which satis es Theorem 2.4. Then the induced map g ^ de ned on the domain of l by g ^(x) = g (m 1(x)) misses l. Hence we conclude that lm is universal if l is universal.2
Suppose that f : X ! Y is a mapping, A X and let f 0 denote f jA . If f 0 is universal, as a map to Y , then f must be universal. Thus, the behavior of f on X n A may be completely arbitrary. In order to characterize universal maps on trees, we need to restrict the map to a subtree on which f is "minimal universal".

2.6 De nition Let f : R ! S be universal map of trees. If the restriction of f to any proper subtree of R is not universal as a map to S , then we shall call f a minimal universal map to S . 2.7 Theorem If f : R ! S is a universal map of trees, then there is a subtree R of R such that f jR is a minimal universal map to S . Further, if M denotes the middle space of f and lm is the monotone-light factorization of f , then ljm(R ) is minimal universal to S . Proof. Let R be the intersection of a maximal tower of subtrees R of R such that for each , f jR is universal to S . Let h = f jR , and suppose that h is not universal to S . Let g : R ! S be a map which misses h. Now since S is an absolute retract, there is an map g 0 : R ! S which extends g . Choose > 0 so that d(h(x); g (x)) > for all x 2 R . Choose > 0 so that if x; y 2 R
4

p2

with d(x; y ) < , then d(f (x); f (y )) < =3 and d(g 0(x); g 0(y )) < =3. Now choose R so that each point of R is within of some point of R . We will show that g 0 misses f on R . Let x 2 R . Choose y 2 R so that d(x; y ) < . Now < d(h(y ); g (y )) d(f (y ); f (x)) + d(f (x); g 0(x)) + d(g 0(x); g (y )) < 2 =3 + d(f (x); g 0(x)). Hence d(f (x); g 0(x)) > 0 for all x 2 R . But this contradicts our assumption that f restricted to R is universal. So h : R ! S is universal. Now since the tower is maximal it follows that R is in the tower and h : R ! S is minimal universal to S . The proof of the last statement follows from 2.5 2

a a a a a a a a a a a a a a a
Figure 1: A combinatorial map from the H to the Y.

a1

b1

a @ @@

e1

p2

d1

p3 c1

1 @ d @

@@ @p
3

c2

3 Combinatorial maps.
We are going to de ne a class of mappings between trees called combinatorial. Later, in Section 4, we will show that light minimal universal mappings must be combinatorial. First, we de ne the notion of subedge.

3.1 De nition Let f : R ! S be a map of trees. An arc rs in R is a subedge of R provided that i) rs lies in an edge of R, and ii) there is an edge ab of S so that rs is a component of f 1 (ab).
We really should call a subedge of R an f -subedge of R, but it is always clear from the context which f we are talking about. Now the de nition of combinatorial can be stated.

3.2 De nition A map f : R ! S of trees is combinatorial provided that

i) f 1 (ES ) = ER, ii) Each terminal edge of R is a subedge of R iii) Each point of R lies in a subedge of R iv) No edge of R contains two subedges which map to the same edge of S .

So, among other things, if f : R ! S is a combinatorial map, then as t traverses an edge of R, f (t) cannot re-enter an edge of S once it has left it. In Figure 1, we describe a combinatorial map from the H to the Y which is simplicial. Points named xi in the domain are mapped to the points named x in range, and the result is extended linearly on each of the subarcs. (Superimposed on this simplicial diagram are some numbers, which we describe shortly.) Combinatorial maps have three additional properties of importance. 5

Figure 2: The edge-subedge diagram for the map in Figure 1.

1 2 3 1

f
3

@@ @@ 1 @@

@ @
3

3.3 Lemma Suppose f : R ! S is a combinatorial map of trees. Then

v) f is a surjection to S . vi) There are only nitely many subedges of R. vii) If p is a branchpoint of R of order n, then f (p) is a branchpoint of S of order at least n.

established. Let ab be an edge of S . By 3.2 iv) there are no more subedges of R mapping into ab than there are edges of R. Hence there are only nitely many subedges mapping into ab. Since there are only nitely many edges in S , vi) is established. Using iii) and vi), we see that each edge of R is the union of nitely many subedges of R and hence there are n subedges of R with p as an endpoint. Using iii) and the de nition of subedge, no two of these subedges can map to the same edge of S . This establishes vii). 2 It turns out to be convenient to describe a combinatorial map by means of its edge-subedge diagram. To construct the edge-subedge diagram for a combinatorial map f : R ! S , rst label all of the edges of S , 1,2, , n. Then label each subedge of R with the label of the edge of S to which it is mapped by f . Figure 1 shows the construction of the edge-subedge diagram superimposed on the simplicial diagram. Several properties of this labeling are evident from the properties of a combinatorial map. (i) No two subedges in the same edge of R have the same label. (ii) All the subedges around a branchpoint of R have distinct labels. (iii) Adjacent subedges of R have labels belonging to adjacent edges of S . (iv) Each terminal subedge of R has only one label written on it, that label belongs to a terminal subedge of S , and each label belonging to a terminal edge of S is written on at least one terminal edge of R. In Figure 2, we have removed all but the labels from the picture, leaving the edge-subedge diagram of f . Working from the labeling given in Figure 2, we can construct a combinatorial map which has Figure 2 as its edge-subedge diagram, by de ning the map piecewise on each subedge and gluing the resulting maps together. For example, the map f in Figure 2 maps each of the terminal edges of 6

Proof. Let x 2 S . Then there are endpoints p; q 2 S such that x 2 pq. By 3.2 i) there are endpoints p0 and q 0 in R which map to p; q respectively. Note that x 2 pq f (p0q 0 ) and so v) is

Edge-subedge diagrams.

Figure 3: Combinatorial but not universal

1 2 3

a a
(2) 3

2 1 3

(1)

@@ @@ 1 @@

@ @
3

the H homeomorphically onto its corresponding terminal edge in Y, taking the branchpoint to the branchpoint. Then the leftmost subedge on the horizontal edge of the H is folded into the 1-edge of the Y with both endpoints going to the branchpoint, being certain not to let the endpoint of the 1-edge be covered in the process. Similarly, the remaining subedge is folded into the 2-edge of the Y. Each of the remaining gures in this paper gives an edge-subedge diagram of some map. Such diagrams do not completely determine the map, but rather an equivalence class of maps. Edge-subedge diagrams which are diagrams of a combinatorial map from R to S can be constructed in advance. To do this, rst label the edges of S by 1,2, etc., and then list sequences of these labels along each edge of R in such a way that the labeling conditions (i)-(iv) given above are satis ed. When this is done, an equivalence class of combinatorial maps is determined. For example, the edge-subedge diagram given in Figure 3 describes a combinatorial map f from the H to the Y which is not universal. Included in the diagram are some labels in parentheses which describe how to construct a map g : H ! Y which misses f . The range of g is the arc in S connecting the endpoint of leg 2 with the endpoint of leg 1. Thus g sends everything to the left of (2) in H to the endpoint of the 2 leg in Y, and g sends everything to the right of (1) in H to the endpoint of the 1 leg in Y. On the arc connecting (2) and (1) in H , g is a homeomorphism to the arc connecting the endpoints of the 2 and 1 legs in S . One needs to choose the points (1) and (2) so that for t 2 (2)(1), f (t) lies in the 3 leg of Y with the vertex removed. A g constructed like this will miss f .

4 Light minimal universal maps are combinatorial.

The goal of this section is to prove Theorem 4.9. We rst prove two lemmas.

4.1 Lemma Let f : R ! S be a universal map of trees. Suppose R is the union of two branches B and B whose intersection is a single point p. If for each i = 1; 2, gi : Bi ! S is a map which misses f jBi , then f (p) lies in the arc from g (p) to g (p). Proof: Suppose that f (p) 62 g (p)g (p). Then we can choose a continuum K containing p in its interior so small that f (K ) \ (g (B \ K ) g (p)g (p) g (B \ K )) = ;. Let S 0 = g (B \ K ) g (p)g (p) g (B \ K ). Since S 0 is a subtree of S , by the Tietze Extension Theorem, there is a map h : K ! S 0 which agrees with gi on the boundary of K in Bi , for i = 1; 2. Note that
1 2 1 2 1 2 1 1 1 2 2 2 1 1 1 2 2 2

h misses f jK . But then the map g de ned to be the join of h with g1j(B1 n K ) and g2j(B2 n K ) misses f , contradicting the universality of f . 2.

4.2 Lemma Let f : R ! S be a minimal universal map of trees. Suppose that xy is an arc contained in some nonterminal edge of R. De ne R1 = Cy (x) and R2 = Cx (y ). For i = 1; 2, let gi : Ri ! S be a map so that gi misses f jRi and gi is endpoint valued at x and y . Then (i) f (xy ) g1(x)g2(y ) (in particular, f (xy ) is an arc or a point), and (ii) either f (xy ) lies in an edge of S or g1(x) < f (x) f (y ) < g2 (y ) in that order on g1(x)g2(y ). Proof: First, note that, by 4.1, for each t 2 xy, f (t) 2 g1(t)g2(t)), hence f (t) is not an endpoint of S . Thus f (xy ) contains no endpoint of S . We make use of this in the proofs of both parts of the lemma. If (i) fails, then there exist r; s 2 xy , with x < r < s < y such that f (rs) \ g1(x)g2(y ) = ;. De ne a map h : xy ! g1(x)g2(y ) by h(xr) = fg1(x)g, h(sy ) = fg2(y )g, and h maps rs homeomorphically onto g1(x)g2(y ) with h(r) = g1(x), h(s) = g2 (y ). We claim that h misses f on xy . To see this, we have by construction that f (rs) \ g1 (x)g2(y ) = ;. So h misses f on rs. But also f (xy ) \ fg1(x); g2(y )g = ;, since f (xy) contains no endpoint of S (from the note at the beginning of the proof), and g1(x), g2 (y ) are endpoints of S . So h misses f on xr and sy . This establishes the claim. 0 to be g1 restricted to (R1 n xy ) fxg and g 0 to be g2 restricted to (R2 n xy ) fy g. De ne g1 2 0 , h, and g 0 . Then g misses f , a contradiction. This Then de ne g : R ! S to be the join of g1 2 proves (i). To prove (ii), assume f (xy ) does not lie in an edge of S . By part (i), f (xy ) is an arc ab contained in g1 (x)g2(y ), ordered so that g1(x) < a < b < g2(y ). Then there is a branchpoint c of S lying in the interior of ab and an endpoint e of S such that ec \ ab = fcg. Assume that (ii) fails. We will construct a map on R which misses f . Since (ii) fails, then f (y ) < f (x) on the arc g1(x)g2(y ), and hence g1(x) < a f (y ) < f (x) b < g2(y ). To de ne the map, we rst choose points x0 ,x00, y 0 , and y 00 in xy so that x x0 < x00 < y 00 < 0 y y , and f (x0 x00) (cb n fcg), f (y 0y 00) (ac n fcg). There are three cases to consider: (1) If f (y ) < c < f (x), choose x0 = x, y 0 = y , and x00, y 00 so close to x0 and y 0 respectively that f (x0x00 ) cb n fcg and f (y0y00) ca n fcg. (2) If c f (y ) < f (x), choose x0 = x and x00 as above. Then, since c lies in the interior of f (xy ), we can choose y 00 and y 0 so that x00 < y 00 < y 0 < y and f (y 00y 0 ) ca n fcg. (3) If f (y ) < f (x) c, choose y 0 = y and y 00 as in case 1 and choose x0 and x00 as in case 2. Now de ne a map (see Figure 4) h : xy ! g1(x)g2(y ) ec as follows: h is constant on the three subintervals xx0 , x00y 00, and y 0y , namely h(xx0) = fg1(x)g, h(x00y 00) = feg, and h(y 0y ) = fg2(y )g. Note that h misses f on these subintervals since h is endpoint valued there and f never assumes an endpoint value there (use the note at the beginning of proof). De ne h on x0 x00 so that it maps x0 x00 homeomorphically onto g1(x)c ce (taking x0 to g1 (x) and x00 to e) and y 00 y 0 homeomorphically onto ec cg2(y ) (taking y 00 to e and y 0 to g2(y ). By the way x0x00 and y 0 y 00 were chosen, f and h never coincide on these arcs. Hence the map g on R which is the join of g1jR1 n xy , g2 jR2 n xy , and h misses f , a contradiction to the universality of f . This completes the proof of (ii). 2
The proof of Theorem 4.9 is broken into several propositions. In each of 4.3, 4.4, 4.5, 4.6, 4.7, and 4.8, f : R ! S is assumed to be a light minimal universal map of trees.

4.3 Proposition If p 2 R, then ordR(p) ordS (f (p)).

8

Figure 4: Diagram for Lemma 4.2

y y0 y 00 x00 x0 x a b f

g2 (y )

(((( ( ( ( ( ( ( ((
f (y0 y 00)

f (x0 x00)

g1 (x)

Proof. Let n = ordR(p) and m = ordS (f (p)). We can assume n > 1. Let A1; ; An denote the closures of the components of R n fpg, and let Ri be the closure of the complement of Ai . Also let D1; ; Dm denote the closure of the components of S n ff (p)g. Since f is minimal universal there are, by Lemma 2.2, maps gi : Ri ! S , i = 1; ; n, such that gi misses f jRi and gi (p) 2 ES . Suppose for the moment that m < n. Then for some i; j; k with i 6= j it must be that gi (p), gj (p) 2 Dk and so f (p) 62 gi(p)gj (p). However, we can apply Lemma 4.1 with B1 = Ri, B2 = Ai , g1 = gi, and g2 = gj jAi to conclude that f (p) 2 gi (p)gj (p). This contradiction shows that m n. 2
of R. Hence each nondegenerate component of f (ab) is a subedge of R.
1 1

4.4 Proposition If ab is an edge of S , then each component of f (ab) is contained in some edge
1

that xp and py are arcs, lying in di erent edges of R. Also since p is a branchpoint of R, we can choose z 2 R so that the arc pz meets the arc xy only in the point p. Let R1, R2 and R3 denote the closure of the complement of Cp(x), Cp(y ), and Cp (z ), respectively. Since f is minimal universal, there are maps gi : Ri ! S , i = 1; 2; 3, which miss fjRi , and are endpoint valued at p. At least two of the endpoints gi (p) must lie in one of the trees Ca (b) and Cb(a). Without loss of generality, assume that that g1(p) and g2 (p) both lie in Ca (b). Hence, g1(p)g2(p) \ ab fbg. Now f (p) is a branchpoint of S in ab, so f (p) = a or f (p) = b. By Lemma 4.1, f (p) 2 g1(p)g2(p) and so f (p) = b. Now by the continuity of g2 and the lightness of f , we can choose t 2 xp so close to p that g2(t)g1 (p) \ ab fbg and f (t) 6= b. Thus f (t) is not in the arc g1(p)g2(t). But we can extend the domain of g1 to include tp by de ning g1 (tp) = fg1(p)g. However, now f (t) 62 g1(t)g2(t) and this contradicts Lemma 4.1. 2

Proof. Suppose not. Then there is an arc xy in f (ab) and a branchpoint p of R in xy such

R, then f (eb) is a terminal edge of S , In fact, each terminal edge of R is a subedge of R.

1

4.5 Proposition f (ES ) = ER. Furthermore, if e 2 ER and b 2 BR with eb a terminal edge of

1

Proof. That f (ES ) ER follows immediately from Proposition 4.3. Conversely, suppose e 2 ER but f (e) 62 ES . Then choose t 2 eb n feg so close to e that f (et) \ ES = ;. Since f is minimal universal there is a map g 0 : Ct (b) ! S such that g 0 misses f jCt (b) and g 0(t) 2 ES . Now
9

the map g : R = Ct (b) et ! S given by g (x) = g 0(x) if x 2 Ct (b) and g (x) = g 0(t) if x 2 et clearly misses f , a contradiction. Hence ER f 1 (ES ). Now suppose that eb is a terminal edge of R. Then f (e) is an endpoint of S . Label b0 2 BS so that f (e)b0 is a terminal edge of S . If f (eb) 6 f (e)b0, then we can choose t 2 eb, with t 6= b, such that f (t) 62 f (e)b0. Since f is minimal universal there is, by Lemma 2.2, a map g1 : Ct (b) ! S such that g1 misses f jCt(b) and g1 (t) 2 ES . We have already proved that f 1 (ES ) is a subset of ER. It follows that f (te) \ ES = ff (e)g. We claim that g1(t) = f (e). If not, then g1(t) 62 f (te) and we can extend g1 to all of R by de ning g1(et) = fg1(t)g. This extension misses f , contradicting the universality of f , and establishing the claim. Choose d 2 ES such that d 6= f (e) and f (t) 62 dg1(t). De ne g2 : et ! S to be the constant map with value d. Since f (et) \ ES = ff (e)g and d 6= f (e), g2 misses f jet . But now 4.1 is contradicted (take p = t, B1 = Ct(b), B2 = et). Hence f (eb) f (e)b0. By 4.3, f (b) 2 BS , and so f (b) = b0. It follows that f (eb) = f (e)b0 is a terminal edge of S . That eb is in fact a subedge of R now follows from Proposition 4.4: the component of f 1 (f (e)b0) containing eb is contained in an edge and hence is eb. 2.

x2, and x3 in pq so that p < x1 < x2 < x3 < q , and f (x1) and f (x3 ) both lie in the interior of ab, and f (x2) lies in the interior of some edge of S sharing an endpoint with ab, which we will assume without loss of generality to be b. Let T1 = Cx3 (x1 ) and T2 = Cx1 (x3). Since f is minimal universal, there are maps gi : Ti ! S which miss f jTi and are endpoint-valued at x1 , x2 and x3. We will apply Lemma 4.2 successively to the arcs x1 x2, x1 x3 , and x2 x3 . We can do this because pq is not a terminal edge (by 4.5, since its image is not an edge). Apply Lemma 4.2, with xy = x1 x2 . By (i), f (x1 x2) g1 (x1)g2(x2), and by (ii), g1(x1) < a < f (x1 ) < b < f (x2) < g2(x2) in the natural order on g1(x1 )g2(x2). Again by Lemma 4.2(i), f (x1x3 ) g1(x1 )g2(x3). So f (x1 ) is in the arc g1(x1 )g2(x3), and it follows that, for i = 1; 3, g1 (x1) < a < f (xi) < b < f (x2) < g2 (x3) in the natural order on g1(x1 )g2(x3). Thus b 62 f (x2)g2 (x3). But now, by Lemma 4.2(i), f (x2 x3 ) g1 (x2)g2(x3 ) and by Lemma 4.2(ii), g1(x2 ) < f (x2) f (x3 ) < g2(x3) in the natural order on g1(x2 )g2(x3). Since b lies between f (x2) and f (x3 ), we get f (x2 ) < b < f (x3 ) < g2(x3 ). Thus b 2 f (x2)g2(x3 ) which contradicts the end of the preceding paragraph. This completes the proof. 2 4.7 Corollary The set of subedges of R is nite. Proof. By 4.6 there are no more subedges of R mapping to a particular edge of S than there are edges in R. Since both R and S have only nitely many edges, it follows that there are only nitely many subedges of R. 2 4.8 Proposition Each point of R lies in a subedge of R. Proof. Let R0 be the union of the nondegenerate components of the sets f 1(ab), as ab runs over the edges of S . Then by 4.4 and 4.7, there are only nitely many such components and so R0 is closed. If R R0 is nonempty, then there is a nondegenerate arc A in R R0 Since f is light, the image f (A) is nondegenerate, and hence A contains a nondegenerate subarc B such that f (B ) lies in an edge of S . This is a contradiction, and so R R0 is empty. 2
Now we can prove that light minimal universal maps are combinatorial. 10

4.6 Proposition No edge of R contains two subedges which map to the same edge in S . Proof. Suppose not. Then there is an edge ab of S , an edge pq of R and three points x ,
1

in 4.8. Property iv) is established in 4.6. 2

4.9 Theorem If f : R ! S is a light minimal universal map of trees, then f is combinatorial. Proof. Properties i) and ii) of De nition 3.2 are established by 4.5. Property iii) is established

5 Further properties of light minimal universal maps.

We have already seen that light minimal universal maps are combinatorial. In this section, we derive three additional properties of minimal universal maps (Theorems 5.3, 5.7, and 5.8). In the next section, these additional properties are used to characterize universal maps on trees.

5.1 De nition Let f : R ! S be a combinatorial map of trees. A subedge ab of R is called a folded subedge if f (a) = f (b). We say that the folded subedges of R are paired if each edge
The answer to the question of determining which combinatorial maps on R are universal hinges on the distribution of the folded subedges of R. The following lemma is a stronger version of Lemma 2.2 which we use repeatedly in establishing properties of the folded subedges of R.

of R which contains a folded subedge contains exactly two folded subedges, each of which contains an endpoint of the edge.

subset of R. Let b be a branchpoint of R, let a be a point in a subedge of R containing b with f (a) 6= f (b) and let e be a point of ES n Cf (b)(f (a)). Then there is a map g : Cb (a) ! S such that g is endpoint valued on F \ Cb (a), g misses f jCb(a), and g (b) = e.

5.2 Lemma Suppose that f : R ! S is a light minimal universal map of trees, and F is a nite

Proof: Suppose that ordR(b) = n. Let s1; ; sn be the vertices of R adjacent to b. Since b is a branchpoint, n > 2. Without loss of generality, we may assume that a 2 Cb (s1 ). For i = 2; 3, let Pi = R n Cb (si ). Then Pi is a proper subcontinuum of R containing Cb (a). So, by 2.2, there is a map gi : Pi ! S which is endpoint valued on fa; bg (F \ Pi ) and misses f jPi . By 4.1, f (b) 2 g2(b)g3(b), so one of g2 (b) and g3(b) is not in Cf (b)(f (a)). Without loss of generality we can assume that g2(b) 62 Cf (b)(f (a)). Choose x 2 ba with f (x) 6= f (b) so close to b that g2(xb) \ Cf (b)(f (a)) = ;. Now choose y 2 bx n fxg so that f (xy ) Cf (b)(f (a)) n ff (b)g. Note that f (xy ) \ g2 (x)e = ;. Then let m : xb ! g2(x)e be any map with m(x) = g2(x) and m(yb) = feg. By construction, m misses f jbx . So de ning g to be the join of m with g2jCx (a) establishes the lemma. 2
f are paired.

5.3 Theorem If f : R ! S is a light minimal universal map of trees, then the folded subedges of

The proof of this theorem is contained in the next three propositions. In each one, f : R ! S is assumed to be a light minimal universal map of trees.

f (pq ) cd, f (p) = f (q ) = c. Now pq is not a terminal edge. For suppose it is. Then one of p and q is an endpoint of R and hence c is an endpoint of S by Theorem 4.9. But then both p and q are endpoints of R by 4.9, and so R = pq . But then S = cd and some non endpoint of pq must go to d under f . This contradicts 4.9, and so pq is not terminal.
11

5.4 Proposition No edge which is a subedge is folded. Proof. Suppose to the contrary, that there are edges pq and cd of R and S respectively so that

So Cp(q ) and Cq (p) are proper subcontinua of R, and there are maps g1 : Cp(q ) ! S and g2 : Cq (p) ! S which miss f on their domain. We can assume that g1 and g2 are endpoint valued at p, q , and at a point t in pq chosen so that f (pq ) = f (p)f (t). Now the arc g1(p)g2(p) must contain c = f (p) by 4.1. In fact, it must contain cd, for if not then g1(p)g2(p) \ cd = fcg and by choosing x 2 pq close to p so that f (x) 62 g1(p)g2(p) and g1(x)g2(x) g1(p)g2(p) we see that 4.1 is violated. In the same way g1 (q )g2(q ) contains cd. Also the arcs g1 (p)g1(q ) and g2(p)g2(q ) must each intersect cd at most in c or in d, by 1.2. Now one of two cases must occur: If g1 (p) < c < d g2(p), then apply 5.2 with b = q , a = t, and e = g1(q ) to obtain a map g : Cq (t) ! S which misses f on Cq (t) and has the value g (q ) = g1(q ). Now the map h which is the join of g and g1 restricted to Cp(q ) n pq misses f and a contradiction is obtained. If g2 (p) < c < d g1(p), then apply 5.2 with b = p, a = t, and e = g2 (p) to obtain a map g : Cp(t) ! S which misses f on Cp (t) and has the value g (p) = g2(p). Now the map h which is the join of g and g2 restricted to Cq (p) n pq misses f and a contradiction is obtained. Since each case leads to a contradiction, our initial supposition is false and the theorem is established. 2

theorem fails, there are three subedges rs, st, and tu lying in an edge pq of R, with f (s) = f (t) = a and f (st) contained in an edge ab of S . Since f is combinatorial, f (ru) is a triod with vertex a. This contradicts 4.2, which says that f (ru) is an arc. 2 Note that 5.5 says that no edge in R contains more than two folded subedges. In fact,

5.5 Proposition Each folded subedge contains exactly one endpoint of the edge in which it lies. Proof. By 5.4, no folded subedge contains both endpoints of the edge in which it lies, so if the

of a combinatorial map contains two subedges mapping to the same edge). So our claim that f (p) 6= f (q ) is established. So k(q ) 2 ES n Cf (q)(f (p)). Now apply 5.2 with b = q , a = s and e = k(q ) to obtain a map g2 : Cq(p) ! S such that g2(q ) = k(q ) and g2 misses f on Cq (p). But now the map g which is the join of g2 and k restricted to Cp(q ) n pq misses f on R, a contradiction to the assumption that f is universal. This establishes the theorem. 2 Now Theorem 5.3 follows from 5.5 and 5.6.

of pq containing q . Then f (sq ) is an edge of S with endpoints f (s) = b and f (q ) = a. Since f is combinatorial, pq is not a terminal edge and Cp(q ), Cq(p) are proper subsets of R. Since f is minimal universal there are maps g1 : Cq (p) ! S and k : Cp (q ) ! S which miss f on their respective domains and are endpoint valued at q . By 4.2, parts (i) and (ii), we have f (pq ) g1(p)k(q ) and g1(p) < f (p) f (q ) < k(q ). We claim that f (p) = 6 f (q). For suppose f (p) = f (q). Then f (q) = f (r) and since sq is not folded f (s) = 6 f (q). Hence f (s) = 6 f (r). But f (rs) f (r)f (s) and f (r)f (s) = f (q)f (s) and f (q)f (s) is an edge of S . So rs contains a subedge mapping to f (q )f (s). This contradicts 4.9 (no edge

5.6 Proposition Each edge of R contains none or two folded subedges. Proof. If not, there is an edge pq of R containing exactly one folded subedge pr, and an edge cd of S such that f (p) = f (r) = c and f (pr) cd. By 5.5, r = 6 q. Let sq be the subedge

5.7 Theorem If f : R ! S is a light minimal universal map of trees, then each edge of R which is not a subedge contains a folded subedge.
12

subedge. Label the endpoints of the subedges of pq in order from p to q , p = x0 < x1 < < xn = q . Since pq is not a subedge, n > 1. Now f (pq ) is an arc by 4.2, (i). We claim that f (pq ) = f (p)f (q ) and that in the order from f (p) to f (q ), f (xi ) < f (xi+1 ) for i = 0; ; n 1. Since pq contains no folded subedge, f (xi xi+1 ) = f (xi )f (xi+1), for i = 0; ; n 1. Also, since f is combinatorial, no two subedges of pq map into to the same edge of S , and so f (pxi ) \ f (xi q ) = ff (xi)g for i = 1; ; n 1. Thus f (xi ) is between f (xj ) and f (xk ) for 0 j < i < k n in the arc f (pq ) for i = 1; ; n 1. Hence

Proof. Suppose not. Let pq be an edge of R which is not a subedge but contains no folded

f (p) = f (x0) < f (x1 ) < : : : < f (xn) = f (q );

and this establishes the claim. By 4.5, pq is not a terminal edge of R, so Cp(q ) and Cq (p) are proper subcontinua of R. Choose an endpoint e 62 Cf (q)(f (p)) and apply 5.2 with b = q and a = xn 1 to obtain a map g1 : Cq (p) ! S which is endpoint valued at p, misses f jCq (p), and g1 (q ) = e. Let g2 : Cp (q ) ! S be any map which is endpoint valued on fp; q g and misses f jCp(q ). By 4.2 (ii), we have the inequality g1(p) < f (p) < f (q ) < g2 (q ). But, since g1(q ) = e 62 Cf (q)(f (p)), we have the inequality g1(p) < f (p) < f (q ) < g1 (q ). Using the inequality established above, we have

g1(x0) < f (x0) < f (x1 ) <

< f (xn) < g1 (xn )

So g1 (x0) 2 Cf (x1) (f (x0)). Then, by 1.2, g1(x1 ) 2 Cf (x2) (f (x1)). Continue to apply 1.2 to obtain g1(xi ) 2 Cf (xi+1) (f (xi )) until i = n 1. But we have g1(xn ) 2 Cf (xn 1) (f (xn )), and so g1 stretches xn 1 xn over its f -image, a violation of 1.2. A contradiction has been reached and the theorem must hold. 2

5.8 Theorem If f : R ! S is a light minimal universal map of trees and p is a branchpoint of order n in R, then f (p) is a branchpoint of order n in S . Proof. By 3.3, the order of f (p) n. Label the subedges which contain p, psi, i = 1; ; n. In each of these subedges choose a point xi so that f (p) 6= f (xi ). If the theorem is false, then there is an endpoint e of S such that f (pxi ) \ f (p)e = ff (p)g for all i = 1; ; n. Note that e 62 Cf (p)(f (xi )) for each i. Hence by Lemma 5.2, there are maps gi : Cp(xi ) ! S missing f such that gi (p) = e. The join of the maps gi misses f . This contradicts the universality of f and so the theorem is proved.
2
Combining Theorems 4.9, 5.3, 5.7, and 5.8, we have the following result.
and (i) the folded subedges of R are paired, (ii) each edge of R which is not a subedge contains a folded subedge, and (iii) if p is a branchpoint of order n in R, then f (p) has order n in S .

5.9 Theorem Let f : R ! S be a light minimal universal map of trees. Then f is combinatorial

6 The characterization.
The characterization is given in Theorem 6.3. We begin by showing that the three conditions of Theorem 5.9 are su cient to establish that a combinatorial map of trees is universal. Note that f is not assumed to be a light mapping in this theorem. 13

6.1 Theorem Let f : R ! S be a combinatorial map of trees such that

(i) the folded subedges of R are paired, (ii) each edge which is not a subedge contains a folded subedge, (iii) if p is a branchpoint of order n in R, then f (p) has order n in S . Then f is universal.

In each folded subedge pr of R, with branchpoint p, let x be the rst point of pr (in the order from p to r) such that f (px) = f (p)f (x) = f (pr) = f (xr) = f (x)f (r). We will call the arc px a half folded subedge. Let E be the ( nite) set consisting of all the nonfolded subedges of R together with all the half folded subedges formed above. Let F be the set of endpoints of the arcs in E , together with the endpoints of the subedges of R. Now let g : R ! S be a map which misses f and is endpoint valued on the set F . Denote by C the set of all branches Cb(r), where b is a branchpoint of R, br 2 E , and g (b) 2 Cf (b)(f (r)). First we show that C is not empty. To see this, let b be any branch point of R. Since f is combinatorial and iii) holds, there is a br 2 E such that f (br) is a subset of f (b)g (b). Thus g (b) 2 Cf (b)(f (r)), and so Cb (r) 2 C . So C is not empty. Now we show that C is empty. To see this, note rst that C is nite and hence it contains an element Cb (r) which is minimal in the sense that if b0r0 2 E with Cb0 (r0) properly contained in Cb (r), then g (b0) 62 Cf (b0 )(f (r0)). Let ba be the edge containing br, and let n = ordR(a). There are points si , i = 1; ; n, so that asi 2 E and s1 2 ba. There are two cases to consider. Case 1. ba contains no folded subedge. In this case, by ii), ba is a subedge of R, s1 = b, and r = a. So f (ba) = f (b)f (a) is an edge of S . Since g (b) 2 Cf (b)(f (a)), it follows from 1.2 that g (a) 2 Cf (b)(f (a)). Also g (a) is an endpoint of S . Hence ba is not a terminal edge. (Otherwise, f (ba) is terminal since f is combinatorial, and so f (a) = g (a), a contradiction.) Now if g (a) 2 Cf (a)(f (b)), then g (a) 2 f (a)f (b), but g (a) is an endpoint of S and f (a)f (b) contains no endpoints of S . So g (a) 62 Cf (a)(f (b)). Hence by iii), g (a) 2 Cf (a)(f (si )) for some i = 2; ; n. But Ca (si ) is a proper subset of Cb(a) = Cb(r), contradicting the minimality of Cb (r). So Case 1 cannot occur. Case 2. ba contains a folded subedge. By i), br and s1 a are half-folded subedges and so there is at least one point of F between r and s1 in ba. Label all these points x1 ; ; xm in order on ba so that b < r < x1 xm < s1 < a with bx1 and xma subedges, and for i = 1 (m 1), xi xi+1 2 E . Now g (b) 2 Cf (b)(f (r)), so by 1.2, g (r) 2 Cf (b)(f (r)). Also, for i > 1, Ca(si ) is a proper subset of Cb (r), so by the minimality of Cb(r), we know g (a) 62 Cf (a)(f (si)) for i > 1. Hence g (a) 2 Cf (a)(f (s1)). It follows from 1.2 that ()

Proof. Suppose f is not universal. Then de ne sets E and F as follows.

g (s1) 2 Cf (a)(f (s1 )):

Now since g (r) 2 Cf (b)(f (r)) and f (x1 ) = f (b), we have by 1.2 that g (x1) 2 Cf (x1) (f (r)) = Cf (b)(f (r)). But Cf (x1)(f (r)) Cf (s1) (f (x1)), so ( ) g (x1) 2 Cf (s1 ) (f (x1)): If m = 1 then f (a) = f (x1). From (*) above, we have g (s1) 2 Cf (a)(f (s1)) = Cf (x1)(f (s1 )). This and (**) above contradict 1.2. If m > 1, then Cf (x1) (f (r)) Cf (x2)(f (x1 )), and so g (x1) 2 Cf (x2) (f (x1)) and it follows from 1.2 that g (x2) 2 Cf (x2) (f (x1)). We can repeat this argument until we get that g (xm) 2 14

#
3 4 7 5 8

Figure 5: f satis es all but property ii).

#
3 4 7 5 8 9

Figure 6: f satis es all but property iii).

a a" !
1 3 6 2 (1) (4) 7 8 9

3 6

2 5 8

f
(g)

4 7

Cf (xm) (f (xm 1 )). But Cf (xm)(f (xm 1 )) Cf (s1 )(f (xm)) so g (xm) 2 Cf (s1)(f (xm)). Also g (s1) 2 Cf (a)(f (s1 )) = Cf (xm)(f (s1)). But now g stretches xms1 over its f -image, a contradiction of 1.2. So f is universal. 2

a a" !
1 3 6 2 (1) 5 8 (4) 7 9

3 6

2 5 8

f
(g)

4 7

6.2 Theorem. The three properties given above in 6.1 which a combinatorial map must have in order to be universal are independent of each other. Proof: To see this, we note rst that the non-universal but combinatorial map given in Figure 3 satis es properties ii) and iii) but not i). An edge-subedge diagram for a non-universal map f satisfying i) and iii) but not ii) is given in Figure 5. Included in the diagram are instructions (in parentheses) for constructing a map g which misses f . (See the text near Figure 3 for details on constructing g .) Finally, a map f satisfying i) and ii) but not iii) is described in Figure 6. 2 Combining the results of sections 3, 4, and 5, we have the following characterization of universal maps on trees. 6.3 Theorem Let f : R ! S be a map of trees, with monotone light factorization f = lm. Then f is universal if and only if there is a subtree R0 of R such that ljm(R0) : m(R0 ) ! S is a combinatorial map satisfying the following: (i) The folded subedges of m(R0 ) are paired. (ii) Each edge of m(R0) which is not a subedge contains a folded subedge. (iii) If p is a branchpoint of order n in m(R0), then l(p) has order n in S .
15

To conclude, we show that the class of universal maps on trees is larger than the class of u-maps de ned by Marsh in 6]. Brie y, a u-map is a map of trees with ve properties, one of which is the requirement that if b is a branchpoint then f takes the star of b (i.e. the union of the edges containing b) into the star of f (b). Marsh shows that u-maps are universal. The example given in Figure 7 is a universal map that is not a u-map, because it does not satisfy the above mentioned property.

#
3 5 8 9

Figure 7: f is universal but is not a u-map. 1 4 3 6 2 5 8 1 3 6 7 9 8 2 5

4 7

"!
7 9

16

References
1] C. A. Eberhart, J. B. Fugate, and G. R. Gordh, Branchpoint Covering Theorems for Con uent and Weakly Con uent Maps, Proc. A.M.S, 55 (1976), 409-415. 2] W. Holsztynski, Universal Mappings and Fixed Point Theorems, Bull. Acad. Polon. Sci., XV(1967), 433-438. 3] W. Holsztynski, Universality of the product mappings onto products of I n and snake-like spaces, Fund. Math. 64 (1969), 147-155. 4] O.W. Lokuciewski, On a theorem on xed points, Yc . Mat. Hayk XII 3(75) 1957, 171-172. 5] M. M. Marsh, Fixed Point Theorems for Certain Tree-like Continua, Dissertation, University of Houston, (1981). 6] M. M. Marsh, u-mappings on Trees, Paci c Journal of Mathematics, Vol. 127, No. 2 (1987), 373-387. 7] S. B. Nadler, Jr., Universal Mappings and Weakly Con uent Mappings, Fund. Math, 110, (1980), 221-235. 8] G. T. Whyburn, Analytic Topology, A.M.S. Colloq. Pub. XXVIII, (1963).

17