\documentclass{beamer}\usepackage{beamerthemesplit}

\usepackage{amsmath}
\usepackage{amssymb}
\usepackage[all]{xy}\newcommand{\ww}{{\omega^\omega}}
\usepackage{eepic}




\theoremstyle{theorem}
\newtheorem*{thm}{Theorem}
\newtheorem*{lem}{Lemma}


\theoremstyle{definition}
%\newtheorem*{fact}{Fact}
\newtheorem*{defn}{Definition}
\newtheorem*{ques}{Question}
\newtheorem*{cor}{Corollary}















\newcommand{\res}{\restriction}
\newcommand{\bg}{\boldsymbol{\Gamma}}
\newcommand{\bgd}{\check{\boldsymbol{\Gamma}}}
\newcommand{\bd}{\boldsymbol{\Delta}}
\newcommand{\bs}{\boldsymbol{\Sigma}}
\newcommand{\bp}{\boldsymbol{\Pi}}



\newcommand{\on}{\text{On}}
\newcommand{\sP}{\mathcal{P}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}



\newcommand{\lh}{\text{lh}}









\begin{document}


\setbeamercovered{dynamic}



\title{Group Colorings and Shift Equivalence Relations}



\author{S.\ Gao, S.\ Jackson*, B.\ Seward}



\institute{
Department of Mathematics\\
University of North Texas\\
%jackson@unt.edu
}






\date{{\color{red} AMS-ASL Special Session on Logic and Dynamical Systems}\\
January, 2009\\
Washington, DC}






\begin{frame}
\titlepage
\end{frame}


\section{Overview}



\begin{frame}
\frametitle{Overview}

Recall the definition of a $2$-coloring of a countable group $G$. 

\begin{defn}
$c \colon G \to \{ 0,1\}$ is a {\em $2$-coloring} if 

$$
\forall s \in G \ \exists T \in G^{< \omega}\ \forall g \in G\ 
\exists t \in T\ (c(gt) \neq c(gst)).$$
\end{defn}


This definition was formulated independently by Pestov 
(c.f.\ paper of Glasner and Uspenski). 
\end{frame}










\subsection{Significance}

\begin{frame}

\color{blue}Significance of the definition.\color{black}

Let $E$ be the shift equivalence relation on $X=2^G$, given by the action of $G$:

$$
g\cdot x(h)=x(g^{-1}h).$$


Let $F$ denote the {\em free part} of this space, that is, 
$$x \in F \text{ iff }\forall g \neq 1\ (g \cdot x \neq x).$$


\begin{enumerate}
\item
Coloring property gives a {\em marker compactness} property. 



(MCP) Let $S_0 \supseteq S_1 \supseteq S_2 \supseteq \cdots$ be relatively closed
complete sections of $F$. Then $\bigcap_n S_n \neq \emptyset$. 
\item
Coloring property is equivalent to a free orbit closure.
\end{enumerate}
\end{frame}




\subsection{Main Result}

\begin{frame}
\frametitle{Main Result}
\begin{thm}
Every countable group $G$ has the $2$-coloring property.
\end{thm}
\pause
\begin{itemize}
\item
First proof works for abelian, solvable groups.
\item
Second proof works for general groups.
\end{itemize}
\end{frame}















\subsection{Other Reformulations}


\begin{frame}
\frametitle{Other Combinatorial Reformulations}
Other natural descriptive properties have combinatorial reformulations in 
terms of the group $G$. 
\bigskip


\begin{defn}
Colorings $c_1$, $c_2$ of $G$ are {\em orthogonal} ($c_1 \perp c_2$) if 

$$
\exists T \in G^{< \omega}\ \forall g_1, g_2 \in G\ 
\exists t \in T\ (c_1(g_1t) \neq c_2(g_2t)).$$
\end{defn}


\begin{fact} 
If $x,y \in F$, then $x \perp y$ iff $\overline{[x]} \cap \overline{[y]}=\emptyset$.
\end{fact}
\end{frame}



\begin{frame}
\begin{defn}
A coloring $c$ is {\em minimal} if 

$$
\forall S \in G^{< \omega}\ \exists T \in G^{< \omega}\ 
\forall g \in G\ \exists t \in T\ \forall s \in S\ (c(s)=c(gts)).$$
\end{defn}



