%t\documentclass[trans]{beamer}
\documentclass{beamer}
\usepackage{beamerthemesplit}
\setbeamertemplate{navigation symbols}{} 

\usepackage{verbatim}

\usepackage[all,color]{xy}

\useoutertheme{infolines} 

\input{nielsenmacros}

\newcommand{\fpause}{\pause\vfill}

\title[Dynamics of random selfmaps]{Dynamics of random selfmaps of surfaces with boundary and graphs}
\author[Staecker]{P. Christopher Staecker (with Seung Won Kim)}
\institute[Fairfield U.]{Fairfield University, Fairfield CT}
\date[]{2011 Joint Meetings}

\newcommand{\aside}{\textcolor{red}}

\begin{document}
\frame{\titlepage}

\frame{Here's the main result:
\begin{thm}
``Almost all'' maps on surfaces with boundary have periodic points of every period, \pause and the number of periodic points with period $k$ grows exponentially in $k$, \pause and the exponential growth rate is as high as you want, \pause and the topological entropy is as high as you want.
\end{thm}

\fpause

All methods are homotopy invariant for the maps, and homotopy-type invariant for the space. \pause So the results hold for surfaces with boundary, graphs, etc.

\fpause

``Almost all maps'' is measured according to homotopy classes by asymptotic density.
}

\frame{
The main tool is Nielsen theory, which can keep track of a fixed point set as it changes throughout a homotopy. 

\fpause

The \emph{Nielsen number} $N(f)$ of a selfmap $f:X \to X$ is a lower bound for the number of fixed points of all maps in the homotopy class of $X$. 

\fpause

Our theorem really is that for ``almost all'' maps $f$, the sequence $\{N(f^n)\}$ is nonzero and grows exponentially in $n$.
}


\frame{
We measure ``almost all'' by \emph{asymptotic density} from combinatorial group theory. 
\fpause
Since everything is homotopy invariant, we only need to consider the induced homomorphisms on $\pi_1(X)$. \pause This is a free group, with a word length.

\fpause

We can measure the ``length'' of a homomorphism in terms of the lengths of the images of the generators.


\fpause

There are only finitely many homomorphisms of each length.
}

\frame{ 
For a set of homomorphisms $S$ we can discuss:
\[ \onslide<3->{D(S) = }\onslide<2->{\lim_{k\to\infty}} \text{proportion of all length $k$ homoms which lie in $S$} \]

\pause \pause\pause
So $D(S)$ is an asymptotic measure of the proportion of all homomorphisms which are in $S$. 

\fpause
Informally $D(S)$ is ``the probability that a randomly chosen homomorphism lies in $S$''.

\fpause
Imagine that your ``randomly chosen homomorphism'' will always be very long.
}

\frame{
So when I say ``almost all maps have property $\mathcal P$'' or ``a random map has $\mathcal P$ with probability 1'' I mean that $D(S) = 1$ for the set of homotopy classes of maps with $\mathcal P$.
}

\frame{
Let's convince you it's true first. (With pictures.)

\fpause

Let $X$ be a bouquet of 2 circles, \pause and let $f$ be specified by its induced homomorphism on the fundamental group.

\fpause

Here, $\pi_1(X) = \langle a, b\rangle$ is a free group on two generators, and $f_\# :\pi_1(X) \to \pi_1(X)$ looks something like:
\[ f_\#: \begin{array}{rcl}
a &\mapsto & abab^2 \\
b &\mapsto & b^2a^{-1}ba^3 \end{array}
\]

}

\frame{
\[ f_\#: \begin{array}{rcl}
a &\mapsto & baba^2 \\
b &\mapsto & a^2b^{-1}ab^3 \end{array}
\]

I imagine this map like this picture ($a$ on the right, $b$ on the left):
\only<1>{
\[ \includegraphics[scale=.25]{bigmapdiag.jpg} \]
}
\only<2->{
\[ \includegraphics[scale=.25]{bigmapcircled.jpg} \]
we can see the fixed points.}
}

