Combinatorial dynamics

Combinatorial Dynamics is a part of the Dynamical systems theory dealing with the combinatorial structure of periodic orbits (called also cycles). It can be applied to continuous maps of one-dimensional compact spaces (the interval, trees, graphs) into itself and homeomorphisms of two-dimensional compact spaces (the disk, surfaces) onto itself. In dimension 1 the combinatorial structure comes from the comparison of the spatial and temporal orderings of the cycle; in dimension 2 it involves Braid Theory. One can take into account the full combinatorial structure or only some of its aspects (e.g., period, rotation number). When the aspect is fixed, one can speak of the types of cycles.

The main goal of Combinatorial Dynamics is to find all possible sets of types coexisting for the same map. An important tool for this is the forcing relation. A type \(A\) of cycles forces type \(B\) if every continuous map with a cycle of type \(A\) has a cycle of type \(B\). Sometimes this notion has to be modified to accommodate forcing of a type by a pair of types.

Another direction is to deduce other dynamical characteristics of the map (like estimates of topological entropy, chaoticity, etc.) from the knowledge of the set of types of all cycles of this map, or even better, from the knowledge of one or two types of its cycles.

For more information on Combinatorial Dynamics, see Alsedà, Llibre and Misiurewicz [2000] and Block and Coppel [1992] for dimension 1, and Boyland [1994] for dimension 2.

Combinatorial Dynamics should not be confused with combinatorics of one-dimensional endomorphisms, as described in the book of de Melo and van Strien [1993].

[edit] Interval

[edit] Periods

The simplest characteristic of a cycle is its period (that is, minimal period, or equivalently, the cardinality of the cycle). Sharkovsky's Theorem (Sharkovsky [1964]) describes the possible sets of periods of all cycles of a continuous map of an interval into itself.

Consider the following Sharkovsky ordering \(<_s\) of the set \(\mathbb{N}\) of natural numbers: \[ 1 <_s 2 <_s 2^2 <_s 2^3<_s 2^4 <_s \cdots <_s 2^n <_s \] \[ \cdots <_s \] \[ \cdots <_s 11 \times 2^n <_s 9 \times 2^n <_s 7 \times 2^n <_s 5 \times 2^n <_s 3 \times 2^n <_s \] \[ \cdots <_s \] \[ \cdots <_s 11 \times 2^2 <_s 9 \times 2^2 <_s 7 \times 2^2 <_s 5 \times 2^2 <_s 3 \times 2^2 <_s \] \[ \cdots <_s 11 \times 2 <_s 9 \times 2 <_s 7 \times 2 <_s 5 \times 2 <_s 3 \times 2 <_s \] \[ \cdots <_s 11 <_s 9 <_s 7 <_s 5 <_s 3 \] Denote by \(S(n)\) the initial segment of this ordering ending at \(n\in\mathbb{N}\ ,\) that is \(S(n)=\{m \in\mathbb{N} : m <_s n \} \cup \{n\}\ .\) Additionally set \(S(2^\infty)=\{1,2,2^2,2^3,2^4,\dots\}\ .\) For a map \(f\colon X \to X\) 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\colon I \to I\) there exists \(n\) in \(\mathbb{N} \cup \{2^\infty\}\) such that \(P(f)=S(n)\ .\) Conversely, for every \(n\) in \(\mathbb{N} \cup \{2^\infty\}\) there exists a continuous map \(f\colon I \to I\) such that \(P(f)=S(n)\ .\)

In particular, if \(k<_s n\) then period \(n\) forces period \(k\). The same theorem, but with the addition of the empty set as a possible set of periods, holds for the continuous maps of the real line into itself.

The minimal possible topological entropy of a continuous interval map which has a cycle of period \(n\cdot2^k\) with \(n\) odd, is \((1/2^k)\log\lambda_n\ ,\) where \(\lambda_n\) is the largest zero of the polynomial \(x^n-2x^{n-2}-1\) for \(n\ge 3\) and \(\lambda_1=1\ .\) For continuous interval maps, possessing a cycle of period \(n\cdot2^k\) with \(n\ge 3\) is equivalent to the positivity of topological entropy and to most forms of chaos (with maps for which \(P(f)=S(2^\infty)\) being borderline).