\begin{fact}
$x \in F$ is minimal iff $\overline{[x]}$ is minimal \newline (i.e., for every 
$y \in \overline{[y]}$ we have $\overline{[x]}=\overline{[y]}$). 
\end{fact}
\end{frame}




\subsection{Extensions}


\begin{frame}
\frametitle{Extension of Result}

\begin{thm}
For every countable group $G$ there is a perfect set of 
pairwise orthogonal, minimal orbits in $F$. 
\end{thm}
\bigskip


In fact, we get more..... 
\end{frame}






\section{First Proof}


\subsection{Case G=Z}










\begin{frame}
First consider the simplest case of $G=\Z$.
\bigskip


The following is not the argument that works in general, but has applications. 
\bigskip





We define two sequences $a_i$, $b_i$ from $2^{< \omega}$. We will have 
$\lh(a_i)=\lh(b_i)$. Can take $b_i=1-a_i$. 
\bigskip




Each $a_{i+1}$, (and $b_{i+1}$) is a concatenation of $a_i$'s and $b_i$'s. 
(May assume $\lh(a_i)>i+1$). 
\bigskip


Let $a_{i+1}=a_ib_i a_i a_i b_i$, \hspace{20pt}
$b_{i+1}=b_i a_i b_i b_i a_i$. 
\end{frame}




\begin{frame}
\setlength{\unitlength}{1mm}

\begin{picture}(150,70)(-10,-50)
\put(0,0){\path(0,0) (15,0) (15,8) (0,8) (0,0)}
\put(15,0){\shade\path(0,0) (15,0) (15,8) (0,8) (0,0)}
\put(30,0){\path(0,0) (15,0) (15,8) (0,8) (0,0)}
\put(45,0){\path(0,0) (15,0) (15,8) (0,8) (0,0)}
\put(60,0){\shade\path(0,0) (15,0) (15,8) (0,8) (0,0)}
\put(7,-5){$a_i$}
\put(22,-5){$b_i$}
\put(37,-5){$a_i$}
\put(52,-5){$a_i$}
\put(67,-5){$b_i$}
\put(-10, 4){$a_{i+1}$}



\end{picture}



\vspace{-90pt}






Let $x$ be any concatenations of $a_{i+1}$'s and $b_{i+1}$'s.
Then for $s=i+1$, can take $T=\{0,1, \dots, 2 \lh(a_{i+1}) \}$. to verify 
the $2$-coloring property for this $s$. 
\bigskip



To get a coloring, take any $x$ such that for each $i$, $x$ is a concatenation of $a_i$'s and $b_i$'s. 
\end{frame}


\subsection{A modification}






\begin{frame}

Easily modify to get a perfect set of pairwise orthogonal $2$-colorings. 
\bigskip


For example, for $w \in 2^\omega$ define $x(w)$ as above but using 
$a_{i+1}=a_i b_i a_i a_i c_i b_i$ where  


$$c_i=\begin{cases} 
a_i & \text{ if } x(i)=0\\
b_i & \text{ if } x(i)=1
\end{cases} 
$$



\setlength{\unitlength}{1mm}


\begin{picture}(150,70)(-10,-50)
\put(0,0){\path(0,0) (15,0) (15,8) (0,8) (0,0)}
\put(15,0){\shade\path(0,0) (15,0) (15,8) (0,8) (0,0)}
\put(30,0){\path(0,0) (15,0) (15,8) (0,8) (0,0)}
\put(45,0){\path(0,0) (15,0) (15,8) (0,8) (0,0)}

\texture{cccccccc a a  a cccccccc a a  a
55555555 0 0  0 cccccccc 0 0  0
33333333 0 0  0 cccccccc 0 0  0
33333333 0 0  0 cccccccc 0 0  0}

%\put(60,0){\shade\path(0,0) (15,0) (15,8) (0,8) (0,0)}
\put(60,1){\fcolorbox{black}{red}{\makebox(12.5,6){}}}

\texture{cccccccc 0 0  0 cccccccc 0 0  0
cccccccc 0 0  0 cccccccc 0 0  0
cccccccc 0 0  0 cccccccc 0 0  0
cccccccc 0 0  0 cccccccc 0 0  0}

