\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<p_2<\dots<p_n\}$.
$p_k$ is a {\it turning point\/} of~$\pi$
iff
$k \ne 1,n$, and either
$\pi(p_k) <  \pi(p_{k-1}),\pi(p_{k+1})$
or $\pi(p_k) >  \pi(p_{k-1}),\pi(p_{k+1})$.}
\endproclaim





\proclaim{Definition}
{\sl Let $\pi : P \to P$, where $P =
\{p_1<p_2<\dots<p_n\}$.
The {\it canonical $\pi$@-linear map\/}
is $L_\pi : [1,n] \to [1,n]$, where
$Z_\pi = \{1,2,\dots,n\}$,
$L_\pi(i) = j$ if
$\pi(p_i) = p_j$, and $L_\pi$ is linear on each
$\pi$@-interval ~$[i,i+1]$.}
\endproclaim






\remark{Remark}
$p_k$ is a turning point of~$\pi$  if and only if
$k$ is a turning point of~$L_\pi$.
\endremark


\proclaim{Lemma 1.1}
{\sl Let $\pi : P \to P$, where $P = \{p_1 < p_2 < \dots <
p_n\}$. The following statements are equivalent.
\newline\noindent (1) There is an arc in the
Markov graph of~$\pi$ from ~$V_i$ to~$V_j$.
\newline\noindent (2) For some continuous
\piwm\ map~$f$
with $\pi$@-set $Z_\pi$,
$f[z_i,z_{i+1}] \supseteq
[z_j,z_{j+1}]$.
\newline\noindent (3) For every
continuous
      map~$f$
with $\pi$@-set $Z_\pi$,
$f[z_i,z_{i+1}] \supseteq [z_j,z_{j+1}]$.
\newline\noindent (4) For some continuous
\piwm\ map~$f$
with $\pi$@-set $Z_\pi$,
there exists $x \in (z_i,z_{i+1})$ such that
$f(x) \in (z_j,z_{j+1})$.
\newline\noindent (5) For every continuous
\piwm\ map~$f$
with $\pi$@-set $Z_\pi$,
there exists $x \in (z_i,z_{i+1})$ such that
$f(x) \in (z_j,z_{j+1})$.}
\endproclaim

\remark{Remark}
The condition
``$f[z_i,z_{i+1}] \supseteq [z_j,z_{j+1}]$''
is sometimes called ``$[z_i,z_{i+1}]$
$f$@-\text{covers } $[z_j,z_{j+1}]$.''
\endremark

\smallpagebreak

We use exponentiation of maps to denote iterated
composition.  Thus $\pi^2 = \pi \circ \pi$,
$f^2 = f \circ f$, etc\.
For  $f : I \to I$,
$x \in I$, and $ n \ge 1$,
we say that $x$ is {\it periodic\/},
or $f$@-{\it periodic},
of {\it period\/}~$n$
iff
$f^n(x) = x$, and $f^m(x) \ne x$ for $1 \le m < n$.
We let $\per(f)$ denote the set of $n \ge 1$ such
that there exists  $x \in I$ of period~$n$,
and call it the {\it set of periods\/} of~$f$.

A closed walk in a directed graph
is called {\it primitive\/}
iff it is not a shorter closed walk
traversed several times.
For example,
$V_1 \to V_1 \to V_2 \to V_1$
is primitive, whereas
$V_1 \to V_2 \to V_1 \to V_2 \to V_1$
is not.



Let $V_{i_0} \to V_{i_1} \to \dots \to V_{i_{t-1}} \to
V_{i_0}$ be a closed walk of length~$t$ in the Markov
graph of~$\pi$, and
let $f: I \to I$ be continuous and \piwm,
with $\pi$@-set $Z_\pi$.
A fixed point~$x$ of $f^t$  {\it follows the walk\/}
iff
$f^k(x) \in [z_{i_k},z_{i_k +1}]$
for $k = 0,1,\dots,t-1$.  Note
that $x$ need not have period~$t$.

