# Topological Entropy and Specialα-Limit Points of Graph Maps

Authors: Taixiang Sun; Guangwang Su; Hailan Liang; Qiuli He
Journal: Discrete Dynamics in Nature and Society
 (2011)

---

## Abstract

LetG a graph and
f:G→G be a continuous map. Denote by
h(f), R(f), and SA(f) the topological entropy, the set of recurrent points, and the set of special
α-limit points of
f, respectively. In this paper, we show that h(f)>0 if and only if SA(f)-R(f)≠∅.


---

## Body

## 1. Introduction

Let(X,d) be a metric space. For any Y⊂X, denote by Y∘, ∂Y, and Y¯ the interior, the boundary, and the closure of Y in X, respectively. For any y∈X and any r>0, write B(y,r)={x∈X:d(x,y)<r}. Let ℕ be the set of all positive integers and ℤ+=ℕ∪{0}.Denote byC0(X) the set of all continuous maps from X to X. For any f∈C0(X), let f0 be the identity map of X and fn=f∘fn-1 the composition map of f and fn-1. A point x∈X is called a periodic point of f with period n if fn(x)=x and fi(x)≠x for 1≤i<n. The orbit of x under f is the set O(x,f)≡{fn(x):n∈ℤ+}. Write ω(x,f)=⋂i=1∞O(fi(x),f)¯, called the ω-limit set of x under f. In fact, y∈ω(x,f) if and only if there exists a sequence of positive integers n1<n2<n3<⋯ such that limi→∞fni(x)=y. x is called a recurrent point of f if x∈ω(x,f). x is called a special α-limit point of f if there exist a sequence of positive integers {ni}i=1∞ and a sequence of points {yi}i=0∞ such that fni(yi)=yi-1 for any i∈ℕ and limi→∞yi=x. Denote by P(f), R(f), and SA(f) the sets of periodic points, recurrent points, and special α-limit points of f, respectively. From the definitions it is easy to see that P(f)⊂SA(f) and P(f)⊂R(f). Let h(f) denote the topological entropy of f, for the definition see [1, Chapter VIII].A metric spaceX is called an arc (resp., an open arc, a circle ) if it is homeomorphic to the interval [0,1] (resp., the open interval (0,1), the unit circle S1). Let A be an arc and h:[0,1]→A a homeomorphism. The points h(0) and h(1) are called the endpoints of A, and we write End(A)={h(0),h(1)}. A compact connected metric space G is called a graph if there are finitely many arcs A1,…,An (n≥1) in G such that G=⋃i=1nAi and Ai∩Aj=End(Ai)∩End(Aj) for all 1≤i<j≤n. A graph T is called a tree if it contains no circle. A continuous map from a graph (resp., a tree, an interval) to itself is called a graph map (resp., a tree map, an interval map).LetG be a given graph. Take a metric d on G such that, for any x∈G and any r>0, the open ball B(x,r)≡{y∈G:d(y,x)<r} is always connected. For any finite set S, let |S| denote the number of elements of S. For any x∈G, write val(x)=limr→+0|∂B(x,r)|, which is called the valence of x. x is called a branching point (resp., an endpoint) of G if val(x)>2 (resp., val(x)=1). Denote by End(G) and Br(G) the sets of endpoints and branching points of G, respectively. Take a finite subset V(G) of G containing End(G)∪Br(G) such that, for any connected component E of G-V(G), the closure E¯ is an arc. Such a subset V(G) is called the set of vertexes of G, and the closure of every connected component of G-V(G) is called an edge. For any edge I of G and any a,b∈I, we denote by [a,b]I (or simply [a,b] if there is no confusion) the smallest connected closed subset of I containing {a,b}, which is called a closed interval of G. So, a closed interval is always a subset of an edge. Write (a,b]=[b,a)=[a,b]-{a} and (a,b)=(a,b]-{b}. Let G be a graph and J,K⊂G closed intervals, and f∈C0(G). We write f(J)ℶK if there exists a closed subinterval L⊂J such that f(L)=K.In the study of dynamical systems, recurrent points, topological entropy, and specialα-limit points play an important role. For interval maps, Hero [2] obtained the following result.Theorem A (see [2, Corollary]).
LetI be a compact interval and  f∈C0(I). Then the following are equivalent: (1)
some pointy that is not recurrent is a special α-limit point;(2)
some periodic point has period that is not a power of two.It is known [1, Chapter VIII, Proposition 34] that h(f)>0 if and only if some periodic point of f has period that is not a power of two for interval map f.In [3], Llibre and Misiurewicz studied the topological entropy of a graph map and obtained the following theorem.Theorem B (see [3, Theorems 1 and 2]).
LetG be a graph and  f∈C0(G). Then  h(f)>0 if and only if there exist  n∈ℕ and closed intervals  L,J,K⊂G with  J,K⊂L and  |K∩J|≤1 such that  fn(J)ℶL and  fn(K)ℶL.Recently, there has been a lot of work on the dynamics of graph maps (see [4–13]). In this paper, we will study the topological entropy and special α-limit points of graph maps. Our main result is the following theorem.Theorem 1.1.
LetG be a graph and  f∈C0(G). Then  h(f)>0 if and only if  SA(f)-R(f)≠∅.


