# 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].

## Interval

### 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).

### 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*.

### 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.

## Other one-dimensional spaces

### 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.

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.

### 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.

### Graphs

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

## 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].

## 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]).

## 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.

## See also

Dynamical Systems, Periodic Orbits, Rotation Theory, Circle Maps, Topological Entropy.