\proclaim{Lemma 1.2}
{\sl Let  $\pi : P \to P$ be a self-map of a \fos,
and let $f: I \to I$ be continuous and
\piwm, with $\pi$@-set ~$Z_\pi$.
Suppose that $x \notin Z_\pi$ is periodic of
period~$n$.  Then $x$ follows a closed walk of
length~$n$ which is either primitive, or  a
primitive closed walk traversed twice.}
\endproclaim

\demo{Proof}
Since  no point of the orbit of~$x$ is in ~$Z_\pi$,
$x$ follows a unique closed walk  by Lemma~1.1.
Suppose that the walk is not primitive, say
$V_{i_0} \to V_{i_1} \to \dots \to V_{i_{t-1}} \to
V_{i_0}$, traversed
$m \ge 2$ times.
Then for $k = 0,1,\dots,t-1$,
$$\{ f^k(x), f^{k+t}(x),\dots, f^{k+(m-1)t}(x)\}
\subseteq [z_{i_k},z_{i_k + 1}].$$
Therefore $f$ is weakly monotone
on these finite sets, and hence
$f^t$ is weakly monotone on $\{ x, f^t(x),\dots,
f^{(m-1)t}(x)\}$. But this set is a periodic orbit of~
$f^t$.   Therefore
      $m = 2$.
\qed
\enddemo

\proclaim{Lemma 1.3}  {\sl Let  $\pi : P \to P$ be a
self-map of a \fos, and let $f: I \to I$ be continuous
and
\piwm.
      Suppose that the Markov graph of~$\pi$ contains a
\pcw\ of length~$n$. Then $f$ has a periodic point
of period~$n$ or ~$n/2$.}
\endproclaim

\demo{Proof}
Let $Z_\pi = \{z_i\}$ be a $\pi$@-set,
and let
$V_{i_0} \to V_{i_1} \to \dots \to V_{i_{n-1}} \to
V_{i_0}$ be a \pcw. By \cite{BCop,
Lemma~I.4} there is a fixed point~ $x$ of~$f^n$
which follows the walk.


Suppose that $x \in (z_{i_0},z_{i_0 + 1})$.  Then
$f^k(x) \in (z_{i_k},z_{i_k + 1})$ for
$0 \le k \le n-1$.  If the
period of~$x$ were less than~$n$, the walk would
not be
primitive.

Suppose that $x = z_{i_0}$ or~$z_{i_0 + 1}$.  Then
$[z_{i_1},z_{i_1 + 1}]$ is the unique $\pi$@-interval with one
endpoint $f(x)$ such that there is an arc from~$V_{i_0}$ to
$V_{i_1}$.  Similarly, for $k = 2,3,\dots,n-1$, $[z_{i_k},z_{i_k +
1}]$ is the unique $\pi$@-interval
      with one endpoint
$f^k(x)$
      such that there is an arc
from~$V_{i_{k-1}}$ to $V_{i_k}$.

Suppose that the period of~$x$   is ~  $m$.
If $V_{i_m} = V_{i_0}$, then $V_{i_m +1} = V_{i_1}$,
etc. Since the walk is primitive,  $m = n$.
If $V_{i_m} \ne V_{i_0}$, then  $[z_{i_m},z_{i_m + 1}]$
and~
$[z_{i_0},z_{i_0 + 1}]$ are the distinct
$\pi$@-intervals with   common
endpoint~$x$. Then
$V_{i_{2m}} = V_{i_0}$ and  $m = n/2$.
\qed
\enddemo



The
{\it \s\ order}, ${\shl}$, on the positive integers is
$$
\split
1\shl2\shl2^2\shl2^3\shl \dotsb \shl 2^2\cdot7 \shl 2^2\cdot5 \shl
2^2\cdot3 \shl \dotsb \\
\dotsb \shl 2\cdot7 \shl 2\cdot5 \shl
2\cdot3 \shl \dotsb
\shl7\shl 5 \shl 3.\\
\endsplit
$$
Formally, if $r$ and $s$ are odd, then $2^kr \shl
2^{\ell}s$ iff
(1) $k <\ell$ and $r=s=1$, or
(2) $r=1$ and $s > 1$, or
(3) $k=\ell$ and $1<s<r$, or
(4) $k > \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 <c,$$
$$ x < f(x)<c \text{ for all}~x,a<x<b.$$