\frame{
\[ \includegraphics[scale=.25]{bigmapcircled.jpg} \]
We get a fixed point every time $c^{\pm 1}$ appears inside the word $f(c)$. 

\fpause

How common is this for a ``random'' map $f$?
}

\frame{

\emph{Very} common! 

\fpause

This much is intuitively clear:
\begin{thm}
For any $r$, almost all maps have at least $r$ fixed points.
\end{thm}

\fpause

Strange things could happen when you iterate though. Letters giving fixed points could cancel after iteration, perhaps resulting in fewer fixed points for $f^2$ than for $f$. 
}

\frame{
Wagner ('99) and R.~F.~Brown discussed this \emph{remnant} condition: 
\fpause
For a homomorphism $f_\#$ on the group $\langle a_1, \dots a_n \rangle$, we say $f_\#$ \emph{has remnant} when there are subwords of each $f_\#(a_i)$ which never cancel in any product like 
\[ f_\#(b_k)^{\pm 1} f_\#(a_i) f_\#(c_k)^{\pm 1} \]

\fpause

So this map has remnant:
\[ f_\#: \begin{array}{rcl}
a &\mapsto &\underline{ab^2a}b^{-1}, \\
b &\mapsto &b\underline{ab^{-1}ab}.\end{array} \]

\fpause
When we iterate a map with remnant, it \emph{grows}! \pause The remnant subwords never cancel, and so just keep building up.
}

\frame{
Brown showed that almost all maps have remnant. 

\fpause

We show a stronger property:
\begin{lem}
For any $k$, almost all $f_\#$ have remnant subwords which each contain at least $k$ occurrences of each letter. 
\end{lem}

\fpause
We write $f_\# \in S_k$.

\fpause
So this map is in $S_2$:
\[ f_\#: \begin{array}{rcl}
a &\mapsto &\underline{ab^2a}b^{-1}, \\
b &\mapsto &b\underline{ab^{-1}ab}.\end{array} \]
}

\frame{
It's not too hard to show:
\begin{thm}
If $f_\# \in S_k$, then 
\[ \#\Fix(f^n) \ge (km)^n - 2m \]
\end{thm}

\fpause

Immediately we get:
\begin{cor}
\begin{itemize}
\item For any $r$, almost all maps have $\#\Fix(f^n) > r$ for all $n$.

\fpause
\item 
For any $r$, almost all maps have
\[ \text{Growth} \{\#\Fix f^n\} = \lim_{n\to \infty} (\#\Fix f^n)^{1/n} > r \]
\end{itemize}
\end{cor}
}

\frame{
It takes more work, but the above arguments can be adapted using techniques by Hart, Heath, Keppelmann (`08) to hold for sets of minimal periodic points (not just $\Fix f^n$). 
}

\frame{
Jiang (`96) connected these things to topological entropy. 
\fpause
Let $N^\infty(f) = \text{Growth} \{N(f^n)\}$, and Jiang showed that $N^\infty (f)$ is always finite on compact polyhedra. 

\fpause But we show that for any $r$, almost all maps have $N^\infty(f)>r$.

\fpause
So the growth of $\#\Fix(f^n)$ for almost all $f$ is exponential with arbitrarily high (but finite) growth rate.

}

\frame{
Jiang also showed that $\log N^\infty(f) \le h(f)$, where $h$ is the topological entropy of $f$. This is an interesting homotopy invariant lower bound for the entropy.
\fpause
Our results immediately give:
\begin{cor}
Given any $r$, almost all maps have $h(f) > r$.
\end{cor}

\fpause
We show the same result for the fundamental group entropy $h_\#(f)$. (Though generally $h(f) \ge h_\#(f)$.)
}

\frame{
Thank you!
\vfill
Paper at arxiv: Kim, Staecker \emph{Dynamics of random selfmaps of surfaces with boundary}
\vfill
Or my website: \url{http://faculty.fairfield.edu/cstaecker}
\vfill
}
\end{document}