\documentclass{beamer}
\usetheme{default}
\usepackage[utf8]{inputenc}
\input{epsf}
\title[permutation pattern avoidance]
{Permutations  Avoiding Pattern}

\setbeamertemplate{navigation symbols}{}


\date[REU 2009]{DIMACS REU 2009}
\author[O. B\'ilka]{Presented by Ond\v{r}ej B\'ilka}
\begin{document}

\begin{frame}
\titlepage
\end{frame}
\begin{frame}
\frametitle{Permutations}
	Permutation: a mapping $\{1,2,\ldots,n\}$ onto $\{1,2,\ldots,n\}$.\\
  We call the set of permutations of order n as $S_n$.\\
	We can visualize permutations in this way:\\
\only<1>{
\epsfbox{perm.1}
}
\pause
\epsfbox{perm.3}\\
We call permutation $\tau$ {\it involution} if $\tau=\tau^{-1}$\\
We call set of involutions of order n as $I_n$.
\end{frame}
\begin{frame}
\frametitle{Included pattern}
  Permutation $\sigma$ contains pattern $\tau$ if we  can by removing rows and collumns obtain permutation $\tau$.\\
The pattern \\
\begin{center} \includegraphics{perm.5} \end{center}
is contained in the following permutation\\
\begin{center} \epsfbox{perm.6} \end{center}
\end{frame}
\begin{frame}
\frametitle{Wilf's equivalence}
$S_n(\tau)=\{\sigma | \sigma \in S_n , \sigma $ does not contain $\tau \}$.\\
$I_n(\tau)=\{\sigma | \sigma \in I_n , \sigma $ does not contain $\tau \}$.\\
\pause
	We call permutations $\sigma,\tau$ Wilf-equivalent for \\
permutations if $\forall n$ $|S_n(\sigma)|=|S_n(\tau)|$ denoted by $\sigma \sim_{S} \tau$,\\
involutions  if $\forall n$ $|I_n(\sigma)|=|I_n(\tau)|$ denoted by $\sigma \sim_{I} \tau$.\\
\pause
Observation: $\sigma \sim_{S} \sigma^{-1} $\\
\epsfbox{perm.8} \epsfbox{perm.7}
\end{frame}
\begin{frame}
\frametitle{The problem}
	Our problem is:\\
	Does $\sigma \sim_{I} \tau$ for $\sigma,\tau \in I_n$ imply that $\sigma \sim_{S} \tau$?\\
\pause
	Converse is not true. For example:\\
\epsfbox{perm.10} and \epsfbox{perm.9}
\end{frame}
\end{document}