\input amstex \input amssym.tex \documentstyle{amsppt} \magnification=1200 %\pagewidth{6in} %\pageheight{8in} \hcorrection{.25in} \advance\vsize-.75in %\NoRunningHeads %\NoBlackBoxes \define \s{Shar\-kov\-ski\u\i} \define \per{\operatorname{Per}} \define \perm{permutation} \define \perms{\perm s} \define \sg{>_{\text S}} \define \shl{<_{\text S}} \define \sge{\ge_{\text S}} \define \sle{\le_{\text S}} \define \pcw{primitive closed walk} \define \th{\theta} \define \conts{continuous} \define \pwm{piecewise monotone} \define \fos{finite ordered set} \define \mono{monotone} \define \mcm{minimal combinatorial model} \define \mpm{minimal \perm\ model} \define \piwm{$\pi$@-weakly monotone} \define \thwm{$\th$@-weakly monotone} \define \rrmin{reduction- and \resmin} \define \Wlog{Without loss of generality} \define \redmin{reduction-minimal} \define \resmin{restriction-minimal} \define \Mg{Markov graph} \define \bs{block structure} \define \sc{simple cycle} \topmatter \title Minimal combinatorial models for maps of an interval with a given set of periods \endtitle \leftheadtext {L. Block, E. M. Coven, W. Geller, and K. Hubner} \rightheadtext {Minimal combinatorial models} \subjclass Primary 37E15; Secondary 37E05 \endsubjclass \thanks Some of the results in this paper first appeared in the 1994 Wesleyan University Ph.D. thesis of the fourth author; some were proved in 1998 while the second and third authors were members of MSRI, where research was supported by NSF grant DMS@-970155; and some were proved in 1998@-99 while the first author was Van Vleck Visiting Professor of Mathematics at Wesleyan University. \endthanks \author Louis Block\\Ethan M. Coven\\William Geller\\Kristin Hubner \endauthor \address{Louis Block, Deparment of Mathematics, University of Florida, Gainseville, FL 32611-8105} \endaddress \email{block\@math.ufl.edu} \endemail \address{Ethan M. Coven, Deparment of Mathematics, Wesleyan University, Middletown, CT 06459-0128} \endaddress \email{ecoven\@wesleyan.edu} \endemail \address{William Geller, Department of Mathematics, IUPUI, Indianapolis, IN 46202-3216} \endaddress \email{wgeller\@math.iupui.edu} \endemail \address {Kristin Hubner, Deparment of Mathematics, Wesleyan University, Middletown CT 06459-0128} \endaddress \curraddr {Innosoft International Inc., 1050 Lakes Drive, West Covina CA 91790} \endcurraddr \email{kristin.hubner\@sun.com} \endemail \abstract A combinatorial model for a property of continuous self-maps of a compact interval is a self map $\pi$ of a finite ordered set such that every continuous $\pi$-weakly monotone self-map of a compact interval has that property. We identify the minimal combinatorial models for the property ``the set of periods is a given set.'' Here the word minimal refers to the number of points in the domain of the model. We also identify the minimal permutation models, and in appropriate cases, the minimal combinatorial models for properties involving ``horseshoes.'' \endabstract \endtopmatter \document \bigpagebreak \head Introduction \endhead \bigpagebreak A {\it combinatorial model\/} for a property of continuous self-maps of a compact interval is a self-map~$\pi$ of a finite ordered set such that every \conts\ \piwm\ self-map of a compact interval has the property. Not every dynamical property has a combinatorial model. For example, the property ``$f$ has a dense orbit'' does not. We also consider {\it \perm\ models}, where we require that ~$\pi$ be a \perm. We consider the following two properties: \noindent$\bullet$ the set of periods of~$f$ is a given set of positive integers. \newline\noindent $\bullet$ the set of periods of~$f$ is a given set of positive integers and $f^{2^k}$ does not have a horseshoe. ({\it Horseshoe\/} is defined in Section~1.) We show that for every set, other than the set of all powers of~$2$, which is the set of periods of some continuous self-map of a compact interval, both properties have combinatorial models. For the properties above, we characterize the {\it \mcm s} and the {\it \mpm s}, where {\it minimal\/} refers to the cardinality of the domain of~$\pi$, denoted~$\#\pi$. It turns out that either every \mcm\ is a \perm\ or none are. Suppose that $\pi : P \to P$ is a self-map of a \fos\ $P = \{p_1 < p_2 < \dots < p_n\}$ and $f: I \to I$ is a self-map of a compact interval. $f$ is {\it \piwm\/} iff (here, and throughout the paper, we use {\it iff\/} for {\it if and only if\/} in definitions) there exist $x_1 < x_2 < \dots < x_n$ in~$I$ such that $I = [x_1,x_n]$, $f(x_i) = x_j$ if $\pi(p_i) = p_j$, and $f$ is weakly (i.e., not necessarily strictly) monotone on every subinterval~$[x_i,x_{i+1}]$. We will show, in Theorems 1.7 and 2.3, that for each of the properties that we are considering, whether a \conts, \piwm\ map has the property depends only on~$\pi$, and not on the map. Let $\per(f)$ denote the set of (least) periods of the points in the domain of~$f$, and let $\shl$ (\s-less than) be the \s\ order on the positive integers, defined in Section~1. It follows from the Theorem of \s, stated in Section~1, that $\per(f)$ is of one of the following: \roster \item $\{t : t \sle 2^k\}$ for some $k \ge 0$. \item $\{t : t \text{ is a power of}~2\}$. \item $\{t : t \sle 3 \cdot 2^k\}$ for some $k \ge 0$. \item $\{t : t \sle n \cdot 2^k\}$ for some $k \ge 0$, and some odd $n \ge 5$. \endroster We will use the term {\it simple cycle\/}, which we define in Section~1 for cycles of length a power of~$2$, and in Section~5 for cycles of other lengths. Our usage corresponds to the usage of the term {\it simple\/} in~\cite{ALM} and to the usage of the term {\it strongly simple\/} in~\cite{BCop}. In Section~1, we define the {\it Markov graph\/} of a self-map of a \fos\ and prove the following. \proclaim{Theorem 1.7}{\sl Let $\pi$ be a self-map of a \fos. Then every \conts, \piwm\ map has the same set of periods. } \endproclaim In light of Theorem~1.7, we define the {\it set of periods\/} of~$\pi$, $\per(\pi)$, to be the set of periods of any \conts, \piwm\ map. \proclaim{Theorem 1.8}{\sl Let $\pi$ be a self-map of a \fos. Then every period of~$\pi$ is the length of a subcycle of~$\pi$ or is the length of a \pcw\ in the Markov graph of~$\pi$. Conversely, every such number is a period of~$\pi$. } \endproclaim \proclaim{Theorem 1.9}{\sl The \mcm s for ``$\per(f) = \{t : t \sle 2^k\}$'' are the simple cycles of length~$2^k$. } \endproclaim We also show that there is no \conts, \piwm\ self-map of a compact interval for which the set of periods is the set of all powers of~$2$ (Theorem~1.4). In Section~2, we show that if the $k$@-th power of some \conts, \piwm\ map has a horseshoe, then so does the $k$@-th power of every \conts, \piwm\ map. This can be seen in the Markov graph of~$\pi$, and we say that {\it the $k$@-th power of the Markov graph of ~$\pi$ has a horseshoe}. We remind the reader that if $f$ is \conts\ and \piwm, then $f^k$ need not be $\pi^k$-weakly monotone. Thus the terminology ``$\pi^k$ has a horseshoe'' would not be appropriate in this case. In Section~3, we define {\it \rrmin}, using the concept of block structure \cite{MN}. We prove that \mcm s for the properties under consideration must be \rrmin. The following result, proved in Section~4, is a crucial step in characterizing \mcm s. \proclaim{Theorem 4.3}{\sl Suppose that $\pi$ is a \rrmin\ self-map of a \fos, such that $\per(\pi)$ is not a subset of the powers of~$2$, and such that the $2^k$@-th power of the Markov graph of ~$\pi$ does not have a horseshoe. Then $\pi$ has a block structure over a simple cycle of length~$2^k$. } \endproclaim \proclaim{Theorem 5.2}{\sl The \mcm s for ``$\per(f) =\{t : t \sle 3 \cdot 2^k\}$ and $f^{2^k}$ does not have a horseshoe'' are the simple cycles of length~$3 \cdot 2^k$. } \endproclaim We also give necessary and sufficient conditions for $\pi$ to be a \mpm\ for ``$\per(f) = \{t : t \sle 3 \cdot 2^k\}$'' (Theorem~5.3). In this case, $\#\pi = 3 \cdot 2^k$, but $\pi$ need not be a cycle. Finally, we give necessary and sufficient conditions for $\pi$ to be a \mcm\ for ``$\per(f) = \{t : t \sle 3 \cdot 2^k\}$.'' In this case, if $k \ge 1$, then $\#\pi = 3 \cdot 2^{k-1} + 1$ and $\pi$ is not a \perm. In Section 6, we prove out last main result. \proclaim{Theorem 6.1}{\sl Suppose that $r \ge 5$ is odd. Then the \mcm s for ``$\per(f) = \{t : t \sle r \cdot 2^k\}$'' are the simple cycles of length~$r \cdot2^k$. } \endproclaim This implies, for example, that if $f$ is \conts, \piwm, and $\per(f) = \{t : t \sle 1,000,000\}$, then $\#\pi \ge 1,000,000$. We conclude the paper with a brief discussion of unimodal \mcm s in ~Section 7. An informal way to summarize some of the conclusions of this paper is the following. For the property that the set of periods is a given set, the only way to obtain a \mcm\ which is not a simple cycle is to create an appropriate horseshoe. In particular, this is possible if and only if the \s-largest member of the given set is ~$3 \cdot 2^k$ for some $k \ge 0$. The ``turbulence stratification'' \cite{BCop, p.~34} is relevant here. \head 1. Periods, subcycles, and closed walks \endhead Let $\pi : P \to P$ be a self-map of a \fos. We will write $\# \pi$ for the cardinality of~$P$. \proclaim{Definition} {\sl Let $\pi : P \to P$, where $P = \{p_1 < p_2 < \dots < p_n\}$. The {\it Markov graph} of~$\pi$, is a directed graph, with $n-1$ vertices, $V_1,V_2,\dots,V_{n-1}$, and an arc from ~$V_i$ to~$V_j$, written $V_i \to V_j$, iff either $\pi(p_i) \le p_j$ and $\pi(p_{i+1}) \ge p_{j+1}$, or $\pi(p_i) \ge p_{j+1}$ and $\pi(p_{i+1}) \le p_j$. } \endproclaim \proclaim{Definition} {\sl Let $\pi : P \to P$, where $P = \{p_1 < p_2 < \dots < p_n\}$, and let $f: I \to I$ be a self-map of a compact interval. We say that $f$ is {\it \piwm\/} iff there is a subset $Z_\pi = \{z_1 < z_2 < \dots < z_n\}$ of~$I$ such that $I = [z_1,z_n]$, $f(z_i) = z_j$ if and only if $\pi(p_i) = p_j$, and $f$ is weakly (i.e., not necessarily strictly) monotone on each subinterval~$[z_i,z_{i+1}]$ of~$I$. We call~$Z_\pi$ a $\pi$@-{\it set}, its members $\pi$@-{\it points}, and the intervals ~$[z_i,z_{i+1}]$ $\pi$@-{\it intervals}. } \endproclaim We remind the reader that a continuous, piecewise weakly monotone self-map $f : I \to I$ of a compact interval has finitely many turning points and finitely many turning intervals. (A {\it turning point\/} is a point~$x \in I$ such that either $f(x-\epsilon), f(x+\epsilon) > f(x)$ for all small $\epsilon > 0$, or $f(x-\epsilon), f(x+\epsilon) < f(x)$ for all small $\epsilon > 0$. A {\it turning interval\/} is a nondegenerate subinterval, $J = [a,b]$ of~$I$, such that $f(J)$ is one point, and either $f(a-\epsilon), f(b+\epsilon) > f(J)$ for all small $\epsilon > 0$, or $f(a-\epsilon), f(b+\epsilon) < f(J)$ for all small $\epsilon > 0$.) \remark{Remark} If $f$ is continuous and \piwm, then every turning point is a $\pi$@-point and every turning interval contains a $\pi$@-point. \endremark \proclaim{Definition} {\sl Let $\pi : P \to P$, where $P = \{p_1 \pi(p_{k-1}),\pi(p_{k+1})$.} \endproclaim \proclaim{Definition} {\sl Let $\pi : P \to P$, where $P = \{p_1 1$, or (3) $k=\ell$ and $1 \ell$ and $r,s > 1$. \smallpagebreak \s's Theorem (\cite{ALM},\cite{BCop}) states that for every \conts\ self-map ~$f$ of a compact interval, if $n$ is a period of some point in the domain of~$f$ and if $k \shl n$, then $k$ is also a period of some point in the domain of~$f$. In symbols, if $n \in \per(f)$, then $\per(f) \supseteq \{k : k \sle n\}$. In particular, if the set of periods of~$f$ is not the set of all the powers of~$2$, then it is determined by its \s-largest member. \proclaim{Theorem 1.4} {\sl There is no continuous, \piwm\ self-map of a compact interval such that the set of periods is the set of all powers of~$2$.} \endproclaim \demo{Proof} Let $\pi : P \to P$ be a self-map of a \fos, and suppose there were such a map~$f$. For every subcycle of~$\pi$, there is an $f$@-periodic point whose period is the length of that subcycle. Therefore, the length of every subcycle of~$\pi$ is a power of~$2$. Let $2^k \ge \#\pi$. Since $f$ has a periodic point of period~$2^{k+1}$, by Lemma~1.2 there is a \pcw\ of length~$2^k$ or ~$2^{k+1}$ in the Markov graph of~$\pi$. Since the graph has $\#\pi - 1$ vertices, this walk must pass through the same vertex twice. Therefore, there are distinct closed walks starting at the same vertex. Going around one of these walks once and around another one twice gives a closed walk of length not a power of~$2$. The resulting walk is either primitive or it is a \pcw\ of length not a power of~$2$, traversed several times. Then, by Lemma~1.3, $f$ has a periodic point of period not a power of~$2$. \qed \enddemo \proclaim{Definition} {\sl $f: I \to I$ has a {\it horseshoe\/} iff there exist subintervals $J$ and $K$ of~$I$, with at most one point in common, such that $f(J),f(K) \supseteq J \cup K$.} \endproclaim It is well-known, \cite{BCop, Lemma II.3}, that if a continuous self-map of a compact interval has a horseshoe, then it has a periodic point of period~$3$. We remark that a map which has a horseshoe is said to be turbulent in~\cite{BCop} and is said to have a $2$-horseshoe in~\cite{ALM}. \proclaim{Lemma 1.5} {\sl Suppose that $f$ is continuous and \piwm, and that the \s-largest period of the periodic points of~$f$ is~$2$. Then $\pi$ has a subcycle of length~$2$.} \endproclaim \demo{Proof} Suppose that all the subcycles of $\pi$ have length~$1$. Let $\{v,w\}$ be a periodic orbit of period~$2$. \Wlog, $v < w$. Then both $v$ and ~$w$ are in the interiors of $\pi$@-intervals. Let $a$ be the left endpoint of the $\pi$@-interval containing~$v$, and let $d$ be the right endpoint of the $\pi$@-interval containing~$w$. If there is at least one $\pi$@-point between $v$ and $w$, let $b$ be the right endpoint of the $\pi$@-interval containing~$v$, and let $c$ be the left endpoint of the $\pi$@-interval containing~$w$. If not, let $b = c$ be the unique fixed point of ~$f$ between $v$ and~$w$. Then $a < b \le c < d$, $f[a,b] \supseteq [c,d]$, and $f[c,d] \supseteq [a,b]$. It follows that $f^k[a,b] \supseteq [a,b]$ for all even~$k$, and that for some even~$k$, $f^k(a)$ is a fixed point of $f$ . Write $x = f^k(a)$. Then $x \le a$ or $x \ge b$. Suppose first that $x \le a$. Since $k+1$ is odd, $f^{k+1}[a,b] \supseteq [x,d]$. Therefore $f^{k+1}[a,b] \supseteq [a,b], f^{k+1}[a,b] \supseteq [c,d]$ and $f^{k+1}[c,d] \supseteq [a,b]$. Thus $[a,b]$ and $[c,d]$ exhibit a horseshoe for ~$f^{2k+2}$. Then $3 \in \per(f^{2k+2})$ and so $2$ is not the \s-largest period of~$f$. Suppose then that $x \ge b$. Then there is a point~$y$ with $a < y < x$, such that $f^k(y) = a$. (For if $x > b$, then there exists ~$y$, $a < y \le b$, such that $f^k(y) = a$; then $y < x$. If $ x = b$, then $f^k(b) = b$, so there exists $y < b = x$ such that $f^k(y) = a$.) But then $[a,y]$ and $[y,x]$ exhibit a horseshoe for ~$f^k$. As above, $2$ is not the \s-largest period of~$f$. \qed \enddemo \proclaim{Theorem 1.6} {\sl Suppose that $\pi$ is a self-map of a \fos, and that $f$ is a continuous and \piwm\ map. If the \s-largest period of~$f$ is a power of\/~$ 2$, then $\pi$ has a subcycle of that length.} \endproclaim \demo{Proof} Suppose that $\pi : P \to P$. We prove by induction on~$k$ that if $f: I \to I$ is continuous and \piwm, and if the \s-largest period of~$f$ is~$2^k$, then $\pi$ has a subcycle of length~$2^k$. Suppose that $k=0$. Since the length of every subcycle of~$\pi$ is also the period of some periodic orbit of~$f$, it follows that $\pi$ has no subcycles of length other than~$1$, and hence has a subcycle of length~$1$. The result is true for $k = 1$ by Lemma~1.5. Suppose that $k \ge 1$ and that the result is true for~$k$; we prove it for~$k+1$. Let $Z_\pi$ be a $\pi$@-set for~$f$. Define $\theta : Q \to Q$ as follows. Let $Q$ be the union of ~$Z_\pi$ and the set of endpoints of the connected components of~$f^{-1}(Z_\pi)$, and let $\theta = f^2|_Q$. Then $f^2$ is $\theta$@-weakly monotone. We have $\per(f) = \{1,2,\dots,2^{k+1}\}$ and $\per(f^2) = \{1,2,\dots,2^k\}$. By the inductive hypothesis, $\theta$ has a subcycle of length~$2^k$. Because $\th(Q) \subseteq Z_\pi$, this subcycle is contained in ~$Z_\pi$. Hence $\pi^2$ has a subcycle of length~$2^k$. Since $k \ge 1$, $2^k$ is even, and so $\pi$ has a subcycle of length~$2^{k+1}$. \qed \enddemo \proclaim{Theorem 1.7} {\sl Let $\pi$ be a self-map of a \fos. Then every continuous, \piwm\ map has the same set of periods.} \endproclaim \demo{Proof} Let $f$ be \conts\ and \piwm. By Theorem~1.4, it suffices to show that ~(1) and~(2) hold. \smallpagebreak \noindent (1) If every subcycle of~$\pi$ and every \pcw\ in the Markov graph of~$\pi$ have length a power of~$2$, then the \s-largest period of ~$f$ is the length of the \s-longest subcycle of~$\pi$. \noindent (2) If some subcycle of~$\pi$ or some \pcw\ in the Markov graph of~$\pi$ has length not a power of~$2$, then the \s-largest period of ~$f$ is the \s-largest of the following two numbers: the \s-longest subcycle of~$\pi$ and the length of the \s-longest \pcw\ in the Markov graph of ~$\pi$. \smallpagebreak \noindent (1) By Lemma~1.2, the \s-largest period of ~$f$ is a power of~$2$. By Theorem~1.6, the \s-largest period of ~$f$ is the length of the \s-longest subcycle of~$\pi$. \noindent (2) Consider the lengths of the \s-longest subcycle of~$\pi$ and of the \s-longest \pcw\ in the Markov graph of~$\pi$. By Lemma~1.2, the \s-largest period of ~$f$ is \s-less than or equal to one of these numbers. By Lemma~1.3, the \s-largest period of ~$f$ is \s-greater than or equal to both of them. \qed \enddemo In light of Theorem~1.7, we introduce the the following notation and terminology. \proclaim{Notation} {\sl For $\pi$ a self-map of a \fos, $\per(\pi)$, called the {\it set of periods\/} of~$\pi$, is the set of periods of any (equivalently, every) continuous, \piwm\ map.} \endproclaim A result stronger than Theorem~1.7 holds. \proclaim{Theorem 1.8} {\sl Let $\pi$ be a self-map of a \fos. Then every period of~$\pi$ is the length of a subcycle of ~$\pi$, or is the length of a \pcw\ in the Markov graph of ~$\pi$. Conversely, every such number is a period of~$\pi$.} \endproclaim \demo{Proof} By Theorem~1.7, $\per(\pi) = \per(L_\pi)$, where $L_\pi$ is the canonical $\pi$@-linear map. We show that if $n \in \per(L_\pi)$, but no subcycle of~$\pi$ has length~$n$ (i.e., no $\pi$@-point has period~$n$), then there is a \pcw\ of length~$n$ in the Markov graph of~$\pi$. Suppose that $x$ is $L_\pi$@-periodic of period~$n$. Then $x$ follows a closed walk $V_{i_0} \to V_{i_1} \to \dots \to V_{i_{n-1}} \to V_{i_0}$ of length~$n$. By Lemma~1.2, the walk is primitive, or is $V_{i_0} \to V_{i_1} \to \dots \to V_{i_{(n/2)-1}} \to V_{i_0}$ traversed twice. Suppose the latter holds. There are exactly two points, $x$ and~$L_\pi^{n/2}(x)$, in the orbit of ~$x$ which lie in the $\pi$@-interval $[i_0,i_0+1]$. $L_\pi^{n/2}$ maps the interval with endpoints $x$ and~$L_\pi^{n/2}(x)$ linearly onto itself with slope ~$-1$. We claim that $L_\pi^{n/2}$ maps the $\pi$@-interval $[i_0,i_0+1]$ linearly onto itself with slope ~$-1$. \Wlog, $x < L_\pi^{n/2}(x)$. Let $y \in [i_0,x]$ be the point closest to~$x$ such that $L_\pi^{n/2}(y)$ is a $\pi$@-point. Similarly, let $w \in [L_\pi^{n/2}(x),i_0+1]$ be the point closest to~$L_\pi^{n/2}(x)$ such that $L_\pi^{n/2}(w)$ is a $\pi$@-point. Since $L_\pi^{n/2}[x,L_\pi^{n/2}(x)]$ contains no $\pi$@-points, $L_\pi^{n/2}$ maps $[y,w]$ linearly onto $[i_0,i_0+1]$ with slope~$-1$. Therefore $y = i_0$ and $w = i_0+1$. Now $i_0$ and $i_0+1$ are fixed points of~$L_\pi^n$, and are in the same $L_{\pi}$@-orbit. If $i_0$ had period $m < n$, then $x$ would be a fixed point of~$L_\pi^m$. Since this is not the case, $i_0$ has period~$n$. To prove the converse, it suffices by Lemma~1.3 and \s's Theorem, to prove that if the Markov graph of~$\pi$ has a \pcw\ of length $2^m$, then $2^m$ is a period of~$\pi$. Suppose that $2^m$ is the length of a \pcw\ in the Markov graph of~$\pi$, but that $2^m$ is not a period of~$\pi$. Let $f$ be continuous and \piwm, with $\pi$@-set $Z_\pi$. It follows, as in the proof of Lemma~1.3, that there is a $\pi$@-point~$z_k \ne \max Z_\pi$ or~$\min Z_\pi$, which is periodic of period~$2^{m-1}$, and there are walks of length~$2^{m-1}$ in the Markov graph of~$\pi$ from~$V_k$ to~$V_{k-1}$ and from~$V_{k-1}$ to~$V_k$. There are points $a \in [z_{k-1},z_k)$ and $d \in (z_k,z_{k+1}]$ such that $f^{2^{m-1}}(a) = z_{k+1}$ and $f^{2^{m-1}}(d) = z_{k-1}$. Then, setting $b = c = z_k$ and $g = f^{2^{m-1}}$, we have $a < b \le c < d$, $g(a) \ge d$, $g(d) \le a$, $g(b) = b$, $g(c) = c$, and there are no $\pi$@-points in~$(a,b)$. In addition, $\per(g) = \{1\}$, and for some even~$j \ge 0$, $g^j(a)$ is both a $\pi$@-point and a fixed point of~$g$. This leads to a contradiction as in the proof of Lemma~1.5. \qed \enddemo \remark{Remark} The proof of Theorem~1.8 shows that if $\pi$ has no subcycle of length~$n$, then every $L_\pi$@-periodic point of period~$n$ follows a \pcw\ of length~$n$. This is not true for arbitrary continuous, \piwm\ maps in place of ~$L_\pi$รพ. Let $\pi = \left(\smallmatrix 1&2&5&6\\ 5&6&2&1 \endsmallmatrix\right)$ and $\th = \left(\smallmatrix 1&2&3&4&5&6\\ 5&6&4&3&2&1 \endsmallmatrix\right)$. Then $L_\th$ is \piwm, and $x = 3$ is a point of $L_\th$@-period~$2$ which does not follow a \pcw\ of length~$2$ in the Markov graph of ~$\pi$. Theorem 1.8 also shows that for every \pcw\ in the Markov graph of~$\pi$, there is an $L_\pi$@-periodic point of that period. But there need not be such a point which follows the walk. Consider $\pi = \left(\smallmatrix 1&2&3&4&5\\ 4&5&3&2&1 \endsmallmatrix\right)$, and the \pcw\ $V_2 \to V_3 \to V_2$. Then $2$ is a period of ~$\pi$, but no $L_\pi$@-periodic point of period~$2$ follows this walk. \endremark \proclaim{Definition} {\sl Let $\pi : P \to P$ be a cyclic \perm\ of a \fos, $P = \{p_1 < p_2 < \dots < p_{2^k}\}$, of cardinality $2^k$, $ k \ge 0$. If $k=0$, we say that $\pi$ is a {\it simple cycle\/} of length~$1$. If $ k > 0$, set $L = \{p_1 < p_2 < \dots < p_{2^{k-1}}\}$ and $R = \{p_{2^{k-1}+1} < p_{2^{k-1}+2} < \dots < p_{2^k}\}$. We say that $\pi$ is a {\it simple cycle\/} of length~$2^k$ iff $\pi(L) = R$, $\pi(R) = L$, and both $\pi^2|_L$ and $\pi^2|_R$ are simple cycles of length~$2^{k-1}$.} \endproclaim Suppose, for example, that $\pi : P \to P$ a simple cycle of length~$8$, where $P = \{p_1 < p_2 < \dots < p_8\}$. It follows from the definition that $\pi\{p_1,p_2,p_3,p_4\} = \{p_5,p_6,p_7,p_8\}$ and $\pi\{p_5,p_6,p_7,p_8\} = \{p_1,p_2,p_3,p_4\}$. Furthermore, $\pi$ maps each of the sets $\{p_1,p_2\}$ and $\{p_3,p_4\}$ onto one of the sets $\{p_5,p_6\}$ and $\{p_7,p_8\}$, and vice versa. Therefore, there are exactly three \pcw s in the Markov graph of~$\pi$, namely $V_4 \to V_4$, $V_2 \to V_6 \to V_2$, and a walk of length ~$4$ passing through the vertices $V_1,V_3,V_5,V_7$. Using the same analysis for arbitrary $k > 0$, we have \remark{Remark} Suppose that $\pi : P \to P$ is a simple cycle of length~$2^k$, $k > 0$, and let $t$ be a positive integer. Then there is a \pcw\ of length~$t$ in the Markov graph of~$\pi$ if and only if $t = 2^j$ for some $j < k$. In particular, there is no \pcw\ of length ~$2^k$ in the Markov graph of~$\pi$. \endremark \proclaim{Theorem 1.9} {\sl For every $k \ge 0$, the \mcm s for ``$\per(f) = \{t : t \sle 2^k\}$'' are the simple cycles of length~$2^k$. } \endproclaim \demo{Proof} It suffices to consider only $k > 0$, and to prove~(1) and~(2). \noindent (1) Every simple cycle ~$\pi$ of length~$2^k$ satisfies $\per(\pi) = \{t : t \sle 2^k\}$. \noindent (2) Every \mcm\ for ``$\per(f) = \{t : t \sle 2^k\}$'' is a simple cycle of length~$2^k$. Statement (1) follows from Theorem~1.8 and the Remark immediately preceding the statement of this theorem. To prove~(2), suppose that $\pi$ is a \mcm\ for ``$\per(f) = \{t : t \sle 2^k\}$.'' Then, by~(1), $\#\pi \le 2^k$, and so by Theorem~1.6, $\pi$ is a cycle of length~$2^k$. By \cite{BCop, Theorem VII.24} (see also \cite{B}), if a \conts\ self-map of a compact interval has a periodic point of period~$2^k$ whose orbit is not simple, then it has a periodic point whose period is not a power of~$2$. It follows that $\pi$ is a simple cycle of length~$2^k$. \qed \enddemo \proclaim{Definition}{\sl Two self-maps of \fos s, $\pi: P \to P$ and $\th : Q \to Q$, are {\it equivalent\/} iff $\#\pi = \#\th$, and $\pi(p_i) = p_j$ if and only if $\th(q_i) =q_j$. } \endproclaim \remark{Remark} Suppose that $\pi: P \to P$ is a self-map of a \fos\ and that $\#\pi = n$. Then there is a unique map $\th: \{1,2,\dots,n\} \to \{1,2,\dots,n\}$ which is equivalent to~$\pi$. Observe that the \Mg s of~$\pi$ and of~$\th$ are the same. Moreover, any self-map of a compact interval is \piwm\ if and only if it is \thwm. So we may assume, when convenient, that $P = \{1,2,\dots,n\}$. We will do this several times in later sections. \endremark \head 2. Horseshoes \endhead Recall that $f: I \to I$ has a {\it horseshoe\/} iff there exist subintervals $J$ and $K$ of~$I$, with at most one point in common, such that $f(J),f(K) \supseteq J \cup K$. Recall also that a continuous map with a horseshoe has periodic points of all periods. \proclaim{Lemma 2.1} {\sl Suppose that $\pi : P \to P$ is a self-map of a finite ordered set, and that $f : I \to I $ is continuous and \piwm. Then $f$ has a horseshoe if and only if there exist points $p_i < p_j < p_k$ in~$P$ such that $\pi(p_i),\pi(p_k) \le p_i$ and $\pi(p_j) \ge p_k$, or $\pi(p_i),\pi(p_k) \ge p_k$ and $\pi(p_j) \le p_i$.} \endproclaim \demo{Proof} The conditions are clearly sufficient for $f$ to have a horseshoe. For the converse, it suffices to show that one of the conditions holds if $f$ has a horseshoe. Let $Z$ denote the set of $\pi$@-points of~$f$. By \cite{BCop, Lemma~II.2}, we may assume that there exist points $a < b < c$ in~$I$ such that $$f(a)=f(c) = a \text{ and } f(b) = c,$$ $$f(x) > a \text{ for all}~x, a < x 0$, $f$ is nondecreasing on $[a,a+\epsilon]$ and there are no $\pi$@-points in $(z_i,a+\epsilon)$, that $f(z_i) \le z_i$. Similarly, $f(z_k) \le z_i$. It follows that $\pi(p_i),\pi(p_k) \le p_i$ and $\pi(p_j) \ge p_k$. \qed \enddemo \proclaim{Lemma 2.2} {\sl Suppose that $\pi : P \to P$ is a self-map of a finite ordered set, and that $f : I \to I $ is continuous and \piwm. Let $k \ge 1$. Then $f^k$ has a horseshoe if and only if there exist $\pi$@-points, $a < b < c$ of~$f$, such that $f^k[a,b], f^k[b,c] \supseteq [a,c]$.} \endproclaim \demo{Proof} One direction is trivial. Suppose then that $f^k$ has a horseshoe. Let $Z_\pi$ denote the set of $\pi$@-points of~$f$. As in the proof of Theorem~1.6, there is a self-map $\th :Q \to Q$ of a \fos, such that $f^k(Z_\th) \subseteq Z_\pi$ and $f^k$ is $\theta$@-weakly \mono. By Lemma~2.1, there are points $x < y < z$ in ~$Z_\th$ such that, without loss of generality, $f^k(x) \le x, f^k(z) \le x$ and $f^k(y) \ge z$. Hence $f^k(x) \le x, f^k(z) \le x$ and $f^k(y) \ge z$. In particular, $f^i(y) \ne f^i(x),f^i(z)$ for $0 \le i \le k$. Let $m$ be the smallest positive integer such that $f^m(y)$ is not between $f^m(x)$ and $f^m(z)$. Then $ 1 \le m \le k$. We may assume that $f^m(y) < f^m(x), f^m(z)$. Let $$v = \min\{f^{m-1}(x), f^{m-1}(z)\},$$ $$\text{and } w = \max\{f^{m-1}(x), f^{m-1}(z)\}.$$ Then $v < f^{m-1}(y) < w$ and $f^{m-1}[x,z] \supseteq [v,w]$. Let $b$ be a point in~$[v,w]$ at which $f$ attains its minimum value. This minimum is less than~$f(v)$ and~$f(w)$, so $\min f[v,w] = f(b)$, where $b$ is a turning point or in a turning interval. Since every turning interval contains a $\pi$@-point, we may assume that $b$ is a $\pi$-point. Now let $a$ be the largest $\pi$-point less than or equal to~$v$, and let $c$ be the smallest $\pi$-point greater than or equal to~$w$. Since $f^k[v,b], f^k[b,w] \supseteq [v,w]$ and $f^k(Z_\th) \subseteq Z_\pi$, it follows that $f^k[v,b], f^k[b,w] \supseteq [a,c]$. Thus $f^k[a,b], f^k[b,c] \supseteq [a,c]$. \qed \enddemo We now phrase Lemma 2.2 in terms of ~$\pi$ and its Markov graph. \proclaim{Definition}{\sl A directed graph, with ordered vertices, and arcs $\cdot \to \cdot$, {\it has a horseshoe\/} iff there are disjoint, nonempty collections $\Cal V_L $ and $\Cal V_R$, of vertices of the Markov graph of~$\pi$, such that $i < j$ for every $V_i \in \Cal V_L$ and every $V_j \in \Cal V_R$, and such that for every $V \in \Cal V_L \cup\Cal V_R$, there exist $V_i \in \Cal V_L$ and $V_j \in \Cal V_R$ and arcs from $V_i$ to~$V$ and from $V_j$ to ~$V$. } \endproclaim \proclaim{Definition}{\sl Let $D$ be a directed graph and let $k \ge 1$. The $k$@-{\it th power\/} of~$D$ is the directed graph whose vertices are the vertices of~$D$ (and with the same order if the vertices of~$D$ are ordered), and whose arcs are the paths of length~$k$ in~$D$.} \endproclaim \proclaim{Theorem 2.3} {\sl Suppose that $\pi : P \to P$ is a self-map of a finite ordered set, and that $f : I \to I $ is continuous and \piwm. Let $k \ge 1$. Then $f^k$ has a horseshoe if and only if the $k$@-th power of the Markov graph of~$\pi$ has a horseshoe. } \endproclaim \demo{Proof} Let $Z$ denote the set of $\pi$@-points of~$f$. Suppose that $f^k$ has a horseshoe. By Lemma~2.2, there are $\pi$@-points points $a < b < c$ such that $f^k[a,b], f^k[b,c] \supseteq [a,c]$. Let $\Cal V_L$ denote the set of vertices~$V_i$ in the Markov graph of~$\pi$ such that $a \le z_i < z_{i+1} \le b$, and let $\Cal V_R$ denote the set of vertices~$V_j$ in the Markov graph of~$\pi$ such that $b \le z_j< z_{j+1} \le c$. Then $\Cal V_L$ and~$\Cal V_R$ are well-defined, and satisfy the conditions of the definition. Conversely, suppose that $\Cal V_L$ and~$\Cal V_R$ are as in the definition. Let $i$ and~$j$ be least such that $V_i \in \Cal V_L$ and $V_j \in \Cal V_R$. Similarly, let $i'$ and~$j'$ be greatest such that $V_i' \in \Cal V_L$ and $V_j' \in \Cal V_R$. Then $[z_i,z_{i'+1}]$ and $[z_j,z_{j'+1}]$ exhibit a horseshoe for~$f^k$. \qed \enddemo \head 3. Reduction- and restriction-minimality \endhead In this section, we introduce an important property of \mcm s, {\it \rrmin ity}. Reduction-minimality is defined in terms of an even more important concept, {\it block structure}. Throughout this section, $\pi : P \to P = \{p_1 \pi(p_k)$. \proclaim{Lemma 3.9 } {\sl Suppose that $\pi: P \to P$ is \rrmin, and that the set of periods of~$\pi$ does not consist only of powers of~$2$. Then every point in ~$P$ is in the orbit of a turning point of ~$\pi$.} \endproclaim \demo{Proof} Let $\th$ be the restriction of~$\pi$ to~$Q$, where $Q$ is the set of points in ~$P$, each of which is in the orbit of at least one of the following. \newline$\bullet$ the largest point in $P$ \newline$\bullet$ the smallest point in $P$ \newline$\bullet$ a turning point of $\pi$ \newline$\bullet$ an endpoint of a maximal flat block \newline$\bullet$ an endpoint of a block in a maximal monotone cycle of blocks. By \cite{BCov, Theorem~2.6}, $L_\th$ and~$L_\pi$ are topologically conjugate; in particular they have the same set of periods. But then by Theorem~1.7, $\per(\th) = \per(\pi)$. Since $\pi$ is \rrmin, $\th = \pi$. Since $\pi$ has no flat blocks and no monotone cycles of blocks, it suffices to show that the smallest and largest points in~$P$, say $p$ and~$p'$, are in the orbits of turning points of ~$\pi$. If $\pi^{-1}(p) \subseteq \{p$\}, $\pi^{-1}(p') \subseteq \{p'\}$, or $\pi^{-1}\{p,p'\} \subseteq \{p,p'\}$, then there is a restriction of~$\pi$ with the same set of periods as~$\pi$. If none of these conditions hold, then $p$ and~$p'$ are in the orbits of turning points of~$\pi$. \qed \enddemo \head 4. Block structure over a simple cycle \endhead Recall that $f : I \to I$ has a horseshoe iff there are nondegenerate closed subintervals, $J$ and~$K$ of~$I$, with at most one point in common, such that $f(J), f(K) \supseteq J \cap K$. It is clear that if ~$f$ has a horseshoe, then so does any power of~$f$. \proclaim{Lemma 4.1} {\sl Suppose $f : I \to I$ is continuous and that there is no nondegenerate, closed subinterval $J \ne I$ of~$ I$, such that $f(J) \subseteq J$. \newline\noindent (1) If $f$ has more than one fixed point, then $f$ has a horseshoe. \newline\noindent (2) If some fixed point of~$f$ has more than one preimage, then $f^2$ has a horseshoe.} \endproclaim \demo{Proof} \Wlog\ $I = [0,1]$. \noindent (1) It suffices to find $a < b < c$ in~$[0,1]$, such that $f(a) = f(c) = a$ and $f(b) = c$ (or $f(a) = f(c) = c$ and $f(b) = a$). The set of non--fixed points of~$f$ is open and dense in~~$[0,1]$. Since $f$ has more than one fixed point, there is a connected component~$C$ of that set such that both endpoints $a < a'$ are fixed points. \Wlog\ $f(x) > x$ for every~$x$, $a < x < a'$. Then $a' \ne 1$. (Otherwise let $J = [a+\epsilon,1]$.) Let $c > a'$ be least such that $f(c) = a$. (If no such $c$ exists, again let $J = [a+\epsilon,1]$.) There exists~$b$, $a < b< c$, such that $f(b) = c$. (If no such $b$ exists, let $J = [a,c-\epsilon]$.) \noindent (2) We may assume that $f$ has exactly one fixed point~$a$, for otherwise by ~(1), $f$ has a horseshoe and then so does~$f^2$. Since $f$ is onto, $a \ne 0,1$. Suppose that $f(c) = a$, where without loss of generality, $c > a$. Let $u = \min \{f(x): a < x < c\}$. Then $u < a$. (If not, let $J = [a,c]$.) There exists $b', u \le b' < a$, such that $f(b') = c$. (If not, let $J = f[u,c]$.) There exists $b, a < b < c$, such that $f(b) = b'$. Then $f^2(a) = f^2(c) = a$ and $f^2(b) = c$. \qed \enddemo Recall that if $\#\pi = n$, then $L_\pi : [1,n] \to [1,n]$ is the canonical $\pi$@-linear map. \proclaim{Lemma 4.2} {\sl Suppose that $\pi : P \to P$ is \rrmin, $\#\pi = n$, and the set of periods of~$\pi$ does not consist only of powers of~$2$. If there is a nondegenerate, closed interval~$J \subseteq [1,n]$, and a positive integer~$t$, such that $J, L_{\pi}(J),\dots,L_{\pi}^{t-1}(J)$ are pairwise disjoint and $L_{\pi}^t(J) \subseteq J$, then $J \cup L_{\pi}(J) \cup \dots \cup L_{\pi}^{t-1}(J) \supseteq \{1,2,\dots,n\}$. \endproclaim \demo{Proof} Without loss of generality, $P =\{1,2,\dots,n\}$. Since $\pi$ has no flat blocks, the slope of~$L_{\pi}$ on any $\pi$@-interval ~$[i,i+1]$ has absolute value at least ~$1$. Let $J$ be an interval satisfying the conditions of the lemma. Suppose first that $J \cap P = \varnothing$. Then, for $i = 0,1,\dots,t-1$, $L_{\pi}^i(J) \cap P = \varnothing$. Therefore, $L_{\pi}^t$ is linear on ~$J$. Since $L_{\pi}^t(J) \subseteq J$ and the slope of ~$L_{\pi}^t$ on~$J$ has absolute value at least ~$1$, $L_{\pi}^t$ maps ~$J$ linearly onto~$J$. Therefore $L_{\pi}^{2t}$ is the identity on~$J$, and so $J$ is contained in a periodic (in the sense of \cite{BCov} - see Section~3) interval whose endpoints belong to~$P$. This contradicts Lemma~3.8. Therefore $J \cap P \ne \varnothing$. Next, suppose that $J \cap P$ contains exactly one point, say~$d$. Since $\pi$ has no flat blocks, each $L_{\pi}^i(J) \cap P$ contains exactly one point. Define a subinterval $K$ of~$J = [a,b]$, as follows. If $d = a$ or ~$b$, let $K = J$. Suppose that $a < d < b$. At least one of the following holds. \roster \item $L_{\pi}^t[a,d] \subseteq [a,d]$. \item $L_{\pi}^t[d,b] \subseteq [d,b]$. \item $L_{\pi}^t[a,d] \subseteq [d,b]$ and $L_{\pi}^t[d,b] \subseteq [a,d]$. \endroster If (1) holds, set $K= [a,d]$; otherwise set $K= [d,b]$. Then $L_{\pi}^{2t}(K) \subseteq K$, and for each $i = 0,1,\dots,2t-1$, $L_{\pi}^i(K)$ is contained in a unique $\pi$@-interval. As above, this leads to a condradiction of Lemma~3.8. Therefore $J \cap P$ contains at least two points. For each $i = 1,2,\dots,t$, let $B'_i = L_{\pi}^{i-1}(J) \cap P$. Each~$B'_i$ is a block containing at least two points, and $\pi(B'_i) \subseteq B'_{i+1}$ for $i = 1,2,\dots,t$, where $B'_{t+1} = B'_1$. It follows from Lemma~3.7 that $B'_1 \cup B'_2 \cup \dots \cup B'_t = P$. Therefore $J \cup L_{\pi}(J) \cup \dots \cup L_{\pi}^{t-1}(J) \supseteq P$. \qed \enddemo \remark{Remark} A cycle which is a double (defined in Section~3) of a simple cycle of length~$2^k$ (defined in Section~1) is a simple cycle of length~$2^{k+1}$. \endremark \proclaim{Theorem 4.3} {\sl Let $k \ge 0$. Suppose that $\pi: P \to P$ is a \rrmin\ self-map of a finite ordered set, such that the set of periods of~$\pi$ does not consist only of powers of~$2$, and such that the $2^{k}$@-th power of the Markov graph of~$\pi$ does not have a horseshoe. Then $\pi$ has a block structure over a simple cycle of length~$2^k$.} \endproclaim \demo{Proof} We prove, by induction on~$j$, that for every $j = 0,1,\dots,k$, $\pi$ has a block structure over a simple cycle of length~$2^j$. There is nothing to prove for $j = 0$. Suppose then that $0 \le j \le k-1$, and that $\pi$ has a block structure over a simple cycle~$\th$ of length~$2^j$. Let $B''_1,B''_2,\dots,B''_{2^j}$ be the blocks of this block structure, labelled so that $\pi(B''_i) \subseteq B''_{i+1}$ for $i = 1,2,\dots,2^j$, where $B''_{2^j + 1} = B''_1$. Since $\pi$ has no flat blocks and the set of periods of~$\pi$ does not consist only of powers of~$2$, each block contains at least two points of ~$P$. Suppose that $\#\pi = n$. \Wlog, $P = \{1,2, \dots ,n\}$. Let $L_\pi : [1,n] \to [1,n]$ be the canonical $\pi$@-linear map. For $i = 1,2,\dots,2^j$, let $J_i$ be the convex hull, in~$[1,n]$, of the block~$B''_i$, where $B''_i$ is as in the preceding paragraph, and let $g_i = L_{\pi}^{2^j}|_{J_i}$. Then $g_i $ maps~$J_i$ to itself. Since $j \le k-1$, $g_i^2$ does not have a horseshoe. Now, fix $i$, $1 \le i \le 2^j$. We claim that there is no nondegenerate, proper, closed subinterval ~$J$ of~$J_i$ such that $g_i(J) \subseteq J$. Suppose that~$J$ is such an interval. Then the intervals $J,L_{\pi}(J),\dots,L_{\pi}^{2^j -1}(J)$ are pairwise disjoint. So, by Lemma~4.2, $J \cup L_{\pi}(J) \cup \dots \cup L_{\pi}^{2^j -1}(J) \supseteq P$. Since the endpoints of~$J_i$ are in~$P$, it follows that $J = J_i$. This establishes the claim. By Lemma~4.1, $g_i$ has a unique fixed point~$w_i$, and $w_i$ is its own $g_i$@-preimage. We claim that every $L_{\pi}$@-periodic point not in $J_1 \cup J_2 \cup \dots \cup J_{2^j}$ has period a power of~$2$. If not, then by Lemma~1.2, the Markov graph of~$\pi$ has a \pcw\ of length not a power of~$2$ which passes through only gap vertices. By Lemma~3.1, the Markov graph of~$\th$ has a a \pcw\ of length not a power of~$2$. This contradicts the Remark immediately preceding Theorem~1.9. Since $L_{\pi}$ has a periodic point of period not a power of~$2$, $g_i$ has a periodic orbit~$Q$ with more than one point. There exist adjacent points $y < z$ in~$Q$, such that $g_i(y) > y$ and $g_i(z) < z$. Therefore $y < w_i < z$, $g_i(y) > w_i$, and $g_i(z) < w_i$. Since $w_i$ is its own $g_i$@-preimage, it follows that \smallpagebreak \noindent ($*$) $ g_i(x) > w_i$ for every $x \in J_i$ such that $x < w_i$, and $g_i(x) < w_i$ for every $x \in J_i$ such that $x > w_i$. \smallpagebreak Now, $\{w_1,w_2,\dots,w_{2^j}\}$ is a periodic orbit of~$L_\pi$. It follows from ~($*$) that if $x_1 \in J_1$ and $L_\pi(x_1) = w_2$, then $x_1 = w_1$. Therefore we have \smallpagebreak \noindent ($**$) $L_{\pi}^{-1}(w_1) \cap J_{2^j} = \{w_{2^j}\}$, and for $i \ne 1$, $L_{\pi}^{-1}(w_i) \cap J_{i-1} = \{w_{i-1}\}$. \smallpagebreak It also follows from~($*$) that none of the points~$w_i$ are turning points of ~$L_{\pi}$. Since $J_1 \cup J_2 \cup \dots \cup J_{t}$ contains all the turning points of~$L_\pi$, it follows from~($**$) that none of the points ~$w_i$ is in the orbit of a turning point of~$L_\pi$. Then, by Lemma~3.9, none of the points ~$w_i$ is in~$P$. This, together with~($*$) and the remark immediately preceding the statement of this theorem, implies that $\pi$ has a block structure over a simple cycle of length~$2^{j+1}$. \qed\enddemo \head 5. \s-largest period $3 \cdot 2^k$ \endhead \bigpagebreak This section contains the most surprizing, and technically most difficult to prove, results --- the characterizations of the \mcm s and the \mpm s for ``$\per(f) = \{t : t \sle 3 \cdot 2^k\}$.'' It is the only case for which the \mcm s and the \mpm s are not the same. \proclaim{Definition} {\sl Let $\pi : P \to P$ be a cyclic \perm\ of a \fos\ of cardinality $m \cdot 2^k$, where $m > 1$ is odd. $\pi$ is a {\it simple cycle\/} iff \newline\noindent (1) $\pi$ has a block structure over a simple cycle of length~$2^k$. \newline\noindent (2) $\pi$ is \mono\ on all blocks but one. \newline\noindent (3) For each block $B$, letting $p$ be the central point of~$B$ and $\th = \pi^{2^k}|_B$, either $$\th^{m-1}(p) < \th^{m-3}(p) < \dots < \th^2(p) < p < \th(p) < \dots < \th^{m-4}(p) < \th^{m-2}(p)$$ \qquad\qquad\qquad\qquad\qquad\qquad or $$\th^{m-1}(p) > \th^{m-3}(p) > \dots > \th^2(p) > p > \th(p) > \dots > \th^{m-4}(p) > \th^{m-2}(p).$$ } \endproclaim \proclaim{Lemma 5.1} {\sl Let $\pi : P \to P$ be a \rrmin\ map of a finite ordered set, such that $\per(\pi) = \{t : t \sle 3 \cdot 2^k\}$, and such that the $2^k$@-th power of the Markov graph of~$\pi$ does not have a horseshoe. If $ \#\pi \le 3\cdot2^k$, then $\pi$ is a simple cycle of length~$3\cdot2^k$.} \endproclaim \demo{Proof} \Wlog, $P = \{1,2,\dots,n\}$. By Theorem~4.3, $\pi$ has a block structure over a simple cycle of length~$2^k$. Let $B_1,B_2,\dots,B_{2^k}$ be the blocks of this structure, labelled so that $\pi(B_i) \subseteq B_{i+1}$ for $i = 1,2,\dots,2^k$, where $B_{2^k + 1} = B_1$. Let $C_i = [\min B_i, \max B_i]$ be the convex hull of~$B_i$ (in $[1,n]$). Since the set of periods of~$\pi$ does not consist only of powers of~$2$, at least one block contains more than one point. Since $\pi$ has no flat blocks, every block contains at least two points. If every block contained exactly two points, then, by Theorem~1.8, every period of~$\pi$ would be a power of~$2$. Therefore, one of the blocks contains at least three points. If one of the blocks contained exactly two points, then some block $B_i$ contains more than two points, while $B_{i+1}$ contains exactly two points. Now let $L_\pi: [1,n] \to [1,n]$ be the canonical $\pi$@-linear map. Since $\pi$ has no flat blocks, there are nonoverlapping subintervals ~$J'$ and $J''$ of~$C_i$, such that $L_\pi(J') = L_\pi(J'') = C_{i+1}$. But then $L_\pi^{2^k}$ has a horseshoe. Therefore each block contains at least three points, hence exactly three points, and $\#\pi = 3\cdot2^k$. Let $\Cal J$ be the set of $\pi$@-intervals contained in $C_1 \cup C_2 \cup \dots \cup C_{2^k}$, i.e., $\Cal J = \{[j,j+1]: V_j \text{ is a block vertex}\}$. Note that each ~$C_i$ contains exactly two intervals in ~$\Cal J$. If, for each interval $J$ in $\Cal J$, $L_\pi(J)$ contains only one interval in~$\Cal J$, then every $L_\pi^{2^k}|_{C_i}$ is \mono. This contradicts the fact that some $L_\pi^{2^k}|_{C_i}$ has a periodic point of period~$3$. Therefore, there is at least one interval $J_0$ in~$\Cal J$ such that $L_\pi(J_0)$ contains two intervals in~$ \Cal J$. By relabelling, we may assume that $J_0 \subseteq C_{2^k}$. Let $I_{{2^k},1} = J_0$, and let $I_{{2^k},2}$ be the other interval in~$ \Cal J$ which is a subset of ~$C_{2^k}$. Then $L_\pi(I_{{2^k},1}) = C_1$. Now, it follows from Lemma~3.7 that $L_\pi(C_i) = C_{i+1}$ for $i=1,2,\dots,2^k -1$. In particular, $L_\pi^{2^k}(I_{{2^k},1}) = C_{2^k}$. Since $L_\pi^{2^k}$ does not have a horseshoe, $L_\pi(I_{{2^k},2})$ is a proper subset of~$ C_1$. Denote the intervals in~$\Cal J$ which are contained in~$C_1$ by $I_{1,1}$ and $I_{1,2}$, where $L_\pi(I_{{2^k},2}) = I_{1,2}$. Similarly, for $i = 2,3, \dots, {2^k}-1$, denote the two members of ~$\Cal J$ which are contained in ~$C_i$ by~$I_{i,1}$ and ~$I_{i,2}$, where $L_\pi(I_{i-1,2}) = I_{i,2}$. Since $L_\pi^{2^k}$ has a point of period~$3$, we must have $L_\pi(I_{{2^k}-1,2}) \supseteq I_{{2^k},1}$. If \linebreak $L_\pi(I_{{2^k}-1,2}) \supseteq I_{{2^k},2}$ as well, then the intervals $I_{{2^k},1}$ and $I_{{2^k},2}$ would exhibit a horseshoe for~$L_\pi^{2^k}$. Thus $L_\pi(I_{{2^k}-1,2}) = I_{{2^k},1}$. If $L_\pi(I_{1,1}) \supseteq I_{2,2}$, then the intervals $I_{1,1}$ and $I_{1,2}$ would exhibit a horeshoe for~$L_\pi^{2^k}$. Thus $L_\pi(I_{1,1}) = I_{2,1}$. Similarly $L_\pi(I_{i,1}) = I_{i+1,1}$ for $i = 2,3,\dots,{2^k}-2$ and $L_\pi(I_{{2^k}-1,1}) = I_{{2^k},2}$. We have determined all the arcs emanating from block vertices in the Markov graph of~$\pi$. In particular, $\pi$ maps~$B_i$ monotonically onto~$B_{i+1}$ for $i = 1,2, \dots, {2^k}-1$. Furthermore, if $x$ is the point in~$B_1$ which is an endpoint of~$I_{1,1}$, but not an endpoint of~$I_{1,2}$; if $y$ is the common endpoint of ~$I_{1,1}$ and ~$I_{1,2}$; and if $z$ is the point in~$B_1$ which is an endpoint of~$I_{1,2}$, but not an endpoint of~$I_{1,1}$, then it is easy to check that $\pi^{2^k}(x) = y, \pi^{2^k}(y) = z$, and $ \pi^{2^k}(z) = x$. Therefore $\pi$ is a simple cycle. \qed \enddemo \proclaim{Theorem 5.2}{\sl The \mcm s for ``$\per(f) = \{t : t \sle 3 \cdot 2^k\}$ and $f^{2^k}$ does not have a horseshoe'' are the simple cycles of length~$3 \cdot2^k$.} \endproclaim \demo{Proof} First suppose that $\pi: P \to P$ is a simple cycle of length~$3 \cdot 2^k$. Then $\pi$ has a \bs\ over a \sc\ ~ $\th$ of length~$2^k$. Since the length of any \pcw\ in the \Mg\ of~$\th$ is a power of ~$2$, it follows from Lemma~3.1(2) that the length of any \pcw\ in the \Mg\ of~$\pi$ which passes through only gap vertices is also a power of~$2$. On the other hand, any \pcw\ in the \Mg\ of~$\pi$ which passes only through block vertices has length a multiple of~$2^k$. The \Mg\ of ~$\pi$ has a \pcw\ of length ~$3 \cdot 2^k$, and $3 \cdot 2^k$ is the \s-largest multiple of~$2^k$. By Theorem~1.8, the \s-largest period of~$\pi$ is~$3 \cdot 2^k$. Let $f$ be \conts\ and \piwm. The monotonicity condition on ~$\pi$ implies that the $2^k$@-th power of the \Mg\ of ~$\pi$ does not have a horseshoe. By Theorem~2.3, neither does ~$f^{2^k}$. Therefore $\pi$ is a combinatorial model for ``$\per(f) = \{t : t \sle 3 \cdot 2^k\}$ and $f^{2^k}$ does not have a horseshoe.'' To complete the proof, suppose that $\pi: P \to P$ is a \mcm\ for ``$\per(f) = \{t : t \sle 3 \cdot 2^k\}$ and $f^{2^k}$ does not have a horseshoe.'' Then, by the first part of the proof, $\#\pi \le 3 \cdot 2^k$, and by Theorem~ 3.3, $\pi$ is \rrmin. So, by Lemma~5.1, $\pi$ is a \sc\ of length ~$3 \cdot 2^k$. \qed \enddemo \proclaim{Theorem 5.3}{\sl The \mpm s for ``$\per(f) = \{t : t \sle 3 \cdot 2^k\}$'' are the \perm s of cardinality~$3 \cdot2^k$ which satisfy (1) and (2). \newline\noindent (1) $\pi$ has a \bs\ over a \sc\ of length~$2^k$, with each block having exactly three points. \newline\noindent (2) For any pair of adjacent points, $p_j$ and $p_{j+1}$, in the same block, $\pi^i(p_j)$ and $\pi^i(p_{j+1})$ are not adjacent points for some~$i$, $1 \le i \le 2^{k+1}$. } \endproclaim \demo{Proof} First, suppose that $\pi: P \to P$ is a \perm\ which satisfies (1) and (2). There is a block $B = \{p_j,p_{j+1},p_{j+2}\}$ such that the restriction of~$\pi$ to~$B$ is not \mono. Consider $V_j$ and $V_{j+1}$, the two block vertices associated with~$B$ in the \Mg\ of~$\pi$. \Wlog, there are arcs from ~$V_j$ to two distinct block vertices. Since $\pi$ maps blocks onto blocks, it follows that there are walks of length~$2^k$ from~$V_j$ to~$V_j$ and from ~$V_j$ to~$V_{j+1}$. It follows from (2) that there is a closed walk of length~$2^k$ from~$V_{j+1}$ to~$V_j$. By following, in succession, the walks from ~$V_j$ to~$V_j$, from ~$V_j$ to~$V_{j+1}$, and from ~$V_{j+1}$ to~$V_j$, we obtain a \pcw\ of length~$3 \cdot 2^k$. By Theorem~1.8, $3 \cdot 2^k \in \per(\pi)$. On the other hand, it follows from (1) that the length of any subcycle of~$\pi$ is a multiple of~$2^k$. Now suppose that $W$ is a \pcw. By Lemma~3.1(1), $W$ passes through only block vertices or through only gap vertices. In the first case, the length of~$W$ is a multiple of~$2^k$. In the second case, it follows from Lemma~3.1(2) and the remark immediately preceding Theorem~1.9, that the length of~$W$ is $2^j$ for some $j < k$. Therefore, the length of~$W$ is \s-less than or equal to~$3 \cdot 2^k$. Thus, by Theorem~1.8, $3 \cdot 2^k$ is the \s-largest period of~$\pi$, and so $\pi$ is a \perm\ model for ``$\per(f) = \{t : t \sle 3 \cdot 2^k\}$.'' To complete the proof, suppose that $\pi : P \to P$ is a \mpm\ for ``$\per(f) = \{t : t \sle 3 \cdot 2^k\}$.'' For notational convenience, we may assume that $P = \{1,2,\dots,n\}$, and consider the canonical $\pi$-linear map~$L_\pi : [1,n] \to [1,n]$. We may also assume that $k \ge 1$, as the case $k = 0$ is straightforward. By Theorem~3.3, $\pi$ is \rrmin. Since $3 \cdot 2^{k-1} \notin \per(\pi)$, the $2^{k-1}$@-st power of the \Mg\ of~$\pi$ does not have a horseshoe. Hence, by Theorem~4.3, $\pi$ has a \bs\ over a \sc\ of length~$2^{k-1}$. As in the proof of Theorem~4.3, let $B$ be one of the blocks, and let $C = [\min B,\max B]$ be its convex hull. Since $\pi$ maps blocks onto blocks, $L_\pi$ maps convex hulls of blocks onto convex hulls of blocks. Set $g = L_\pi^{2^{k-1}}|_C$. Then $g$ maps ~$C$ onto itself. We will show that ($*$) holds. \medpagebreak \noindent ($*$) There is a point $z \in C$, $z \notin B$, such that $g(p) > z$ for every $p \in B$ with $p < z$, and $g(p) < z$ for every $p \in B$ with $p > z$. \medpagebreak As in the proof of Theorem~4.3, $g$ has no proper, nondegenerate, invariant subinterval. Since $g$ does not have a horseshoe, by Lemma~4.1, it has a unique fixed point, call it~$z$. Since $g$ maps $C$ onto itself, $z$ is not an endpoint of~$C$. We first claim that $z$ is not a turning point of~$g$. Note that, since $\pi$ is \rrmin, $L_{\pi}$ and hence~$g$ have no flat intervals. If $z$ is a turning point of~$g$, let $Q$ be $B$ union the set of endpoints of maximal \mono\ pieces of~$g$. Let $a$ be the largest point in~$Q$ less than~$z$, and let $b$ be the smallest point in~$Q$ greater than~$z$. Then, since $g$ maps endpoints of maximal monotone pieces of ~$g$ into~$B$, $g(a),g(b) \in B$. Since the turning point $z$ is the unique fixed point of~$g$, either $g(a) < a$ or $g(b) > b$. Without loss of generality, assume the former. Then $g(x) < x$ for all $x \in C$ such that $x \le a$. But $g(a) < a$, so $g^2(a) < g(a)$. Continuing, we have $ \dots < g^3(a) < g^2(a) < g(a)$, which contradicts the fact that $g(a)$ is $g$@-periodic. Therefore $z$ is not a turning point of~$g$, and hence not a turning point of~$L_\pi$. Similarly no point in the $L_{\pi}$-orbit of ~$z$ is a turning point of~$L_{\pi}$. Since $\pi$ is a \perm, $z$ is not in the orbit of a turning point of ~$L_{\pi}$. Then by Lemma~3.9, $z \notin P$. Let $p \in B$. Then $p$ is $L_\pi$@-periodic and hence $g$@-periodic. Since $p \ne z$, and $\per(g)$ contains no odd number other than~$1$, it follows from \cite{ALM, Lemma~2.1.6} that there exists $z' = z'(p) \in C$, $z'$ not in the $g$@-orbit of~$p$, such that $g(p) > z'$ if $p < z'$, and $g(p) < z'$ if $p > z'$. Clearly $z'$ may be chosen to be a fixed point of ~$g$. Therefore we may choose $z'(p) = z$ for all $p \in B$ and ($*$) is estabished. It follows from ($*$) and the remark immediately preceding Theorem~4.3 that $\pi$ has a \bs\ over a \sc\ of length~$2^k$. Since $\pi$ is a \perm, the blocks all have the same number of points. If this number were one or two, then by Theorem~1.8, the \s-largest period of~$\pi$ would be ~$2^k$ or~$2^{k+1}$. Since this is not the case, every block contains three points, i.e., (1) holds. Finally, we show that (2) holds. Proceeding by contradiction, suppose that there is a pair of adjacent points, $p_j$ and $p_{j+1}$, in the same block, such that for every $i,\ 1 \le i \le 2^{k+1}$, $\pi^i(p_j)$ and $\pi^i(p_{j+1})$ are adjacent points. \Wlog, we may assume that the block which contains $p_j$ and $p_{j+1}$ is~$\{p_j,p_{j+1},p_{j+2}\}$. It follows from Lemma~3.7 that $\{\pi^{2^k}(p_j),\pi^{2^k}(p_{j+1})\} = \{p_{j+1},p_{j+2}\}$, and hence that $\{\pi^{2^k}(p_{j+1}),\pi^{2^k}(p_{j+2})\} = \{p_j,p_{j+1}\}$. Therefore, $\pi$ is \mono\ on every block, $\pi^{2^k}(p_j) = p_{j+2}$, $\pi^{2^k}(p_{j+1}) = p_{j+1}$, and $\pi^{2^k}(p_{j+2}) = p_j$. Then, by Theorem~1.8, the \s-largest period of~$\pi$ is ~$2^{k+1}$. This is a contradiction, and so (2) holds. \qed \enddemo It follows from Theorem 5.3 that every cyclic \perm\ which satisfies ~(1) is a \mpm\ for ``$\per(f) = \{t : t \sle 3 \cdot 2^k\}$.'' On the other hand, there are non-cyclic \mpm s. For example, the \perm\ $\left( \smallmatrix 1&2&3&4&5&6\\ 5&4&6&2&3&1 \endsmallmatrix \right)$ is a \mpm\ for ``$\per(f) = \{t : t \sle 6\}$.'' \proclaim{Theorem 5.4}{\sl The \mcm s for ``$\per(f) = \{t : t \sle 3 \cdot 2^k\},\ k \ge 1$'' are the self-maps $\pi$ of \fos s of cardinality ~$3 \cdot 2^{k-1} + 1$ which satisfy (1), (2), (3), and (4). \noindent (1) $\pi$ has a \bs\ over a \sc\ of length~$2^{k-1}$. \newline\noindent (2) There is a block $B$ with four points, and every other block has three points. \newline\noindent (3) $\pi$ is strictly \mono\ on every block other than ~$B$. \newline\noindent (4) $\pi^{2^{k-1}}|_B$ is equivalent to $\left( \smallmatrix 1&2&3&4\\ 3&4&3&1 \endsmallmatrix \right)$ or $\left( \smallmatrix 1&2&3&4\\ 4&2&1&2 \endsmallmatrix \right)$. } \endproclaim \demo{Proof} First, suppose that $\pi: P \to P$, $\#\pi = 3 \cdot 2^{k-1} + 1$, and $\pi$ satisfies (1), (2), (3), and (4). Let $P = \{p_1 < p_2 < \dots < p_{3\cdot2^{k-1}+1}\}$, and let the exceptional block be $B = \{p_m,p_{m+1},p_{m+2},p_{m+3}\}$. Let $V_m,V_{m+1},V_{m+2}$ be the corresponding block vertices in the \Mg\ of~$\pi$. Number the blocks $B_1 = B$, and the remaining blocks $B_2,B_3,\dots,B_{2^{k-1}}$, so that $\pi(B_i) \subseteq B_{i+1}$, where $B_{2^{k-1}+1} = B_1$. \Wlog, $\pi^{2^{k-1}}|_{B_1}$ is equivalent to $\left( \smallmatrix 1&2&3&4\\ 3&4&3&1 \endsmallmatrix \right)$. Then it follows from ~(3) that the endpoints of~$B_2$ are $\pi(p_{m+3})$ and $\pi(p_{m+1})$, and that $\pi(p_m) = \pi(p_{m+2})$ is the midpoint of~$B_2$. Moreover, $\pi$ maps the endpoints of~$B_{2^{k-1}}$ onto~$\{p_m,p_{m+3}\}$, and maps the midpoint of~$B_{2^{k-1}}$ to~$p_{m+2}$. It follows that in the \Mg\ of~$\pi$ there are walks of length~$2^{k-1}$ from~$V_m$ to~$V_{m+2}$, from~$V_{m+1}$ to~$V_{m+2}$, from~$V_{m+2}$ to~$V_m$, and from~$V_{m+2}$ to~$V_{m+1}$, and no other walks of length~$2^{k-1}$ between these vertices. Since by~(1), every \pcw\ which passes through only gap vertices has length a power of~$2$, it follows that the \s-largest length of a \pcw\ is~$3 \cdot 2^k$. As the only subcycle of~$\pi$ has length~$2^{k-1}$, it follows from Theorem~1.8 that $\per(\pi) = \{t : t \sle 3 \cdot 2^k\}$. To complete the proof, suppose that $\pi : P \to P$ is a \mcm\ for ``$\per(f) = \{t : t \sle 3 \cdot 2^k\}, \ k \ge 1$.'' By Theorem~3.3, $\pi$ is \rrmin. Also, since $3 \cdot 2^{k-1} \notin \per(\pi)$, the $2^{k-1}$@-st power of the \Mg\ of ~$\pi$ does not have a horseshoe. Hence, by Theorem~4.3, (1) holds. To show that (2), (3), and (4) hold, first consider the case $k \ge 2$. By Lemma~3.5, $\pi$ has no flat blocks. In particular, each block has at least two points. Suppose that some block has exactly two points, and let $V$ denote the corresponding block vertex in the \Mg\ of ~$\pi$. At least one block has more than two points, otherwise $\per(\pi)$ would consist only of powers of ~$2$. It follows from Lemma~3.7 that there are two distinct \pcw s of length~$2^{k-1}$ from~$V$ to itself. By Theorem~1.8, $3 \cdot 2^{k-1} \in \per(\pi)$. Since this is a contradiction, each block contains at least three points. By the first part of the proof, $\#\pi \le 3 \cdot 2^{k-1} + 1$. Since $k \ge 2$, there is a block~$B$ with exactly three points. Let $V'$ and $V''$ be the corresponding block vertices in the \Mg\ of ~$\pi$. It follows from Lemma~3.7 that there are walks of length~$2^{k-1}$ from~$V'$ to ~$V''$, and from~$V''$ to~$V'$. Since $3 \cdot 2^{k-1} \notin \per(\pi)$, it follows from Theorem~1.8 that \smallpagebreak \noindent($*$) there are no closed walks of length~$2^{k-1}$ from~$V'$ to itself, or from ~$V''$ to itself. \smallpagebreak In light of ($*$), and the fact that $\pi$ has no flat blocks, we see that $\pi$ cannot map the midpoint of~$B$ to an endpoint of another block. From this, and Lemma~3.7, we have \smallpagebreak \noindent($**$) $\pi|_B$ is strictly monotonic and maps the endpoints of~$B$ to the endpoints of another block. \smallpagebreak Since $3 \cdot 2^k \in \per(\pi)$, it follows from~($**$) and Theorem~1.8 that at least one block has more than three points. On the other hand, since $\pi$ is a minimal combinatorial model, it follows from the first part of the proof that $\#\pi \le 3 \cdot 2^{k-1} + 1$. Hence, there is exactly one block with four points, i.e., (2) holds. Since (3) follows from~($**$), it remains to prove ~(4). Number the blocks $B_1,B_2,\dots,B_{2^{k-1}}$, so that $B_1$ has four points, and $\pi(B_i) \subseteq B_{i+1}$, where $B_{2^{k-1}+1} = B_1$. It follows from~($*$) and Lemma~3.7 that $\pi$ maps adjacent points of~$B_1$ to adjacent points of~$B_2$. So $\pi$ maps one endpoint of~$B_1$ to an endpoint of~$B_2$, and the other endpoint of~$B_1$ to the midpoint of~$B_2$. Write $B_1 = \{a < b < c < d\}$. We may assume that $\pi(d)$ is an endpoint of~$B_2$. Write $B_2 = \{u,v,w\}$, where $w = \pi(d)$, and $u$ is the other endpoint of~$B_2$. Then, using Lemma~3.7, we have $\pi(a) = \pi(c) = v$, and $\pi(b) = u$. Write $B_{2^{k-1}} = \{x,y,z\}$, where $\pi^{2^{k-1}-2}(u) = x$, $\pi^{2^{k-1}-2}(v) = y$, and $\pi^{2^{k-1}-2}(w) = z$. By~($**$), $\pi\{x,z\} = \{a,d\}$. If $\pi(x) = a$ and hence $\pi(z) = d$, we obtain a contradiction to Lemma~3.7. Therefore, $\pi(x) = d$ and $\pi(z) = a$. Suppose that $\pi(y) = b$. If $V$ is the block vertex corresponding to the adjacent points $x$ and~$y$ in~$B_{2^{k-1}}$, there is a closed walk of length~$2^{k-1}$ from~$V$ to itself. This contradicts~($*$). Hence $\pi(y) = c$. Therefore $\pi^{2^{k-1}}(a) = c$, $\pi^{2^{k-1}}(b) = d$, $\pi^{2^{k-1}}(c) = c$, and $\pi^{2^{k-1}}(d) = a$, i.e., (4) holds. Finally, we consider the case $k=1$. It suffices to show only that (4) holds, i.e., that $\pi|_B$ is equivalent to $\left( \smallmatrix 1&2&3&4\\ 3&4&3&1 \endsmallmatrix \right)$ or $\left( \smallmatrix 1&2&3&4\\ 4&2&1&2 \endsmallmatrix \right)$. Since $\pi$ is a minimal combinatorial model, it follows from the first part of the proof that $\#\pi \le 4$. On the other hand, it is easy to see, using Theorem~1.8, that there are no combinatorial models for ``$\per(f) = \{t : t \sle 6\}$'' with fewer than four points. Therefore $\#\pi = 4$. Write $P = \{p_1 < p_2 < p_3 < p_4\}$. By Theorem~5.3, $\pi$ is not a \perm, and by Lemma~3.7, $p_1$ and $p_4$ are in the image of~$\pi$. So we may assume that $p_2$ is not in the image of~$\pi$. Now, by Lemma~3.5, $\pi$ has no flat blocks. So, if the image of~$\pi$ were $\{p_1,p_4\}$, the \Mg\ of~$\pi$ would have a horseshoe, implying that $3 \in \per(\pi)$. Therefore, the image of~$\pi$ is $\{p_1,p_3,p_4\}$. We claim that $\pi(p_1) \ne p_1$. If $\pi(p_1) = p_1$, then $\pi(p_2)$ is either $p_3$ or~$p_4$. First, suppose that $\pi(p_2) = p_3$. Since $p_1$ is in the orbit of a turning point of~$\pi$, either $\pi(p_3) = p_1$, or $\pi(p_3) = p_4$ and $\pi(p_4) = p_1$. In either case, there is a \pcw\ of length~$3$ in the \Mg\ of~$\pi$. This is a contradiction. By a similar argument, $\pi(p_2) = p_4$ leads to a contradiction. Therefore $\pi(p_1) \ne p_1$, i.e., $\pi(p_1) = p_3$ or~$p_4$. Arguments similar to the ones above show that $\pi(p_1) \ne p_4$. Therefore, $\pi(p_1) = p_3$. Now, if $\pi(p_2) = p_1$, then $V_1 \to V_1 \to V_2 \to V_1$ is a \pcw\ of length~$3$, where $V_1$ is the block vertex corresponding to $\{p_1,p_2\}$, and $V_2$ is the block vertex corresponding to $\{p_2,p_3\}$. Therefore, $\pi(p_2) = p_4$. It follows similarly that $\pi(p_3) = p_3$ and $\pi(p_4) = p_1$. \qed \enddemo \remark{Remark} The \mcm s for ``$\per(f) = \{t : t \sle 3\}$'' are the self-maps of \fos s which are equivalent to one of the following: $\left( \smallmatrix 1&2&3\\ 2&3&1 \endsmallmatrix \right)$, $\left( \smallmatrix 1&2&3\\ 3&1&2 \endsmallmatrix \right)$, $\left( \smallmatrix 1&2&3\\ 1&3&1 \endsmallmatrix \right)$, $\left( \smallmatrix 1&2&3\\ 3&1&3 \endsmallmatrix \right)$. \endremark \head 6. \s-largest period $r \cdot 2^k, r \ge 5$ \endhead \bigpagebreak In this section, we prove our last main result, Theorem~6.1, the characterization of the \mcm s for ``$\per(f) = \{t : t \sle r \cdot 2^k\}$'', $r$ odd, $r \ge 5$. The proof is entirely in terms of the Markov graph. \proclaim{Theorem 6.1}{\sl Suppose that $r \ge 5$ is odd. Then the \mcm s for ``$\per(f) = \{t : t \sle r \cdot 2^k\}$'' are the simple cycles of length $r \cdot 2^k$. } \endproclaim \proclaim{Corollary}{\sl Suppose that $r \ge 5$ is odd. Then the \mpm s for ``$\per(f) = \{t : t \sle r \cdot 2^k\}$'' are the simple cycles of length $r \cdot 2^k$. } \endproclaim \demo{Proof of Theorem} Suppose first that $\pi : P \to P$ is a simple cycle of length ~$r \cdot 2^k$. Then, by the following \cite{ALM, Corollary 2.11.2}, $\per(\pi) = \{t : t \sle r \cdot 2^k\}$. So to prove the theorem, it suffices to show that if $\pi : P \to P$ is a \mcm\ for $\per(f) = \{t : t \sle r \cdot 2^k\}$, then $\pi$ is a simple cycle of length $r \cdot 2^k$. Suppose then that $\pi : P \to P$ is a \mcm\ for $\per(f) = \{t : t \sle r \cdot 2^k\}$. It follows from the preceding paragraph that $\#\pi \le r \cdot 2^k$. By Theorem~3.3, $\pi$ is \rrmin. Since $3 \cdot 2^k$ is not a period of~$\pi$, and since a \conts\ self-map of a compact interval which has a horseshoe must have a periodic point of period~$3$, it follows from Theorem~2.3 that the $2^k$@-th power of the Markov graph of~$\pi$ does not have a horseshoe. Hence, by Theorem~4.3, $\pi$ has a block structure over a simple cycle of length~$2^k$. By Theorem 1.8, either $\pi$ is a cycle of length~$r \cdot 2^k$, or there is a \pcw\ of length~$r \cdot 2^k$ in the \Mg\ of $\pi$. In the first case, it follows from \cite{BCop, Theorem~VII.11} that $\pi$ is a simple cycle of length ~$r \cdot 2^k$. Hence we may assume that there is a \pcw\ $W$ of length~$r \cdot 2^k$ in the \Mg\ of $\pi$. In light of Theorem~1.8, we have the following: \smallpagebreak \noindent ($*$) There is no \pcw\ of length ~$s \cdot 2^k$, $1 < s< r$, in the \Mg\ of ~$\pi$. \smallpagebreak We claim that every block in the block structure contains exactly $r$ points. To prove the claim, it suffices to show that if a block $ B$ has at most $r$ points, then it has exactly $r$ points. Let $D_B$ be the subgraph of the $2^k$@-th power of the Markov graph of~$\pi$ induced by the block vertices associated with the block~$B$. As in the proof of Theorem~5.3, the walk~$W$ passes through only block vertices. So, from ~$W$ we obtain a closed walk~$W_B$ of length~$r$ in~$D_B$. If $W_B$ contained only one vertex, then the $2^k$@-th power of the \Mg\ of ~$\pi$ would have a horseshoe. So $W_B$ contains at least two vertices. On the other hand, since there are at most $r-1$~vertices in~$D_B$, $W_B$ passes through some vertex twice. It follows that $W_B$ is the concatentation of two shorter closed walks, one of which has odd length. However, it follows from~($*$) that if $s$ is odd and $1 < s < r$, then in~$D_B$, there is no closed walk of length~$s$ which passes through two distinct vertices. Thus $W_B$ is the concatenation of a closed walk of length one and a closed walk of length~$r-1$, i.e., $W_B$ is of the form $$J_1 \to J_1 \to J_2 \to \dots \to J_{r-1} \to J_1. $$ It now follows that $J_1,J_2,\dots,J_{r-1}$ are distinct --- otherwise there would be a closed walk of odd length $s$, $1 < s < r$, in~$D_B$ passing through two distinct vertices. In particular, there are at least $r-1$ distinct vertices in~$D_B$. Hence $B$ contains at least $r$ points, and the claim is proved. It follows from the preceding paragraph and ($*$) that the blocks may be numbered $B_1,B_2,\dots,B_{2^k }$, where $\pi(B_i) \subseteq B_{i+1}$ and $B_{2^k+1} = B_1$, in such a way that the closed walk~$W $ has the form $$J_{1,1} \to J_{2,1} \to \dots \to J_{2^k,1} \to $$ $$ J_{1,1} \to J_{2,1} \to \dots \to J_{2^k,1} \to $$ $$ J_{1,2} \to J_{2,2} \to \dots \to J_{2^k,2} \to $$ $$ \dots \to \cdots$$ $$ J_{1,r-2} \to J_{2,r-2} \to \dots \to J_{2^k,r-2} \to $$ $$ J_{1,r-1} \to J_{2,r-1} \to \dots \to J_{2^k,r-1} \to J_{1,1},$$ \noindent where for each $i = 1,2,\dots,2^k$, the distinct block vertices associated with the block~$B_i$ are $J_{i,1},J_{i,2},\dots,J_{i,r-1}$. Recall that, if $P = \{p_1 p_i$, otherwise the $2^k$@-th power of the \Mg\ of~$\pi$ would have a horseshoe. Since there is a walk of length~$2^k$ in the \Mg\ of~$\pi$ from~$J_{1,2}$ to~$J_{1,3}$, but no such walk from ~$J_{1,2}$ to $J_{1,4}, J_{1,5},\dots$ or~$J_{1,r-1}$, we have $J_{1,3} = V_{i+2}$ and $\pi^{2^k}(p_{i+2}) = p_{i+3}$. In the same way, it follows that $B_1 = \{p_i,p_{i+1},\dots,p_{i+r-1}\}$, $J_{1,s} = V_{i+s-1}$ for $s = 1,2,\dots,r-1$, and $\pi^{2^k}(p_j) = p_{j+1}$ for $j = i,i+1,\dots,i+r-2$. Since $\pi^{2^k}(p_{i+r-2}) = p_{i+r-1}$ and there is a walk of length~$2^k$ from~$J_{1,r-1} = V_{i+r-2}$ to $J_{1,1} = V_i$, it follows that there are walks of length~$2^k$ from~$J_{1,r-1}$ to each of the vertices $J_{1,1},J_{1,2},\dots,J_{1,r-1}$. In particular, there is a \pcw\ of length~$3\cdot2^k$ in the \Mg\ of~$\pi$. This establishes our claim that $\pi^{2^k}(p_i) = p_{i+2}$ and $\pi^{2^k}(p_{i+1}) = p_i$. We claim next that if $ k \ne 0$, then the arc $J_{1,2} \to J_{2,2}$ is the only arc in the \Mg\ of ~$\pi$ emanating from~$J_{1,2}$. If there were an arc from ~$J_{1,2}$ to~$ J_{2,1}$, then the $2^k$@-th power of the \Mg\ of~$\pi$ would have a horseshoe. If there were an arc from~$J_{1,2}$ to any of the vertices $J_{2,3},J_{2,3},\dots,J_{2,r-1}$, it would contradict~($*$). Similarly, there is only one arc emanating from each of the vertices $J_{2,2},J_{3,2},\dots,J_{2^k -1,2}$. Now, each of the maps $\pi, \pi^2,\dots,\pi^{2^k -1}$ is \mono\ on $\{p_i,p_{i+1},p_{i+2}\}$, $\pi^{2^k}(p_i) = p_{i+2}$, and $\pi^{2^k}(p_{i+1}) = p_i$. By~($*$), there cannot be a closed walk of length~$2^k$ from~$J_{1,2}$ to any of the vertices $J_{1,1},J_{1,4},J_{1,5},\dots,J_{1,r-1}$, so we must have $\pi^{2^k}(p_{i+2}) \allowmathbreak = p_{i-1}$. Similarly, we see that $\pi$ is \mono\ on every block except~$B_{2^k}$, $p_{i+1}$ is the central point of~$B_1$, and if $\th = \pi^{2^k}|_{B_1}$, then $$ \multline \th^{r-2}(p_{i+1}) < \th^{r-4}(p_{i+1}) < \dots < \th^3(p_{i+1}) < \th(p_{i+1})<\\ < p_{i+1} < \th^2(p_{i+1}) < \dots < \th^{r-3}(p_{i+1}) < \th^{r-1}(p_{i+1}). \endmultline$$ Finally, since there is a walk of length~$2^k$ from ~$J_{1,r-1}$ to~$J_{1,1}$, but by~($*$), no such walk from ~$J_{1,r-1}$ to~$J_{1,2}$, we must have $\th^r(p_{i+1}) = p_{i+1}$. Therefore, $\pi$ is a simple cycle of length~$r\cdot 2^k$. \qed \enddemo \head 7. Unimodal \mcm s \endhead Recall that a self-map $\pi$ of a \fos\ $\{p_1 < p_2 < \dots < p_n\}$ is {\it unimodal\/} iff for some~$m$, $1 \le m \le n$, $\pi$ is (not necessarily strictly) increasing on ~$\{1,2,\dots,m\}$ and (not necessarily strictly) decreasing on ~$\{m,m+1,\dots,n\}$. Note that unimodality is a property of the equivalence class of~$\pi$ (see the definition in Section~1), and that $\pi$ is unimodal if and only if every \piwm\ map is unimodal. For all the properties considered in this paper, except ``$\per(f) = \{t : t \sle 3 \cdot 2^k\}$,'' $k \ge 1$, the \mcm s are the simple cycles of the appropriate length. It is well-known that there is a unique unimodal simple cycle of every length. Using Theorem~5.4, it can be checked that there is a unique unimodal \mcm\ for ``$\per(f) = \{t : t \sle 3 \cdot 2^k\}$,'' $k \ge 1$. These may be constructed inductively, as follows. Let $\pi_1 = \left( \smallmatrix 1&2&3&4\\ 3&4&3&1 \endsmallmatrix \right)$. Assume that $k \ge 1$, and that $\pi_k$ is the unique unimodal \mcm\ for ``$\per(f) = \{t : t \sle 3 \cdot 2^k\}$.'' Let $\th_{k+1}$ be the ``unimodal \u Stefan square root'' of~$\pi_k$. (See \cite{BkhC} for how to take unimodal square roots of unimodal self-maps of \fos s.) Then $\#\theta_{k+1} = 3 \cdot 2^k + 2$, the turning point of~$ \theta_{k+1}$ is pre-periodic, but not periodic, and it has a unique pre-image under~$\theta_{k+1}$. The pre-image has no pre-images. Restricting $\theta_{k+1}$ to its domain with the pre-image deleted produces a unimodal map $\pi_{k+1}$ with $\#\pi_{k+1} = 3 \cdot 2^k + 1$ and $\per(\pi_{k+1}) = \{t : t \sle 3 \cdot 2^{k+1}\}$. By Theorem 5.4, $\pi_{k+1}$ is a \mcm. \Refs \widestnumber\key{BkhC} \ref \key ALM \by Ll. Alsed\`a, J. Llibre, and M. Misiurewicz \book Combinatorial dynamics and entropy in dimension one \publaddr River Edge NJ \publ World Scientific \yr 1993 \endref \ref \key B \by L. Block \paper Simple periodic orbits of mappings of the interval \jour Trans. Amer. Math. Soc. \vol 254 \yr 1979 \pages 391--398 \endref \ref \key BCop \by L. S. Block and W. A. Coppel \book Dynamics in one dimension \bookinfo Lecture Notes in Math. \vol 1513 \publ Springer-Verlag \publaddr Berlin and New York \yr 1992 \endref \ref \key BCov \by L. Block and E. M. Coven \paper Topological conjugacy and transitivity for a class of \pwm\ maps of the interval \jour Trans. Amer. Math. Soc. \vol 300 \yr 1987 \pages 297--306 \endref \ref \key BkhC \by A. M. Blokh and E. M. Coven \paper Sharkovski\u{\i} type of cycles \jour Bull. London Math. Soc. \vol 28 \yr 1996 \pages 417--424 \endref \ref \key MN \by M. Misiurewicz and Z. Nitecki \paper Combinatorial patterns for maps of the interval \jour Mem. Amer. Math. Soc. \vol 94 \issue 456 \yr 1991 \endref \endRefs \enddocument