\put(75,0){\shade\path(0,0) (15,0) (15,8) (0,8) (0,0)}
\put(7,-5){$a_i$}
\put(22,-5){$b_i$}
\put(37,-5){$a_i$}
\put(52,-5){$a_i$}
\put(67,-5){$c_i$}
\put(82,-5){$b_i$}
\put(-10, 4){$a_{i+1}$}



\end{picture}

\end{frame}




\begin{frame}
Each $x(w)$ has the following {\em marker identification property}:
\bigskip



(MIP) There is a finite $A \subseteq \Z$ such that for any 
$k \in \Z$, whether $k \cdot x$ is the start of an $a_i$ or $b_i$ is determined by 
$k \cdot x \res A$. 
\bigskip

In fact $A$ depends only on $i$, not on $w$. 
\bigskip


If $i$ is least such that $w_1(i) \neq w_2(i)$, then $x(w_1) \perp x(w_2)$ follows from 
the marker identification property, using roughly $A_i+|a_i|$. 
\end{frame}



\subsection{Other G}





\begin{frame}
\frametitle{Extending To Other $G$}


We can extend this method to show the following. 
\bigskip




\begin{thm}
Suppose $\Z \unlhd G$. Then $G$ has the $2$-coloring property. 
\end{thm}


\end{frame}









\begin{frame}
\begin{proof}[proof sketch]
Let $x_1\Z, x_2 \Z,\dots$ be the cosets of $\Z$ in $G=\{ g_1,g_2,\dots\}$. 
If $g \notin \Z$, then $g$ induces a fixed-point-free permutation $\pi_g$ on the cosets. 
 
We use the algorithm above to color each coset $x_i \Z$ with a $2$-coloring 
$c_i$. At step $i$, if $g_i \in \Z$ then we define the $a_i$, $b_i$ for each coset
as above. If $g_i \notin \Z$ then consider $\pi_i=\pi_{g_i}$. On each orbit of 
$\pi_i$, if $\pi_i(x\Z)=y\Z$, then define the $a_i$, $b_i$ for $x\Z$ and for $y\Z$
such that the colorings will be orthogonal, and by a fixed set $A_i$ (not
depending on $x$ and $y$). 


To see this works, for $s \in G$ take cases as to whether $s \in \Z$. If
$s \in \Z$, the $2$-coloring property is satisfied by the argument that each 
$c_n$ is a $2$-coloring. If $s=g_i \notin \Z$, then for $g \in x_j\Z$,
$gs \in x_k \Z$ for some $j \neq k$, and the set $A_i$ witnesses the
$2$-coloring property for $g$ and $gs$ (by the orthogonality of $c_j$ and $c_k$).
\end{proof}
\end{frame}



\subsection{Summary}


\begin{frame}

These methods give:



\begin{cor}
Every abelian, and in fact, every solvable group has the $2$-coloring property.
\end{cor}


\pause

This method can be used to show more, for example:



\begin{thm}
Let $\Z \unlhd G$. Then the set of $2$-colorings of $G$ is $\bp^0_3$-complete. 
\end{thm}

\pause

In summary, these methods show:

\begin{itemize}
\item
Every abelian  or solvable group has the $2$-coloring property.
\item
If $\Z \unlhd G$ or $S \unlhd G$ where $S$ is infinite solvable, then
$G$ has the $2$-coloring property. 
\item
Show directly the free group $F_n$ has the $2$-coloring property.
\end{itemize}


\end{frame}





\section{General Proof}



\subsection{Ideas}




\begin{frame}

Two {\color{red}main ideas}:
\bigskip


\begin{enumerate}
\item
Get reasonable marker regions for general groups.
\item
Exploit polynomial versus exponential growth.
\end{enumerate}

\end{frame}




\subsection{Marker Regions}

\begin{frame}
\frametitle{Marker Regions}

\begin{ques}
What kind of marker regions can we get for general groups?
\end{ques}


\pause

Say a group $G$ has {\em regular markers} if 
there are $E_0 \subseteq E_1 \subseteq E_2 \subseteq \cdots$, each $E_i$ an
equivalence relation on $G$ with finite classes each of which is a translate 
by a fixed set $A_i \subseteq G$, and such that 
$\bigcup_i E_i= G \times G$.


\pause

\begin{ques}
Which groups admit regular markers?
\end{ques}
\end{frame}





\begin{frame}


For general groups we get the following marker structure.
\bigskip