Let $z_i$ be the largest $\pi$@-point less than or
equal to~$a$,
let $z_j$ be the smallest $\pi$@-point  greater than
or equal to~$b$,
and let  $z_k = f(z_j)$.
Then  $z_i \le a < b \le z_j < c \le z_k$.

If $z_i = a$, then $f(z_i) = z_i$.
If $z_i < a$, then
it follows from the fact that
for small $\epsilon > 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<p_2<\dots<p_n\}$ and
$\th : Q \to Q = \{q_1<q_2<\dots<q_m\}$
will denote self-maps of \fos s,
$n = \#\pi$ and $m=\#\th$.


\proclaim{Definition and Notation}{\sl
A {\it block\/} of~$P$ is a
subset~$B$ of consecutive members (possibly only one)
of~$P$.
For blocks $B$ and $B'$, write $B < B'$
iff
$b < b'$ for every $b \in B, b' \in B'$.}
\endproclaim



\proclaim{Definition}{\sl
A {\it block structure\/} for~$\pi$ is a
partition $\Cal B = \{B_1 < B_2<\dots<B_m\}$ of~$P$
into disjoint blocks such that if $b$ and~$b'$
belong to the same block, then so do $\pi(b)$
and~$\pi(b')$.  }
\endproclaim



\proclaim{Definition}{\sl
Let $\Cal B= \{B_1 < B_2<\dots<B_m\}$ be a block structure
for $\pi$.
The {\it reduction\/} of~$\pi$ corresponding to~$\Cal B$
is ~$\th : \{q_1 < q_ 2 < \dots <q_m\} \to \{q_1
< q_ 2 < \dots <q_m\}$, defined by
$\th(q_i) = q_j$  if $\pi(B_i) \subseteq
B_j$.}
\endproclaim

We will use some graph theory terminology.

\proclaim{Definition}{\sl
Let $D$ be a graph and let $\Cal V$ be a subset of the
vertices of~$D$.
The {\it subgraph of $D$ induced by~$\Cal V$\/}
is the graph whose set of vertices is ~$\Cal V$,
and whose set of arcs is the set of arcs in~ $D$ from
vertices  in~$\Cal V$ to vertices
in~$\Cal V$.}
\endproclaim

\proclaim{Definition}{\sl
Let $\Cal B$ be a block structure for $\pi$.
The vertex $V_k$ in the Markov
graph of~$\pi$ is a  {\it gap vertex\/} if
$p_k$ and~$p_{k+1}$
are in different blocks, and a {\it block vertex\/}
if  they are in the same block.}
\endproclaim

\proclaim{Lemma 3.1}
{\sl Suppose that $\Cal B$ is a block structure for~$\pi$,
and that ~$\th$ is the corresponding reduction.
\newline (1) Every closed walk in the Markov graph
of~$\pi$ passes through only block vertices or
through only gap vertices.
\newline (2) \cite{MN, Theorem~4.1} The Markov graph of~$\th$ is
isomorphic, via an
increasing map of the vertices, to the subgraph of the
Markov graph of~$\pi$ induced by the gap
vertices.}
\endproclaim

\demo{Proof}
(1) follows from the fact that there are no arcs from
block vertices to gap vertices.
\qed\enddemo

\proclaim{Definition}{\sl
$\th : Q \to Q$ is a {\it restriction\/} of
$\pi : P \to P$
iff
$Q \subseteq P$ and $\th = \pi|_Q$.}
\endproclaim

\proclaim{Lemma 3.2}
{\sl Suppose that $\th$ is a reduction of or a
restriction of~$\pi$.
\newline (1) If $\pi$ is a \perm, then so is~$\th$.
\newline (2)
If the $r$-th power of the Markov graph of~ $\th$
has a horseshoe, then so does
the $r$-th power of the Markov graph of~ $\pi$.
}
\endproclaim

\demo{Proof}
(1) By \cite{MN, Remark 3.2}, a reduction of a \perm\ is
a \perm.  It is obvious that a restriction of a \perm\
is a \perm.


(2) If $\th$ is a reduction of~$\pi$
      and
the $r$-th power of the Markov graph of~ $\th$
has a horseshoe,
      then by
Lemma~3.1, so does
the $r$-th power of the Markov graph of~ $\pi$.

Suppose  that $\th: Q \to Q$ is a restriction of
~$\pi : P \to P$, and that
the $r$-th power of the Markov graph of~ $\th$
has a horseshoe.
Let $f$ be continuous, \piwm, and,  without loss of
generality, the set of $\pi$@-points of~$f$
is~$P$.  Similarly, let $g$ be continuous, \thwm,
and  the set of
$\th$@-points of~$g$ is~$Q$.
Since
the $r$@-th power of the Markov graph of~ $\th$
has a horseshoe,
it follows from Theorem~2.3 that
$g^r$ has a horseshoe.
By Lemma~2.2, there are $\th$@-points
$a < b < c$, such that
$g^r[a,b],g^r[b,c] \supseteq [a,c]$.
Since $Q \subseteq P$, $a,b$, and $c$ are
$\pi$@-points. But $f(J) \supseteq g(J)$ for every
interval~$J$ whose endpoints are
$\th$@-points, and hence $f^r(J) \supseteq g^r(J)$
for every such interval.
Therefore $f^r[a,b],f^r[b,c] \supseteq [a,c]$.
By Theorem ~2.3,
the $r$-th power of the Markov graph of~ $\pi$
has a horseshoe.
\qed
\enddemo






\proclaim{Definition}
{\sl $\pi$ is {\it \rrmin\/}
iff
      there is
no proper reduction of~$\pi$   with the same set of periods
as~$\pi$ and there is no proper restriction of~$\pi$   with
the same set of periods as~$\pi$.}
\endproclaim




The  following theorem is immediate from
Lemma~3.2.




\proclaim{Theorem 3.3}{\sl
Suppose that $\pi$ is a \mcm\ or a \mpm\ for either of the
following properties.
\newline
(1) $\per(f) = \{t : t \sle s\},\ s \ge 1$.
\newline
(2) $\per(f) = \{t : t \sle 3 \cdot 2^k\},\ k \ge
0$, and $f^{2^k}$ does not have a horseshoe.

Then $\pi$ is \rrmin.}
\endproclaim

In the remainder of this section, we establish several
properties of \rrmin\ maps.  These
properties will be needed in the next section.



\proclaim{Definition}
{\sl $f : I \to I$ {\it exhibits\/}
$\pi$   iff
there exist $x_1 < x_2 < \dots <
x_n$ in~$I$ such that if $\pi(p_i) = p_j$, then
$f(x_i) = x_j$.}
\endproclaim

\remark{Remark}
Every \piwm\ map exhibits $\pi$.
\endremark

\proclaim{Definition}
{\sl
A block $B$ of $P$
is {\it flat\/}
iff
    $B$ contains  at least two
points, and $\pi$ is
constant on~$B$.}
\endproclaim


\proclaim{Lemma 3.4}
{\sl If $\th$ is a reduction of or a restriction
of~$\pi$,
then $\per(\th) \subseteq \per(\pi)$.}
\endproclaim

\demo{Proof}
(1) $\th$ is a reduction of~$\pi$.

By Lemma~3.1, if the  Markov graph of~$\th$ has a
\pcw, then the Markov graph of~$\pi$ has a \pcw\ of
the same length.

Suppose that $\th$ has a subcycle
$q_{i_1} \to q_{i_2} \to \dots \to q_{i_k} \to q_{i_1}$
      of
length~$k$.
Let $B_{i_1}, B_{i_2}, \dots, B_{i_k}$
be the corresponding blocks of $\pi$@-points.
Since the $q$'s are distinct, these blocks are pairwise
disjoint. Let $f$ be continuous and \piwm, with
$\pi$@-set~$Z$.  Define closed intervals
$J_{i_1}, J_{i_2}, \dots, J_{i_k}$ by
$$J_{i_1} = [\min \{z_r \in Z :
        p_r \in B_{i_1}\},
        \max \{z_r \in Z : p_r \in B_{i_1}\}],
                 \text{etc}.$$
These intervals are pairwise disjoint,
and some may be degenerate.
$f^k(J_{i_1}) \subseteq J_{i_1}$,
and $f^j(J_{i_1}) \cap J_{i_1} = \varnothing$
for $1 \le j \le k-1$.
Therefore, $k \in \per(f) = \per(\pi)$.



By Theorem 1.8, $\per(\th) \subseteq \per(\pi)$.

\smallpagebreak

\noindent (2) $\th$ is a restriction of~$\pi$.

We  show that if $f$ is continuous and
exhibits~$\th$, then $\per(\th) \subseteq \per(f)$.
Then, since $\th$ is a restriction of~$\pi$,
any continuous, \piwm\ map exhibits~$\th$.
By \cite{MN, Corollary~1.15}, there is a
continuous, \thwm\ map $f_\th$, such that
for every map ~$\eta$ of a \fos\ which has no flat
blocks,
if  $f_\th$ exhibits~$\eta$, then any continuous~$f$
which exhibits ~$\th$ also exhibits~$\eta$.
So let $k \in \per(\th) = \per(f_\th)$,
and let $f$ be a continuous map which exhibits~$\th$.
There is a cyclic permutation~$\eta$ of a
\fos\ containing~$k$ points which is
exhibited by~$f_\th$.
Since permutations have no flat blocks, $f$ also
exhibits~$\eta$.  Thus $k \in \per(f)$.
\qed
\enddemo





We now  derive the desired properties of \rrmin\
maps.
Some of these properties hold only  for
maps whose  set of periods
does not consist only of powers of~$2$.




We will show that a \rrmin\ map
\newline\noindent $\bullet$ has no flat
blocks,
\newline\noindent $\bullet$ is not a double,
\newline\noindent $\bullet$ has no proper
cycle of blocks,
\newline\noindent $\bullet$ has no monotone
cycle of blocks,
\newline\noindent $\bullet$ has every point
in the orbit of a turning point.




\proclaim{Lemma 3.5 }
{\sl A \rrmin\ map
      has no flat
blocks.}
\endproclaim

\demo{Proof}
Suppose that $\pi : P \to P$ is \rrmin, but that
$\pi(p_k) = \pi(p_{k+1})$.
Define a block structure
      $\Cal B = \{B_1<B_2<\dots<B_{n-1}\}$,
by $B_i = \{p_i\}$, $i = 1,2,\dots, k-1$,
$B_k = \{p_k,p_{k+1}\}$, and
$B_i = \{p_{i+1}\}$, $i = k+1,k+2,\dots, n-1$.
Let $m = n-1$ and
let ~$\th$ be the corresponding proper reduction
of~$\pi$.

        The Markov graph of
~$\th$ is  isomorphic, via the obvious
      map,
to the  subgraph of the  Markov graph of~$\pi$
induced by the vertices
$V_i, i \ne k$.  Since no subcycles of~$\pi$  pass
through both $p_k$ and~$p_{k+1}$, and  no arcs in
the  Markov graph of~$\pi$ have initial vertex~$V_k$, it
follows from Theorem~1.8 that
$\pi$ and $\th$
have the same set of periods.

Therefore, $\pi$ has no flat  blocks.
\qed
\enddemo


\proclaim{Definition}
{\sl
$\pi : P \to P$ is a {\it double\/}
of~$\th: Q \to Q$
iff
$n = 2m$, and
$\pi\{p_{2i-1},p_{2i}\} = \{p_{2j-1},p_{2j}\}$
if $\th(q_i) = q_j$.}
\endproclaim

\proclaim{Lemma 3.6 }
{\sl  A \rrmin\
map~$\pi$
      such that the set of periods of~$\pi$
      does not consist only of powers of~$2$
      is not a double.}
\endproclaim

\demo{Proof}
Suppose that
$\pi$ is \rrmin, and
the set of periods of~$\pi$
      does not consist only of powers of~$2$,
but that $\pi$ is a double of~$\th$.
      Since
$\th$ is a proper reduction of~$\pi$, it suffices, by
Lemma~3.4, to show that $\per(\pi) \subseteq \per(\th)$.
To do this, it suffices to show that the \s-largest
period~$s$ of~$\pi$ is also a period of~$\th$.
       By Theorem~1.8,
$\pi$ has a subcycle of length~$s$, or
there is a \pcw\ of length~$s$ in the Markov graph
of~$\pi$.

In the first case, $\th$ has a subcycle of
length~$s$ or of
length~$s/2$.  Since $s$ is not a power
of~$2$, $s/2$ is \s-greater than~$s$.  So by
\s's Theorem,
$s$ is a period of~$\th$.

In the second case, if
      the \pcw\  passes through only block vertices,
then $\th$ has a subcycle of   length~$s$.  If the
subcycle passes through only gap vertices,  then  by
Lemma~3.1(2), the Markov graph of~$\th$ contains   a
\pcw\  of length~$s$.
By Theorem~1.8, $s$ is a period of~$\th$.
\qed
\enddemo





\proclaim{Lemma 3.7}
{\sl
Suppose that $\pi : P \to P$ is  \rrmin, and that
$\{B_1,B_2,\dots,B_k\}$ is a collection
of disjoint blocks, each containing at least two
points,  such that
$\pi(B_i) \subseteq B_{i+1}$, $i = 1,2,\dots, k$,
where $B_{k+1} = B_1$.
Then $B_1 \cup B_2 \cup \dots \cup B_k = P$.}
\endproclaim

\demo{Proof}
If there is such a collection of blocks
whose union is not all of~$P$,
let $\Cal C$ be the block structure for~$\pi$,
where the blocks  in ~$\Cal C$ are
$B_1,B_2,\dots,B_k$ and the singleton subsets of
$P \smallsetminus (B_1 \cup B_2 \cup \dots \cup B_k)$.
      Let
$\th$ be the proper reduction of~$\pi$ determined by ~$\Cal
C$, and let
$\eta$ be the proper restriction of~$\pi$ to
$B_1 \cup B_2 \cup \dots \cup B_k$.
We show that $\per(\pi)
= \per(\th)$ or~$\per(\eta)$. To do this, it suffices, by
Lemma~3.4, to show that
$\per(\pi) \subseteq \per(\th)$ or
~$\per(\pi) \subseteq \per(\eta)$.
As in the proof of  Lemma~3.5, we show
that the
\s-largest period $s$ of~$\pi$ is also a period of~$\th$
or of~$\eta$.  By Theorem ~1.8, $\pi$ has a
subcycle of length~$s$, or there is a \pcw\ of
length~$s$ in the Markov graph of~$\pi$.

Suppose that $\pi$ has a subcycle of length~$s$.
This cycle is either entirely contained in
$B_1 \cup B_2 \cup \dots \cup B_k$ or is disjoint
from it.  In the first case, $\eta$ has a subcycle of
length~$s$; in the second case, $\th$ does.

Suppose that there is a \pcw\ of
length~$s$ in the Markov graph of~$\pi$.
There are no arcs from block vertices to gap vertices,
and the Markov graph of~$\th$ is isomorphic to the
subgraph
of the Markov graph of~$\pi$ induced by
the gap vertices.
The subgraph of the Markov graph of~$\pi$
induced by the block vertices is isomorphic
to the corresponding induced subgraph of the Markov
graph of~$\eta$.
Therefore,
      the Markov graph of ~$\th$ or
the Markov graph of ~$\eta$ contains a \pcw\
of length~$s$.
\qed
\enddemo










\proclaim{Lemma 3.8 }
{\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 there is no collection
$\{B_1,B_2,\dots,B_k\}$  of disjoint blocks,
each containing at least two points,  such that $\pi$ maps
$B_i$ monotonically onto~$B_{i+1}$, $i = 1,2,\dots,
k$,  where $B_{k+1} = B_1$.
\endproclaim

\demo{Proof}
If there is such a collection, then by Lemma~3.7,
$B_1 \cup B_2 \cup \dots \cup B_k = P$. Also, $\pi$ maps the
union of the endpoints of the blocks
onto itself.
      Let $\th$ be the
restriction of~$\pi$ to this set.
By  Lemma~3.6, $\pi$ is not a double,
so $\th$ is a proper restriction of~$\pi$.
We show that $\per(\th) = \per(\pi)$.

By Lemma~3.4, $\per(\th) \subseteq \per(\pi)$.
To show the opposite containment, let~$s$
be the \s-largest period of~$\pi$.
We show that $s$ is a period of~$\th$.

First suppose that $s = k$ or~$2k$.
Then, as in the proof of Lemma~3.4,
$k \in \per(\th)$, and since~$s$ is not a power of~$2$,
$2k$ is \s-less than or equal to~$k$, and hence $2k
\in
\per(\th)$.

Next suppose that $s \ne k$ or~$2k$.
Since every subcycle of~$\pi$ has length~$k$
or~$2k$, by Theorem~1.8, the Markov graph of~$\pi$
has a \pcw\ of length~$s$.
Every \pcw\ which passes through only block  vertices
       has length~$k$ or~$2k$.
Therefore, this walk passes  through only gap vertices.
Since
$\th$ and~$\pi$ have
block structures with a common reduction,
by Lemma~3.1, the subgraphs of the
Markov graphs of~$\th$ and of~$\pi$ induced by
the respective gap vertices are isomorphic.
       Therefore, the
Markov graph of~$\th$ has a \pcw\ of length~$s$.
By Theorem~1.8, $s \in \per(\th)$.
\qed
\enddemo


Recall that $L_\pi :
[1,n] \to [1,n]$ is the canonical $\pi$@-linear map.
In \cite{BCov}, an interval~$J$
with endpoints in~$P$
is called  periodic
iff
there is a positive integer~$t$ such that
$L_\pi^t$ is the identity on~$J$.
It follows from \cite{BCov, Lemmas~2.3 and~2.4}
that
$\{p_i,p_{i+1},\dots,p_{i+k}\}$
is in a
monotone cycle of blocks if and only if $[i,i+k]$ is a
      periodic interval.

Recall that $p_k$ is a  {\it turning point\/}
of $\pi$
iff
$k \ne 1,n$, and either
$\pi(p_{k-1}),\pi(p_{k+1}) < \pi(p_k)$ or
$\pi(p_{k-1}),\pi(p_{k+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_2<\dots<p_{r\cdot2^k}\}$,
then the vertices $V_i$ of the \Mg\ of~$\pi$
are labelled so that
$V_i \to V_j$
if and only if
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$.


Using ($*$), we have  that  arcs in
~$W$ are the only arcs in the \Mg\ of
$\pi$ emanating from
$J_{1,1},J_{2,1},\dots,J_{2^k,1}$.
In particular,
$\{J_{1,1},J_{1,2}\} = \{V_i,V_{i+1}\}$
for some~$i$.
We may assume that
$J_{1,1} = V_i$ and
$J_{1,2} = V_{i+1}$.
It follows that
$\pi^{2^k}\{p_i,p_{i+1}\} = \{p_i,p_{i+2}\}$.

We claim that $\pi^{2^k}(p_i) = p_{i+2}$ and $\pi^{2^k}(p_{i+1}) =
p_i$. Suppose not, i.e., $\pi^{2^k}(p_i) = p_i$ and
$\pi^{2^k}(p_{i+1}) = p_{i+2}$. Then  $\pi^{2^k}(p_{i+2}) > 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