## 2. Proof of Theorem1.1

In this section, we will prove Theorem1.1. To do this, we need the following lemmas.Lemma 2.1 (see [11, Theorem 1]).
LetG be a graph and  f∈C0(G). If  x∈SA(f), then there exist a sequence of positive integers  n1≤n2≤n3≤⋯ and a sequence of points  {yi}i=0∞ with  y0=x such that  fni(yi)=yi-1 for any  i∈ℕ and  limi→∞yi=x.Remark 2.2.
The main idea of the proof of Theorem 1 in [11] is similar to the one of Main Theorem in [2].Lemma 2.3.
LetG be a graph and  f∈C0(G). Then  SA(f)⊂f(SA(f)).Proof.
Letx∈SA(f). Then there exist a sequence of points {xi}i=0∞ and a sequence of positive integers 2≤m1≤m2≤⋯ such that fmi(xi)=xi-1 for every i∈ℕ and limi→∞xi=x. Write yi=fmi-1(xi) for i∈ℕ. Let yk0=y1,yk1,yk2,…,yki,… be a convergence subsequence of {yi}i=1∞, and let limi→∞yki=y. Then
(2.1)f(y)=lim⁡i→∞f(yki)=lim⁡i→∞fmki(xki)=lim⁡i→∞xki-1=x.
Write
(2.2)μi={mk1-1+⋯+m1,ifi=1,mki-1+mki-2+⋯+mki-1,ifi≥2.
Then fμi(yki)=fμi+mki-1(xki)=fmki-1-1(xki-1)=yki-1 for any i∈ℕ, which implies that y∈SA(f) and SA(f)⊂f(SA(f)). The proof is completed.Lemma 2.4 (see [3, Lemma 2.4]).
LetG be a graph and  f∈C0(G). Suppose that  J and  L=[a,b] are intervals of  G. If there exist  x∈(a,b) and  y∉(a,b) such that  {x,y}⊂f(J), then  f(J)ℶ[a,x] or  f(J)ℶ[x,b].Theorem 2.5.
LetG be a graph and  f∈C0(G). Then  h(f)>0 if and only if  SA(f)-R(f)≠∅.Proof Necessity
IfSA(f)-R(f)≠∅, then take a point w0∈SA(f)-R(f). By Lemma 2.3 and f(R(f))=R(f), for every i=1,2,…, there exists a point wi∈SA(f)-R(f) such that f(wi)=wi-1. Note that w0,w1,w2,… are mutually different. Since the numbers of vertexes and edges of G are finite, there exists an edge I of G such that I∩{w0,w1,w2,…} is an infinite set. We can choose integers 1<i1<i2<⋯ such that {wik:k∈ℕ}⊂I and wik∈(wi1,wik+1) for every k≥2. Take points {y,x,z}⊂I∘∩(SA(f)-R(f)) with x∈(y,z) such that fm(y)=x and fn(x)=z for some m,n∈ℕ. Without loss of generality we may assume that I=[0,1] and 0<y<x<z<1. Since y∈SA(f)-R(f), we can take points {yi:i∈ℕ}⊂(0,1) and positive integers m+n<m1<m2<m3<⋯ satisfying the following conditions:(1)
the sequence(y1,y2,y3,…) is strictly monotonic with fmi(yi)=yi-1 for any i∈ℕ and y0=y (see Lemma 2.1) and limi→∞yi=y;(2)
mi>m1+m2+⋯+mi-1 for any i≥2.
Letxi=fm(yi) and zi=fn(xi) for any i∈ℤ+. Then limi→∞xi=x and limi→∞zi=z. Noting that x,z∈SA(f)-R(f), we can assume that {xi,zi:i∈ℕ}⊂(0,1), and there exists ɛ>0 such that the following conditions hold:
(3)
fi(x)∉[x-ɛ,x+ɛ] for any i∈ℕ;(4)
the sequences(x1,x2,x3,…) and (z1,z2,z3,…) are strictly monotonic, and {xi:i∈ℕ}⊂[x-ɛ,x+ɛ]⊂(y,z).
In the following we may consider only the case that(x1,x2,x3,…) is strictly decreasing since the other case that (x1,x2,x3,…) is strictly increasing is similar.
Writeμi=mi+mi-1+⋯+m1 for any i∈ℕ. Put Ii=[xi,xi-1] and Ai=fμi-1(Ii) for any i≥2. Then Ai is a connected set, and(2.3){fμi-1(xi-1),fμi-1(xi)}={x,fμi-1(xi)}⊂Ai.
Noting that fmi(fμi-1(xi))=fμi(xi)=x, we have x∈fmi(Ai)∩Ai. Write Si=⋃j=0∞fjmi(Ai). Then Si is a connected set containing x and fmi(Si)⊂Si for every i≥2.
Sincefmi(xi-1)=fmi-μi-1(x) and fmi(xi)=xi-1 for any i≥2, by Lemma 2.4 it follows that fmi(Ii)ℶ[x-ɛ,xi-1] or fmi(Ii)ℶ[xi-1,x+ɛ]. There are two cases to consider.
Case 1.
There exist2≤α<β<λ such that fmi(Ii)ℶ[x-ɛ,xi-1] for every i∈{α,β,λ}.
Subcase 1.1.
There existsλ≤τ such that Sτ⊄(0,1). Then Sτ∩{yα,zα+1}≠∅, and there exist r≥μτ-1 and u∈Iτ such that fr(u)∈{yα,zα+1}, from which and mα+1>m+n it follows
(2.4)fm+r(u)=fm(yα)=xαorfmα+1-n+r(u)=fmα+1-n(zα+1)=xα.
Noting fm+r(xτ-1)=fm+r-μτ-1(x) and fmα+1-n+r(xτ-1)=fmα+1-n+r-μτ-1(x), we have
(2.5){fm+r-μτ-1(x),fmα+1-n+r-μτ-1(x)}∩[x-ɛ,x+ɛ]=∅.
There exists s∈{m+r,mα+1-n+r} such that fs(Iτ)ℶIβ∪Iλ or fs(Iτ)ℶIα, which implies
(2.6)fs+mλ(Iλ)ℶfs(Iτ)ℶIβ∪Iλorfs+mα+mλ(Iλ)ℶfs+mα(Iτ)ℶfmα(Iα)ℶIβ∪Iλ.
On the other hand, fmβ(Iβ)ℶIβ∪Iλ. Thus we can obtain fl(Iλ)ℶIβ∪Iλ and fl(Iβ)ℶIβ∪Iλ for some l∈{(s+mλ)mβ,(s+mα+mλ)mβ}. By Theorem B it follows that h(f)>0.
Subcase 1.2.
Si⊂(0,1) for all i≥λ, and there exists τ≥λ such that x<supSτ. Then we can take j≥τ such that [x,xj]⊂Sτ. Thus there exist r≥μτ-1 and u∈Iτ such that fr(u)=xj, which implies fr+mj+⋯+mα+1(u)=xα. Write s=r+mj+⋯+mα+1. Then fs(Iτ)ℶIβ∪Iλ or fs(Iτ)ℶIα since fs(xτ-1)=fs-μτ-1(x)∉[x-ɛ,x+ɛ], which implies
(2.7)fs+mλ(Iλ)ℶfs(Iτ)ℶIβ∪Iλorfs+mα+mλ(Iλ)ℶfs+mα(Iτ)ℶfmα(Iα)ℶIβ∪Iλ.
On the other hand, fmβ(Iβ)ℶIβ∪Iλ. Thus we can obtain fl(Iλ)ℶIβ∪Iλ and fl(Iβ)ℶIβ∪Iλ for some l∈{(s+mλ)mβ,(s+mα+mλ)mβ}. By Theorem B it follows that h(f)>0.
Subcase 1.3.
One hasSi⊂(0,1) and x=supSi for all i≥λ.
Iffmr(x)<f2mr(x)<x for some r≥λ, then there exist j≥r+2 and u∈Ir such that fμr(u)=f2mr(xj) since limi→∞f2mr(xi)=f2mr(x) and {fmr(x),x}⊂fμr(Ir), which implies fμr+mj+mj-1+⋯+mα+1-2mr(u)=xα. Using arguments similar to ones developed in the proof of Subcase 1.2, we can obtain fl(Iλ)ℶIβ∪Iλ and fl(Iβ)ℶIβ∪Iλ for some l∈ℕ. By Theorem B it follows that h(f)>0. Now we assume f2mr(x)≤fmr(x)<x for all r≥λ. Note fμr-1(xr)∉O(fmr,x) since x∉R(f).
Iff2mr(x)≤fmr(x)<fμr-1(xr)<x for some r≥λ, then fmr([fmr(x),fμr-1(xr)])ℶ[fmr(x),x] and fmr([fμr-1(xr),x])ℶ[fmr(x),x]. By Theorem B it follows that h(f)>0.
Iffμr-1(xr)<fmr(x) for some r≥λ, then there exist j≥r+2 and u∈Ir such that fμr-1(u)=fmr(xj) since limi→∞fmr(xi)=fmr(x) and {fμr-1(xr),x}⊂fμr-1(Ir), which implies fμr-1+mj+mj-1+⋯+mα+1-mr(u)=xα. Using arguments similar to ones developed in the proof of Subcase 1.2, we can obtain fl(Iλ)ℶIβ∪Iλ and fl(Iβ)ℶIβ∪Iλ for some l∈ℕ. By Theorem B it follows that h(f)>0.Case 2.
There existsκ≥2 such that fmi(Ii)ℶ[xi-1,x+ɛ] for all i≥κ.
Subcase 2.1.
There existκ≤α<β such that Si⊄(0,1) for every i∈{α,β}. Then Sβ∩{yβ,zβ+1}≠∅ and Sα∩{yβ,zβ+1}≠∅. Thus there exist r≥μβ-1 and u∈Iβ such that fr(u)∈{yβ,zβ+1}, from which it follows that fm+r(u)=xβ or fmβ+1-n+r(u)=xβ. Since fm+r(xβ-1)=fm+r-μβ-1(x), fmβ+1-n+r(xβ-1)=fmβ+1-n+r-μβ-1(x), and
(2.8){fm+r-μβ-1(x),fmβ+1-n+r-μβ-1(x)}∩[x-ɛ,x+ɛ]=∅,
there exists s∈{m+r,mβ+1-n+r} such that fs(Iβ)ℶIβ∪Iα or fs(Iβ)ℶIβ+1, which implies fs(Iβ)ℶIβ∪Iα or fs+mβ+1(Iβ)ℶfmβ+1(Iβ+1)ℶIβ∪Iα. In similar fashion, we can show ft(Iα)ℶIβ∪Iα for some t∈ℕ. Thus we get fl(Iβ)ℶIβ∪Iα and fl(Iα)ℶIβ∪Iα for some l∈{st,(s+mβ+1)t}. It follows from Theorem B that h(f)>0.
Subcase 2.2.
There existsϑ≥κ such that Si⊂(0,1) for all i≥ϑ and there exists τ≥λ≥ϑ such that x<supSτ and x<supSλ. Take j≥τ+2 such that Si⊃[x,xj] for i∈{λ,τ}. Then there exist r1≥μτ-1,r2≥μλ-1, and u∈Iτ,v∈Iλ such that fr1(u)=fr2(v)=xj. Using arguments similar to ones developed in the proof of Subcase 2.1, we can obtain fl(Iλ)ℶIτ∪Iλ and fl(Iτ)ℶIτ∪Iλ for some l∈ℕ. By Theorem B it follows that h(f)>0.
Subcase 2.3.
There existsϑ≥κ such that Si⊂(0,1) and x=supSi for all i≥ϑ.
If there existτ>λ≥ϑ such that fmi(x)<f2mi(x)<x for i∈{τ,λ}, then there exist j≥τ+2, u∈Iτ, and v∈Iλ such that fμτ(u)=f2mτ(xj) and fμλ(v)=f2mλ(xj), which implies fμτ+mj+mj-1+⋯+mτ+1-2mτ(u)=xτ and fμλ+mj+mj-1+⋯+mτ+1-2mλ(v)=xτ. Using arguments similar to ones developed in the proof of Subcase 2.1, we can obtain fl(Iλ)ℶIτ∪Iλ and fl(Iτ)ℶIτ∪Iλ for some l∈ℕ. By Theorem B it follows that h(f)>0. Now we assume that there exists θ≥ϑ such that f2mi(x)≤fmi(x)<x for all i≥θ.
Iffμi-1(xi)<fmi(x)<x for all i≥θ, then using arguments similar to ones developed in the above proof, we can obtain h(f)>0.
Iff2mr(x)≤fmr(x)<fμr-1(xr)<x for some r≥θ, then fmr([fmr(x),fμr-1(xr)])ℶ[fmr(x),x] and fmr([fμr-1(xr),x])ℶ[fmr(x),x]. By Theorem B it follows h(f)>0.Sufficiency
Ifh(f)>0, then it follows from Theorem B that there exist n∈ℕ and closed intervals L,J,K⊂G with J,K⊂L and |K∩J|≤1 such that fn(J)=L and fn(K)=L. Without loss of generality we may assume that L=[0,1] and J=[a,b] and K=[c,d] with 0≤a<b≤c<d≤1 such that fn([a,b])=[0,1] and fn([c,d])=[0,1]. By [1, Chapter II, Lemma 2] we can choose u,v,w∈[0,1] with u<v<w such that one of the following statements holds:(i)
fn(u)=fn(w)=u, fn(v)=w, fn(x)>u for u<x<w and x<fn(x)<w for u<x<v.(ii)
fn(u)=fn(w)=w, fn(v)=u, fn(x)<w for u<x<w and u<fn(x)<x for v<x<w.
We may consider only case (i) since case (ii) is similar. We claim that, for anyx∈(v,w) and any 0<ɛ<w-x, there exist y∈[w-ɛ,w) and s∈ℕ such that fsn(y)=x. In fact, we can choose u<⋯<xi<xi-1<⋯<x1≤v<x0=x such that limi→∞xi=u and fn(xi)=xi-1 for any i∈ℕ. Thus there exists some xN∈fn([w-ɛ,w)). That is, we can choose y∈[w-ɛ,w) satisfying fn(y)=xN, which implies f(N+1)n(y)=x. The claim is proven.
By the above claim we can choose a sequence of positive integers{si}i=1∞ and a sequence of points v<y0<y1<y2<⋯<w such that fnsi(yi)=yi-1 for any i∈ℕ and limi→∞yi=w. Note that fn(w)=fn(u)=u; then w∈SA(fn)-R(fn)⊂SA(f)-R(f). The proof is completed.



---

*Source: 132985-2011-05-11.xml*