| Topology Atlas Document # taic-41 | Topology Atlas Invited Contributions vol. 6 issue 1 (2001) 1-3 |
Department of Mathematical SciencesNote: Detailed treatment of Combinatorial Dynamics in dimension 1 (with an extensive bibliography and historical remarks) can be found in the book [1]. For dimension 2, see for instance [2-5].
Indiana University - Purdue University Indianapolis
402 N. Blackford Street
Indianapolis, IN 46202-3216
USA
mmisiure@math.iupui.edu
Combinatorial Dynamics has its roots in Sharkovsky's Theorem. This beautiful theorem describes the possible sets of periods of all cycles of a continuous map of an interval (or the real line) into itself. Here by a cycle I mean a periodic orbit, and by a period its minimal period.
Consider the following Sharkovsky's ordering <s of the set N of natural numbers:
| : | |||||
| ¼ | <s 11×2n | <s 9×2n | <s 7×2n | <s 5×2n | <s 3×2n |
| : | |||||
| ¼ | <s 11×22 | <s 9×22 | <s 7×22 | <s 5×22 | <s 3×22 |
| ¼ | <s 11×2 | <s 9×2 | <s 7×2 | <s 5×2 | <s 3×2 |
| ¼ | <s 11 | <s 9 | <s 7 | <s 5 | <s 3 |
Denote by S(n) the initial segment of this ordering ending at nÎN, that is S(n) = {mÎN : m <s n}È{n}. We also set S(2¥) = {1,2,22,23,24,¼}. For a map f : X®X we denote by P(f) the set of periods of all cycles of f.
Sharkovsky's Theorem: Let I be a closed interval. Then for every continuous map f : I®I there exists nÎNÈ{2¥} such that P(f) = S(n). Conversely, for every nÎNÈ{2¥} there exists a continuous map f : I®I such that P(f) = S(n).
The same holds for continuous maps of the real line into itself, except that we may have P(f) = Æ.
All proofs of Sharkovsky's Theorem inevitably lead to an idea of a "type" of a cycle. For instance, when ordering the points of a cycle p1 < p2 < ¼ < pn , one gets a cyclic permutation s corresponding to it, such that pi is mapped to ps(i) .
Combinatorial Dynamics deals with types of cycles (defined in various ways and not only for interval maps), their coexistence, complexity (usually measured by the topological entropy of the system) and properties of maps with cycles of a given type. The word "Combinatorial" refers not only to the fact that we often deal with permutations, but also to the techniques involved in the proofs, that are often of a combinatorial nature.
Another way of looking at the permutation given by a cycle (and forgetting about the orientation of the interval) is to say that two cycles, P of the map f : I®I and Q of the map g : J®J, have the same pattern if there is a homeomorphism h : I®J such that h(P) = Q and h(f (x)) = g(h(x)) for xÎP. We say that a pattern A forces pattern B if any interval map with a cycle of pattern A has also a cycle of pattern B. For other definitions of the "type" of a cycle, we define forcing in the same way. Note that by Sharkovsky's Theorem, forcing among periods is a linear ordering.
Theorem 1.1: Forcing among patterns is a partial ordering.
There is another notion, between the period and the pattern, that gives us also a linear ordering. Let q be the period of a cycle P of f, and let m be the number of times f (x) - x changes sign when x moves along P (that is, x = y, f (y), ¼, f q-1(y), y). Note that p = m/2 is an integer. We call the pair (p,q) the over-rotation pair of P and the number p/q the over-rotation number of P.
Theorem 1.2: For a given continuous interval map, the set of over-rotation numbers of all cycles of period larger than 1 is either the intersection of Q with an interval whose one endpoint is 1/2, or {1/2}, or Æ.
Theorem 1.3: Forcing among over-rotation pairs is a linear ordering.
This ordering can be described as follows. Suppose we want to compare two over-rotation pairs (p,q) and (r,s). If p/q > r/s then (p,q) forces (r,s); if p/q < r/s then (r,s) forces (p,q). If p/q = r/s then we write p/q as a fraction in the reduced form and take its denominator k. Both q,s are divisible by k, and the relation between (p,q) and (r,s) is the same as between q/k and s/k in the Sharkovsky's ordering.
Often we can identify the simplest patterns within some classes, for instance patterns that do not force any other pattern of the same period (primary patterns) or patterns that do not force any other pattern of the same over-rotation number (twist patterns).
The infimum of the topological entropies of maps with a cycle of a given pattern is called the entropy of a pattern. It indicates how chaotic a map has to be to accommodate a cycle of a given pattern. There are simple ways to compute this entropy, and cycles of the smallest entropy with a given period or over-rotation number have been identified.
Theorem 2.1: For a given continuous circle map of degree 1, the set of rotation numbers of all cycles is either the intersection of Q with a closed interval, or a singleton, or Æ.
Possible sets of periods are obtained by choosing the endpoints of the rotation interval and for each rational endpoint one element of N È{2¥}. Then periods are all denominators of the fractions from the interior of the rotation interval (not necessarily in the reduced form) and initial segment(s) of the Sharkovsky's ordering times the denominators of the endpoints of the rotation interval (reduced).
Thus, the description of the set of periods of such a map involves more data than in the case of interval maps, so the patterns and the forcing relation do not play important role here. Minimal entropy of maps with a given rotation interval is known.
For continuous tree maps (except maps of n-ods which fix the central point, where the situation resembles that for interval maps), despite substantial progress, the situation is still unclear. It seems that the idea of patterns can work, but one cannot fix the tree. That is, maps of different trees can have cycles with the same pattern.
For graph maps, basically nothing is known from the point of view of Combinatorial Dynamics.
For a map of a disk D into itself, one can define a pattern of a cycle in the following way. Cycles P of f and Q of g have the same pattern if there exists a homeomorphism h : D®D such that h(P) = Q, h(f (x)) = g(h(x)) for xÎP and g is isotopic to h ° f ° h-1 modulo Q (that is, the isotopy maps act on the points of Q in the same way as g). This is equivalent to the condition that the orbits that are obtained from P and Q when we take suspensions of f and g respectively have the same braid types (modulo full twists). The same definitions work for maps of any surface map isotopic to the identity.
Forcing among patterns can be defined in the same way as for interval maps, and Theorem 1.1 holds also in this case. Similar questions can be asked, although usually they are much harder than for interval maps. The classification of patterns uses the Nielsen-Thurston theory.
While for interval maps it is obvious whether two given cycles have the same pattern, in two dimensions the algorithm for doing that is quite complicated.
Rotation theory has a nice generalization for homeomorphisms of the torus isotopic to the identity. The displacement function takes values in R2, so this is where the rotation vectors live.
Theorem 3.1: For a homeomorphism of the torus isotopic to the identity the set of rotation vectors of cycles is equal to the intersection of Q2 with some compact convex set, except perhaps some points from interiors of segments contained in the boundary of this set.
An interesting problem is whether any compact convex subset of the plane is the rotation set of a torus homeomorphism.
[2] M. Bestvina and M. Handel, Train tracks for surface homeomorphisms, Topology 34 (1995), 109--140
[3] P. Boyland, Topological methods in surface dynamics, Topology Appl. 58 (1994), 223--298
[4] J. Franks and M. Misiurewicz, Cycles for disk homeomorphisms and thick trees, in Nielsen Theory and Dynamical Systems Conference Proceedings, Contemporary Math 152 (1993), 69--139
[5] J. Los, Pseudo-Anosov maps and invariant train tracks in the disc: a finite algorithm Proc. London Math. Soc. (3) 66 (1993), 400--430