[edit] Patterns

Numbering points of a cycle according to their position on the interval and looking how the map permutes them is equivalent to the following approach (which also neglects the orientation of the interval). Two cycles, \(P\) of a map \(f\colon I \to I\) and \(Q\) of a map \(g\colon J \to J\ ,\) have the same pattern if there is a homeomorphism \(h\colon I \to J\) such that \(h(P)=Q\) and \(h(f(x))=g(h(x))\) for \(x\) in \(P\). While there are too many patterns to describe all possible sets of patterns of cycles for continuous interval maps, it is known that the forcing relation among patterns is a partial ordering. For each \(n\) the patterns of period \(n\) that do not force any other patterns of the same period have been identified. If \(n\ge 3\) is odd, they are Štefan patterns.

Figure 1: Štefan pattern of period 7. Its over-rotation pair is (3,7).

[edit] Over-rotation numbers

There is another notion, between the period and the pattern, for which forcing is 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), \dots f^{q-1}(y), y\)). Note that \(p=m/2\) is an integer. The pair \((p,q)\) is called the over-rotation pair of \(P\) and the number \(p/q\) is the over-rotation number of \(P\) (Blokh and Misiurewicz [1997]). 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 the set \(\mathbb{Q}\) of all rational numbers with an interval whose one endpoint is \(1/2\ ,\) or \(\{1/2\}\ ,\) or it is empty. 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 ordering.

[edit] Other one-dimensional spaces

[edit] Circle

Continuous circle maps are classified by their degree. The most interesting case is when the degree is 1 (maps homotopic to the identity). In this case, an important characteristics of a cycle is its rotation number. It is defined as the number of times the orbit goes around the circle, divided by the period. To measure it, one has to fix a lifting \(F\colon\mathbb{R}\to\mathbb{R}\) of the map, where the circle is \(\mathbb{R}/\mathbb{Z}\ .\) The rotation number is equal to the average along the cycle of the displacement function \(\varphi(x)=F(y)-y\) where \(y\) in \(\mathbb{R}\) projects to \(x\). The over-rotation number for interval maps mentioned earlier is an analogue of this notion; instead of the displacement function one takes \(\psi(x)\) equal to \(1/2\) if \((f^2(x)-f(x))(f(x)-x)>0\ ,\) and 0 otherwise.

Figure 2: A cycle of a circle map and its lifting. The period of the cycle is 5 and its rotation number is 1/5.

For a given continuous circle map \(f\) of degree 1, the set of rotation numbers of all cycles is either the intersection of \(\mathbb{Q}\) with a closed interval (the rotation interval of \(f\)), or a singleton, or \(\emptyset\ .\)

Possible sets of periods are obtained by choosing the endpoints of the rotation interval and for each rational endpoint one element of \(\mathbb{N}\cup\{2^\infty\}\ .\) Then the periods are all the denominators of the fractions from the interior of the rotation interval (not necessarily in the reduced form) and initial segment(s) of the Sharkovsky ordering multiplied by the denominators of the endpoints of the rotation interval (reduced).

Since the description of the set of periods of such a map involves more data than in the case of interval maps, the patterns and the forcing relation do not play important role here. Minimal entropy of maps with a given rotation interval is known.

[edit] Trees

For continuous tree maps, the problem of finding all possible sets of periods of cycles is solved when one admits all possible trees (Alsedà, Juher and Mumbrú [2005]). The characterization involves more orderings than the Sharkovsky one, so called Baldwin orderings. Those orderings are connected with the order in which the denominators of rational numbers appear as those numbers approach a given rational number (for the Sharkovsky ordering this number is 1/2; this can be deduced from the over-rotation numbers approach).

In the proofs, the idea of a pattern plays the central role. However, the definition of a pattern is more sophisticated than for interval maps. In particular, cycles of maps of distinct trees can have the same pattern.