Will have marker sets $\bd_1 \supseteq \bd_2 \supseteq \bd_3 \supseteq \cdots$ 
(each $\bd_n \subseteq G$). 
\bigskip


Will have $F_1 \subseteq F_2 \subseteq F_3 \subseteq \cdots$ (each $F_n \subseteq G$ finite).
\bigskip



\begin{itemize}
\item
The $\bd_n$ translates of $F_n$ are maximally disjoint.  
\item
Each $F_n$ will be a disjoint union of copies of $F_{1}, \dots, F_{n-1}$. 
\item
(homogeneity)
Within  any copy $\gamma F_n$ of $F_n$, the  points in $\bd_k$ ($k \leq n$) 
are precisely the translates $\gamma (\bd_k \cap F_n)$ of the points in $F_n$. 
\item
(fullness)
If a copy $\delta F_k$ intersects $\gamma F_n$ ($k \leq n$) 
then $\delta F_k \subseteq \gamma F_n$.
\end{itemize}
\end{frame}






\begin{frame}


\normalsize

\begin{figure}[h]
\begin{center}
\setlength{\unitlength}{8mm}
\begin{picture}(14,8.5)(0,0)
%\put(0,0){\line(1,0){15}}

%\linethickness{.1mm}
\put(11,6){\makebox(0,0)[b]{$H_n$}}
\qbezier(0,3)(0,8)(7,8)
\qbezier(0,3)(0,0)(5,0)
\qbezier(5,0)(12,0)(12,5)
\qbezier(7,8)(12,8)(12,5)

\linethickness{.08mm}
\put(-1.5,-0.1){
\put(5,5){\makebox(0,0)[b]{$F_{n-1}$}}
\qbezier(3,4.5)(3,3)(4.5,3)
\qbezier(3,4.5)(3,6)(4.5,6)
\qbezier(4.5,3)(6,3)(6,4.5)
\qbezier(4.5,6)(6,6)(6,4.5)}

\linethickness{.075mm}
\put(2.5,-2){
\put(5,5){\makebox(0,0)[b]{$\gamma_1 F_{n-1}$}}
\qbezier(3,4.5)(3,3)(4.5,3)
\qbezier(3,4.5)(3,6)(4.5,6)
\qbezier(4.5,3)(6,3)(6,4.5)
\qbezier(4.5,6)(6,6)(6,4.5)}

\linethickness{.075mm}
\put(4.2,1.3){
\put(5,5){\makebox(0,0)[b]{$\gamma_2 F_{n-1}$}}
\qbezier(3,4.5)(3,3)(4.5,3)
\qbezier(3,4.5)(3,6)(4.5,6)
\qbezier(4.5,3)(6,3)(6,4.5)
\qbezier(4.5,6)(6,6)(6,4.5)}

\put(3.3,1.0){
\put(1.1, 1.1){\makebox(0,0)[b]{$\lambda_1 F_{n-2}$}}
\put(1,1){\circle{2}}}

\put(4.6,4.6){
\put(1, 1.1){\makebox(0,0)[b]{$\lambda_2 F_{n-2}$}}
\put(1,1){\circle{2}}}


\put(5.5,4){\circle{.8}}
\put(7,4.6){\circle{.8}}
\put(9, 3.5){\circle{.8}}

\put(6.8,6){\circle{.4}}
\put(6.9, 5.4){\circle{.4}}
\put(6.2, 4.3){\circle{.4}}
\put(5.1, 3.3){\circle{.4}}
\put(8, 4.1){\circle{.4}}
\put(7.6, 4.3){\circle{.4}}
\put(8.4, 3.8){\circle{.4}}

\end{picture}
\caption{The composition of $F_n$}
\end{center}
\end{figure}

\end{frame}



\begin{frame}

\normalsize
\vspace{-20pt}
%\hspace{-160pt}

\begin{figure}[h]
\begin{center}
\setlength{\unitlength}{0.8cm}
\begin{picture}(15,8)(-.3,0)

\put(6,3.7){\oval(12,7.5)}
\put(11, 6.5){\makebox(0,0)[b]{$\gamma F_n$}}

\put(0.4,4.4){
\put(1.2,1.0){\oval(2.2,2.6)}
\put(1.2,.8){\circle*{.1}}
\put(1.2,1.5){\circle*{.1}}
%\put(1.2,2.4){\circle*{.1}}
\put(.7,.7){\makebox(0,0)[b]{$b_{n-1}$}}
%\put(1.5, .7){\makebox(0,0)[b]{$0$}}
\put(.7,1.3){\makebox(0,0)[b]{$a_{n-1}$}}
%\put(1.5, 1.4){\makebox(0,0)[b]{?}}
%\put(.7,2.2){\makebox(0,0)[b]{$\omega_{n-1}$}}
%\put(1.5,2.3){\makebox(0,0)[b]{?}}
\put(1.2, -1.0){\makebox(0,0)[b]{$\lambda^n_1F_{n-1}$}}
}

\put(3,4.4){
\put(1.2,1.0){\oval(2.2,2.6)}
\put(1.2,.8){\circle*{.1}}
\put(1.2,1.5){\circle*{.1}}
%\put(1.2,2.4){\circle*{.1}}
\put(.7,.7){\makebox(0,0)[b]{$b_{n-1}$}}
%\put(1.5, .7){\makebox(0,0)[b]{$0$}}
\put(.7,1.3){\makebox(0,0)[b]{$a_{n-1}$}}
%\put(1.5, 1.4){\makebox(0,0)[b]{?}}
%\put(.7,2.2){\makebox(0,0)[b]{$\omega_{n-1}$}}
%\put(1.5,2.3){\makebox(0,0)[b]{?}}
\put(1.2, -1.0){\makebox(0,0)[b]{$\lambda^n_2F_{n-1}$}}
}

\put(6.4, 5.5){\circle*{.05}}
\put(6.6, 5.5){\circle*{.05}}
\put(6.8, 5.5){\circle*{.05}}



\put(8,4.4){
\put(1.2,1.0){\oval(2.2,2.6)}
\put(1.2,.8){\circle*{.1}}
\put(1.2,1.5){\circle*{.1}}
%\put(1.2,2.4){\circle*{.1}}
\put(.7,.7){\makebox(0,0)[b]{$b_{n-1}$}}
%\put(1.5, .7){\makebox(0,0)[b]{$0$}}
\put(.7,1.3){\makebox(0,0)[b]{$a_{n-1}$}}
%\put(1.5, 1.4){\makebox(0,0)[b]{?}}
%\put(.7,2.2){\makebox(0,0)[b]{$\omega_{n-1}$}}
%\put(1.5,2.3){\makebox(0,0)[b]{?}}
\put(1.2, -1.0){\makebox(0,0)[b]{$\lambda^n_{s(n)}F_{n-1}$}}
}






\put(1,1){
\put(1.2,1.0){\oval(2.2,2.6)}
\put(1.2,.8){\circle*{.1}}
\put(1.2,1.5){\circle*{.1}}
%\put(1.2,2.4){\circle*{.1}}
\put(.7,.7){\makebox(0,0)[b]{$b_{n-1}$}}
%\put(1.5, .7){\makebox(0,0)[b]{$1$}}
\put(.7,1.3){\makebox(0,0)[b]{$a_{n-1}$}}
%\put(1.5, 1.4){\makebox(0,0)[b]{$1$}}
%\put(.7,2.2){\makebox(0,0)[b]{$\omega_{n-1}$}}
%\put(1.5,2.3){\makebox(0,0)[b]{?}}
\put(1.2, -1.0){\makebox(0,0)[b]{$\lambda^n_{s(n)+1}F_{n-1}$}}
}

\put(3.6,1){
\put(1.2,1.0){\oval(2.2,2.6)}
\put(1.2,.8){\circle*{.1}}
\put(1.2,1.5){\circle*{.1}}
%\put(1.2,2.4){\circle*{.1}}
\put(.7,.7){\makebox(0,0)[b]{$b_{n-1}$}}
%\put(1.5, .7){\makebox(0,0)[b]{$0$}}
\put(.7,1.3){\makebox(0,0)[b]{$a_{n-1}$}}
%\put(1.5, 1.4){\makebox(0,0)[b]{?}}
%\put(.7,2.2){\makebox(0,0)[b]{$\omega_{n-1}$}}
%\put(1.5,2.3){\makebox(0,0)[b]{?}}
\put(1.2, -1.0){\makebox(0,0)[b]{$\lambda^n_{s(n)+2}F_{n-1}$}}
}