[edit] Graphs

For graph maps, the question about all possible sets of periods of cycles is much harder, and only a few partial results exist.

[edit] Dimension 2

For homeomorphisms of a compact surface (perhaps with boundary) \(M\) onto itself, the only restriction for the sets of periods of cycles is that for certain surfaces there has to be a fixed point. However, one can define a pattern of a cycle for homeomorphisms isotopic to the identity. Cycles \(P\) of \(f\) and \(Q\) of \(g\) have the same pattern if there exists a homeomorphism \(h \colon M \to M\) such that \(h(P)=Q\ ,\) \(h(f(x))=g(h(x))\) for \(x\) in \(P\) and \(g\) is isotopic to \(h \circ f \circ 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).

Forcing among patterns is a partial ordering also in this case. The classification of patterns for surface homeomorphisms uses the Nielsen-Thurston theory, see e.g., Bestvina and Handel [1995]. While for interval maps it is obvious whether two given cycles have the same pattern, in two dimensions the algorithm for doing this is quite complicated. Information about patterns appearing in the Smale horseshoe can be found in the paper of de Carvalho and Hall [2004].

[edit] Generalizations

Parts of the theory can be generalized for certain discontinuous interval maps (for instance, Lorenz-like maps) instead of continuous maps (Alsedà, Llibre, Misiurewicz and Tresser [1989]), or for objects other than cycles. Possible choices for those objects include finite invariant sets (Misiurewicz and Nitecki [1991]) or minimal sets (Bobok [2001], see also Bobok [2005]).

[edit] References

Ll. Alsedà, J. Llibre and M. Misiurewicz [2000]: Combinatorial dynamics and entropy in dimension one, Second Edition, World Scientific (Advanced Series in Nonlinear Dynamics, vol. 5), Singapore.

L. Alsedà, J. Llibre, M. Misiurewicz and C. Tresser [1989]: Periods and entropy for Lorenz-like maps, Ann. Inst. Fourier 39, 929-952.

Ll. Alsedà, D. Juher and P. Mumbrú [2005]: Periodic behavior on trees, Ergod. Th. & Dynam. Sys. 25, 1373-1400.

M. Bestvina and M. Handel [1995]: Train tracks for surface homeomorphisms, Topology 34, 109-140.

L. S. Block and W. A. Coppel [1986]: Dynamics in one dimension, Lecture Notes in Math. 1513, Springer, Berlin.

A. M. Blokh and M. Misiurewicz [1997]: New order for periodic orbits of interval maps, Ergod. Th. & Dynam. Sys. 17, 565-574.

J. Bobok [2001]: Forcing relation on minimal interval patterns, Fund. Math. 169, 161-173.

J. Bobok [2005]: Forcing relation on interval patterns, Fund. Math. 187, 37-60.

P. Boyland [1994]: Topological methods in surface dynamics, Topology Appl. 58, 223-298.

A. de Carvalho and T. Hall [2004]: Braid forcing and star-shaped train tracks, Topology 43, 247-287.

W. de Melo and S. van Strien [1993]: One-Dimensional Dynamics, Springer, Berlin.

M. Misiurewicz and Z. Nitecki [1991]: Combinatorial patterns for maps of the interval, Mem. Amer. Math. Soc. 94, no. 456.

A. N. Sharkovsky [1964]: Co-existence of the cycles of a continuous mapping of the line into itself, Ukrain. Math. Zh. 16 (1), 61-71.

Internal references

James Meiss (2007) Dynamical systems. Scholarpedia, 2(2):1629.
Tomasz Downarowicz (2007) Entropy. Scholarpedia, 2(11):3901.
Jeff Moehlis, Kresimir Josic, Eric T. Shea-Brown (2006) Periodic orbit. Scholarpedia, 1(7):1358.
Michał Misiurewicz (2007) Rotation theory. Scholarpedia, 2(10):3873.
Steve Smale and Michael Shub (2007) Smale horseshoe. Scholarpedia, 2(11):3012.