\put(6.2,1){
\put(1.2,1.0){\oval(2.2,2.6)}
\put(1.2,.8){\circle*{.1}}
\put(1.2,1.5){\circle*{.1}}
%\put(1.2,2.4){\circle*{.1}}
\put(.7,.7){\makebox(0,0)[b]{$b_{n-1}$}}
%\put(1.5, .7){\makebox(0,0)[b]{?}}
\put(.7,1.3){\makebox(0,0)[b]{$a_{n-1}$}}
%\put(1.5, 1.4){\makebox(0,0)[b]{$0$}}
%\put(.7,2.2){\makebox(0,0)[b]{$\omega_{n-1}$}}
%\put(1.5,2.3){\makebox(0,0)[b]{?}}
\put(1.2, -1.0){\makebox(0,0)[b]{$\lambda^n_{s(n)+3}F_{n-1}$}}
}



\end{picture}
\caption{The labeling of the $F_{n-1}$ copies inside an $F_n$ copy}
\end{center}
\end{figure}
\end{frame}







\subsection{The coloring}




\begin{frame}
We define a coloring $c=\bigcup c_n$, which will then be extended to the $2$-coloring $c'$.
\bigskip

$c$ will color all points except those in 
$$D=\bigcup_n \bd_n \{ \lambda^n_1,\dots,\lambda^n_{s(n)}\} b_{n-1}.$$
\bigskip

 

In extending $c_{n-1}$ to $c_n$ we color the above points except for those in 
$\bd_n \lambda^n_1,\dots, \bd_b \lambda^n_{s(n)}$, and $\bd_n \{ a_n,b_n\}$ where: 
\bigskip


\begin{equation*}
\begin{split}
a_n & \doteq  \lambda^n_{s(n)+2} \, a_{n-1}\\  
b_n& \doteq \lambda^n_{s(n)+3} \, b_{n-1}.
\end{split}
\end{equation*}
\end{frame}





\begin{frame}
\vspace{-20pt}

\begin{figure}[h]
\begin{center}
\setlength{\unitlength}{0.8cm}
\begin{picture}(15,8)(-.3,0)

\put(6,3.7){\oval(12,7.5)}
\put(11, 6.5){\makebox(0,0)[b]{$\gamma F_n$}}

\put(0.4,4.4){
\put(1.2,1.0){\oval(2.2,2.6)}
\put(1.2,.8){\circle*{.1}}
\put(1.2,1.5){\circle*{.1}}
%\put(1.2,2.4){\circle*{.1}}
\put(.7,.7){\makebox(0,0)[b]{$b_{n-1}$}}
\put(1.5, .7){\makebox(0,0)[b]{$?$}}
\put(.7,1.3){\makebox(0,0)[b]{$a_{n-1}$}}
\put(1.5, 1.4){\makebox(0,0)[b]{0}}
%\put(.7,2.2){\makebox(0,0)[b]{$\omega_{n-1}$}}
%\put(1.5,2.3){\makebox(0,0)[b]{?}}
\put(1.2, -1.0){\makebox(0,0)[b]{$\lambda^n_1F_{n-1}$}}
}

\put(3,4.4){
\put(1.2,1.0){\oval(2.2,2.6)}
\put(1.2,.8){\circle*{.1}}
\put(1.2,1.5){\circle*{.1}}
%\put(1.2,2.4){\circle*{.1}}
\put(.7,.7){\makebox(0,0)[b]{$b_{n-1}$}}
\put(1.5, .7){\makebox(0,0)[b]{$?$}}
\put(.7,1.3){\makebox(0,0)[b]{$a_{n-1}$}}
\put(1.5, 1.4){\makebox(0,0)[b]{0}}
%\put(.7,2.2){\makebox(0,0)[b]{$\omega_{n-1}$}}
%\put(1.5,2.3){\makebox(0,0)[b]{?}}
\put(1.2, -1.0){\makebox(0,0)[b]{$\lambda^n_2F_{n-1}$}}
}

\put(6.4, 5.5){\circle*{.05}}
\put(6.6, 5.5){\circle*{.05}}
\put(6.8, 5.5){\circle*{.05}}





\put(8,4.4){
\put(1.2,1.0){\oval(2.2,2.6)}
\put(1.2,.8){\circle*{.1}}
\put(1.2,1.5){\circle*{.1}}
%\put(1.2,2.4){\circle*{.1}}
\put(.7,.7){\makebox(0,0)[b]{$b_{n-1}$}}
\put(1.5, .7){\makebox(0,0)[b]{$?$}}
\put(.7,1.3){\makebox(0,0)[b]{$a_{n-1}$}}
\put(1.5, 1.4){\makebox(0,0)[b]{0}}
%\put(.7,2.2){\makebox(0,0)[b]{$\omega_{n-1}$}}
%\put(1.5,2.3){\makebox(0,0)[b]{?}}
\put(1.2, -1.0){\makebox(0,0)[b]{$\lambda^n_{s(n)}F_{n-1}$}}
}










\put(1,1){
\put(1.2,1.0){\oval(2.2,2.6)}
\put(1.2,.8){\circle*{.1}}
\put(1.2,1.5){\circle*{.1}}
%\put(1.2,2.4){\circle*{.1}}
\put(.7,.7){\makebox(0,0)[b]{$b_{n-1}$}}
\put(1.5, .7){\makebox(0,0)[b]{$1$}}
\put(.7,1.3){\makebox(0,0)[b]{$a_{n-1}$}}
\put(1.5, 1.4){\makebox(0,0)[b]{$1$}}
%\put(.7,2.2){\makebox(0,0)[b]{$\omega_{n-1}$}}
%\put(1.5,2.3){\makebox(0,0)[b]{?}}
\put(1.2, -1.0){\makebox(0,0)[b]{$\lambda^n_{s(n)+1}F_{n-1}$}}
}

\put(3.6,1){
\put(1.2,1.0){\oval(2.2,2.6)}
\put(1.2,.8){\circle*{.1}}
\put(1.2,1.5){\circle*{.1}}
%\put(1.2,2.4){\circle*{.1}}
\put(.7,.7){\makebox(0,0)[b]{$b_{n-1}$}}
\put(1.5, .7){\makebox(0,0)[b]{$0$}}
\put(.7,1.3){\makebox(0,0)[b]{$a_{n-1}$}}
\put(1.5, 1.4){\makebox(0,0)[b]{?}}
%\put(.7,2.2){\makebox(0,0)[b]{$\omega_{n-1}$}}
%\put(1.5,2.3){\makebox(0,0)[b]{?}}
\put(1.2, -1.0){\makebox(0,0)[b]{$\lambda^n_{s(n)+2}F_{n-1}$}}
}

\put(6.2,1){
\put(1.2,1.0){\oval(2.2,2.6)}
\put(1.2,.8){\circle*{.1}}
\put(1.2,1.5){\circle*{.1}}
%\put(1.2,2.4){\circle*{.1}}
\put(.7,.7){\makebox(0,0)[b]{$b_{n-1}$}}
\put(1.5, .7){\makebox(0,0)[b]{?}}
\put(.7,1.3){\makebox(0,0)[b]{$a_{n-1}$}}
\put(1.5, 1.4){\makebox(0,0)[b]{$0$}}
%\put(.7,2.2){\makebox(0,0)[b]{$\omega_{n-1}$}}
%\put(1.5,2.3){\makebox(0,0)[b]{?}}
\put(1.2, -1.0){\makebox(0,0)[b]{$\lambda^n_{s(n)+3}F_{n-1}$}}
}




\end{picture}
\caption{Extending $c_{n-1}$ to $c_n$. }
\end{center}
\end{figure}

\end{frame}





\begin{frame}



We extend $c$ to $c'$ by coloring the points of $D$ so as to get a $2$-coloring. 
Exploit polynomial versus exponential growth. 
\bigskip



At stage $n$ we extend $c$ to points of 
$\bd_n \{ \lambda^n_1,\dots, \lambda^n_{s(n)}\} b_{n-1}$ to take care of
coloring property for $s=g_n \in H_n$.
\bigskip


Let $g \in G$ and consider the pair $g, gs$. 
By maximal disjointness of $F_n$ copies, $gf \in \bd_n$ for some $f \in F_n F_n^{-1}$. 
Done unless $gsf \in \bd_n$. In this case 
$$gsf= gf (f^{-1} s f) \in (gf)  F_n F_n^{-1} H_n F_n F_n^{-1}.$$
\bigskip


So there are about $|H_n|^5$ many points to consider, and there 
$2^{s(n)}$ many ``colors'' available, where $s(n)$ is linear in $|H_n|$. 
\end{frame}




























\end{document}