\documentclass{beamer}
\usepackage{beamerthemesplit}

\usepackage{amsmath}
\usepackage{amssymb}
\usepackage[all]{xy}\newcommand{\ww}{{\omega^\omega}}
\usepackage{eepic}
\usepackage{xcolor}
\usepackage{comment}
%\usepackage{tikz}



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


\theoremstyle{definition}
%\newtheorem*{fact}{Fact}
\newtheorem*{defn}{Definition}
\newtheorem*{ques}{Question}
\newtheorem*{cor}{Corollary}
\newtheorem*{conj}{Conjecture}
\newtheorem*{rem}{Remark}
\newtheorem*{ex}{Example}












\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}}
\newcommand{\mys}{\bigskip}

\newcommand{\id}{\text{id}}
\newcommand{\ac}{\mathsf{AC}}
\newcommand{\sI}{\mathcal{I}}
\newcommand{\sB}{\mathcal{B}}




\begin{document}


\setbeamercovered{dynamic}

\title{Countable Borel Equivalence Relations, Markers, and Shift Equivalence}




\author{S.\ Jackson}



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






\date{{\color{red}Real Analysis 33}\\
June, 2009\\
Durant, Oklahoma}


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


\section{Equivalence Relations}

 
\subsection{Introduction}


\begin{frame}
%\subsection{Introduction}

$X$, $Y$ will denote {\color{red} standard Borel spaces}.
\mys


An equivalence relation $E$ is {\color{red} countable} if all 
classes $[x]_E$ are countable. $E$ is {\color{red} Borel} if 
$E \subseteq X \times X$ is Borel. 
\mys





$X/E$ is the {\color{red} quotient space} of equivalence classes. 
\mys



\begin{ex}
If $E=\id$, then $X/E \cong X$, a standard Borel space.
\end{ex}
\end{frame}


\begin{frame}

With $\ac$, every set has a cardinality, and those of size $c=2^\omega$
can be viewed as standard Borel spaces. 
\mys

So, with $\ac$, for every countable $E$, $X/E$ is isomorphic to a
standard Borel space. 
\mys




However, we are interested in ``definable'' cardinalities, i.e., definable
maps between spaces. Usually this means Borel. 
\mys


Note that $X/\id \cong X$ by a Borel map, namely, $f=\id$.
\end{frame}


\begin{frame}


\begin{defn}
If $(X, E)$, $(Y, F)$ are Borel equivalence relations, we say $E \leq F$ 
($E$ is {\color{red} reducible} to $F$) 
if there is a Borel function $f \colon X \to Y$ such that 
$$x\ E\ y \leftrightarrow f(x)\ F\ f(y).$$
\end{defn}
\mys


$X/E$ is Borel isomorphic to a standard Borel space iff 
$(X,E) \leq (\R, \id)$. 
\mys


When $E$ is countable this equivalent to saying $E$ has a Borel 
{\color{red} selector}:
\mys


\begin{defn}
$S \subseteq X$ is a selector for $E$ if for all $x$, 
$| S \cap [x]_E|=1$.
\end{defn}
\mys
\end{frame}

\begin{frame}

\begin{defn}
$E$ is {\color{red} smooth} or {\color{red} tame} if 
$E \leq \id$.
\end{defn}
\mys


When $E$ is smooth, then $X/E$ is Borel isomorphic to a standard Borel space, and
in this case the ``Borel cardinalities'' are completely understood.
\mys

Namely, if $A \subseteq X$ is Borel, then either $A$ is countable or contains a perfect
subset. Any two Borel sets in a Polish space of the same cardinality are Borel isomorphic. 
\mys

So, for countable $E$ on an uncountable Polish space $X$, there is up
to Borel isomorphism only one smooth equivalence relation, $\id$. 
\end{frame}




\begin{frame}


\begin{thm}[Silver]
If $E$ is a $\bp^1_1$ equivalence relation on a Polish space $X$, then $E$
has either countable many or perfectly many equivalence classes. 
\end{thm}
\mys


\begin{cor}
If $E$ is a Borel equivalence relation with uncountably many classes, then 
$\id \leq E$.
\end{cor}
\mys



Let $\{ n\}$ be a Borel equivalence relation with $n$ classes. 
Likewise for $\{ \omega\}$.
\mys

For general Borel $E$ we have the following initial segment of the 
equivalence relations:
\mys



$$
\{ 1\} \leq \{2\} \cdots \leq \{ \omega\} \leq \id$$
\mys

For countable $E$, we have $\id$ at the bottom. 
\end{frame}



\begin{frame}


Let $E_0$ be the equivalence relation of eventual equality on 
$2^\omega$:
\mys


$$
x\ E_0\ y \leftrightarrow \exists n\ \forall n \geq n\ (x(m)=y(m)).
$$




\begin{fact}
$E_0$ is bireducible with the Vitali equivalence relation on $\R$.
\end{fact}
\mys




\begin{thm}[Harrington-Kechris-Louveau]
Let $E$ be a Borel equivalence relation on a Polish space $X$ 
Then either $E \leq \id$ or $E_0 \leq E$ (in fact $E_0 \sqsubseteq E$).
\end{thm}
\mys


So, for general Borel $E$ we have:
\mys


$$
\{1\} \leq \{2 \} \leq \cdots \leq \{ \omega\} \leq \id \leq E_0.
$$

\end{frame}



\begin{frame}
General Borel equivalence relations can arise in many different ways.
\mys



\begin{itemize}
\item
The {\color{red} orbit equivalence relation} from a Borel action of
a Polish group $G$ on a Polish space $X$.  

For example, the {\color{red} logic action} of $S_\infty$ on the models of
a countable theory.
\item
If $\sI$ is any Borel ideal on $\omega$, $x \equiv y$ iff $x \triangle y \in \sI$.
\item
$\sB$ a separable Banach space with basis $\{ e_1, e_2,\dots\}$. 
$X=\R^\omega$ with  $x E y$ iff $x-y \in \sB$. For example
$c_0, \ell_1, \ell_p, \dots, \ell_\infty$. 
\item 
$E_1$ on $(2^\omega)^\omega$: $\{ x_n\} E_1\ \{ y_n\}$
iff $\exists k\ \forall \ell \geq k\ (x_\ell =y_\ell)$.
\item
$(E_0)^\omega$, the countable product of $E_0$. 
\item
$x =^+ y$ iff $\{ x_n\}=\{ y_n\}$.
\end{itemize}


\end{frame}


\begin{frame}



\begin{center}
\setlength{\unitlength}{.3cm}
\begin{picture}(20,25)(0,0)

\put(10,1){\circle*{.3}}
\put(12,0.2){\makebox(0,0)[b]{$\id(2^\omega)$}}
\put(10,1){\line(0,1){3}}
\put(10,4){\circle*{.3}}
\put(11,2.8){\makebox(0,0)[b]{$E_0$}}

\put(10,4){\line(-3,2){6}}
\put(4,8){\circle*{.3}}
\put(3,6.5){\makebox(0,0)[b]{$E_0^\omega$}}
\put(10,4){\line(-1,2){2}}
\put(8,8){\circle*{.3}}
\put(7.5,6.5){\makebox(0,0)[b]{$E_\infty$}}
\put(10,4){\line(1,2){2}}
\put(12,8){\circle*{.3}}
\put(12.5,6.5){\makebox(0,0)[b]{$\ell_1$}}
\put(10,4){\line(3,2){6}}
\put(16,8){\circle*{.3}}
\put(16.2,6.5){\makebox(0,0)[b]{$E_1$}}

\put(4,8){\line(0,1){6}}
\put(4,14){\circle*{.3}}
\put(3,13.8){\makebox(0,0)[b]{$=^+$}}
\put(4,14){\line(2,-3){4}}
\put(16,8){\line(0,1){6}}
\put(16,14){\circle*{.3}}
\put(17,13.2){\makebox(0,0)[b]{$\ell_\infty$}}
\put(21.2,13.2){\makebox(0,0)[b]{(equivalence}}
\put(21,12){\makebox(0,0){of bases)}}
\put(16,14){\line(-2,-3){4}}
\put(16,14){\line(-4,-3){8}}

\put(10,23){\line(2,-3){6}}
\put(10,23){\line(-2,-3){6}}
\put(10,23){\circle*{.3}}
\put(10.2,23){\makebox(0,0)[b]{$E_{{\bf\Sigma}^1_1}$}}
\put(15.5,23){\makebox(0,0)[b]{(isomorphism)}}

\put(12,8){\line(-2,3){6}}
\put(6,17){\circle*{.3}}
\put(5,17){\makebox(0,0)[b]{$E_G^\infty$}}
\put(9.5,17){\makebox(0,0)[b]{(isometry)}}

\end{picture}

\end{center}


\end{frame}


\begin{frame}

If $G$ is a countable group, then $2^G$ is a compact Polish space.
\mys


The {\color{red}(left) action} of $G$ on $2^G$ is given by:


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

Equivalently, $g \cdot A = gA=\{ g a \colon a \in A\}$, where $A \subseteq G$.
\mys


\begin{ex}
$\Z^n$ acts by shifts on $2^{\Z^n}$. Equivalence classes can be viewed
as $n$-dimensional grids of $0$s and $1$s (without specifying an origin).
\end{ex}



\end{frame}

\subsection{Hyperfinite}

\begin{frame}




We consider henceforth countable Borel equivalence relations. 
\mys



\begin{thm}[Feldman-Moore]
If $E$ is a countable Borel equivalence relation, the $E$ is induced by the 
Borel action of a countable group $G$. 
\end{thm}
\mys


Thus, it makes sense to study countable equivalence relations ``group by group.''
\mys





If $G$ is a finite group, then $E_G$ is smooth.
\mys



\begin{defn}
$E$ is {\color{red} hyperfinite} if $E$ is an increasing union 
$E= \bigcup_n E_n$ where each $E_n$ is finite (i.e., all classes are finite).
\end{defn}
\end{frame}



\begin{frame}
Consider the simplest infinite group $\Z$.
\mys



\begin{thm}[Slaman-Steel]
The following are equivalent.
\mys


\begin{enumerate}
\item
$E$ is hyperfinite.
\item
$E$ is induced by a Borel action of $\Z$.
\item
All the $E$ (infinite) classes can be uniformly $\Z$ ordered.
\item
$E \leq E_0$.
\end{enumerate}
\end{thm}
\mys


In particular, $\Z$-actions give rise to hyperfinite equivalence relations. 
\end{frame}


\begin{frame}




\begin{ques}
For which countable groups $G$ are the Borel actions of $G$
necessarily hyperfinite?
\end{ques}
\mys




\begin{thm}[Weiss]
If $E$ is induced by a Borel action of $\Z^n$, then $E$
is hyperfinite.
\end{thm}
\mys











$G$ is {\color{red}amenable} if $G$ has an invariant probability measure.
Equivalent to the existence of a {\color{red}F\"{o}lner} sequence.
\mys



\begin{fact}
If $G$ is {\color{red} non-amenable} then there is a free action of $G$
which is not hyperfinite.
\end{fact}
\end{frame}


\begin{frame}


\begin{conj}[Kechris]
If $G$ is amenable, then every Borel action of $G$ is hyperfinite.
\end{conj}



The conjecture has some credibility due to the following results.
\mys



\begin{thm}[Connes-Feldman-Weiss]
If $E$ is an equivalence relation induced by the action of an amenable
group
with an invariant probability measure $\mu$, then $E$ is 
hyperfinite $\mu$-almost everywhere.
\end{thm}
\mys




\begin{thm}[Gao-J]
Every Borel action of a countable abelian group is hyperfinite.
\end{thm}


\end{frame}



\begin{frame}
\section{New Hyperfiniteness Proofs}

The proof of the abelian result gives new information, even in the simplest case
of $G=\Z$. 
\mys


\begin{thm}
There is a {\color{red} continuous} embedding from 
$2^\Z$ into $E_0$. 
\end{thm}
\mys


In fact, we get:


\begin{thm}
There is a {\color{red} continuous} embedding $f$ from 
$2^\Z$ into $E_0$ such that if $y\in 2^\Z$ is a positive shift of $x$, then 
$f(y)$ is a positive shift under the odometer action of $f(x)$. 
\end{thm}
\end{frame}

\begin{frame}


This generalized to $(\ww)^\Z$ which then shows:
\mys


\begin{cor}
If $(X,E)$ is induced by the continuous action of $\Z$ on a $0$-dimensional Polish space $X$,
then there is a continuous embedding from $(X,E)$ to $(2^\omega,E_0)$. 
\end{cor}
\mys

So, $E_0$ is {\color{red} universal} for continuous actions of $\Z$ on 
$0$-dimensional Polish spaces. 
\mys

In fact:

\begin{cor}
Let $\pi$ be a free auto-homeomorphism of a $0$-dimensional Polish space 
$X$. Then $\pi$ is topologically isomorphic to the action of the odometer on
a subspace of $2^\omega$. 
\end{cor}


\end{frame}

\subsection{Nice Markers}

\begin{frame}


Proof uses the construction of nice marker regions.
\mys



\begin{defn}
A {\color{red} Marker set} for $(X,E)$ is a Borel set $M \subseteq X$
with $M \cap [x]_E\neq \emptyset$ for all $x \in X$. 

A set of {\color{red} marker regions} for $(X,E)$ is a Borel finite 
subequivalence relation $R \subseteq E$. 

$M$ is associated  to $R$ if $|M \cap [x]_R|=1$ for all $x \in X$. 
\end{defn}
\mys


Note: Every set of marker regions has an associated marker set.
\mys

The proofs of the previous theorems use the construction of 
marker regions with nice geometric and definability properties.
\end{frame}

\subsection{Some Results}

\begin{frame}


These methods led to the following results.
\mys


\begin{thm}
There is a continuous embedding from $2^{\Z^n}$ into $E_0$. 
Likewise for continuous action of $\Z^n$ on a $0$-dimensional
Polish space. 
\end{thm}


\begin{thm}
There is a continuous embedding from the free part 
$F$ of $2^{\Z^{<\omega}}$ into $E_0$. 
\end{thm}


\begin{thm}
There is a Borel embedding from $2^{\Z^{<\omega}}$ into $E_0$.
\end{thm}


\begin{thm}
Every equivalence relation generated by the Borel action of an 
abelian group is hyperfinite.
\end{thm}
 
\end{frame}

\subsection{Marker Construction}


\begin{frame}


To illustrate the ideas, we sketch the proof in the simplest setting:
show there is a continuous embedding from $F(2^\Z)$ into $E_0$. 
\mys



First we get (relatively) clopen marker sets (we do this step for $\Z^n$):



\begin{itemize}
\item
$S_0 \supseteq S_1 \supseteq S_2 \supseteq \cdots$, each $S_i$ relatively clopen in $F(2^\Z)$. 
\item
There are distances $d_0 \gg d_1 \gg d_2 \gg \cdots$ such that:
\begin{enumerate}
\item
$\forall x,y \in S_n\ \rho(x,y)> d_n$. 
\item
$\forall x \in X\ \exists y \in S_n\ \rho(x,y) \leq d_n$.
\end{enumerate}
\end{itemize}


The definition of $S_n$ is an $\omega$-length construction, constructing a maximal
set $S_n=\bigcup_i S_n^i$ satisfying (1).
\mys

Sets are $S_n^i$ relatively open, so also is $S_n$. Maximality gives (2) which also
shows $S_n$ is relatively closed. 
\end{frame}









\begin{frame}
From these clopen marker sets, one next constructs clopen marker regions which are 
rectangular.  In fact, they can made almost the same size (side lengths of either 
$d_n$ or $d_n+1$). 
\mys



\begin{ques}
Can you get Borel marker regions for $F(2^{\Z^n})$ which are almost the same size and almost 
lined-up?
\end{ques}
\mys




Construction of the marker regions from the marker sets uses the ``big marker-little marker''
method, and a finite sequence of successive adjustments.
\mys


In case of $\Z$, this step is rather trivial.
\end{frame}




\subsection{construction of embedding}




\begin{frame}


Next we modify the marker regions to anti-cohere. 
\mys



At each step when we produce marker regions $R^n$, we also produce an ``orthogonal''
set of marker regions $\tilde{R}^n$: no face of an $\tilde{R}^n$ rectangle is close to a parallel
face of an $R^n$ rectangle. 
\mys


For $\Z$ this just says the endpoints of each $\tilde{R}^n$ interval are not close
to those of an $R^n$ interval
\mys


Close here means some fixed fraction of $d_n$ (a geometrical constant depending only on $n$).
\mys


The $\tilde{R}^n$ are produced by the same adjustment process as the $R^n$.
\end{frame}









\begin{frame}
We now use the $R^n$ and $\tilde{R}^n$ to produce the final 
clopen marker regions $Q^n$. 
\mys


We start with $R^n_n=R^n$, and we define the marker regions $R^n_{n-1},\dots, R^n_0$,
and we will set $Q^n=R^n_0$.
\mys


\begin{rem}
In the $\Z^n$ case the $R^n_n, \dots, R^n_1$ become increasingly ``fractal.''
\end{rem}
\mys



In going from $R^n_{i+1}$ to $R^n_i$ we add or subtract an interval of $\tilde{R}^i$
from the ends of each interval in $R^n_{i+1}$. This ensures that the new 
endpoints of each $R^n_i$ interval are a fraction of $d_i$ away those of each $R^i$
interval.
\mys



We assume w.l.o.g.\ that $d_i \gg \sum_{j<i} d_j$. 
\mys



\end{frame}





\begin{frame}
\begin{itemize}
\item
Each $Q^n$ interval is $\sum_{j<i} d_j \ll d_n$ close to an $R^n$ interval.
\item
For $n>m$, the endpoints of each $Q^n$ interval are $d_m$ far from the endpoints of each 
$R^m$, and hence each $Q^m$ interval.
\end{itemize}
\mys

Then for any $x \sim y$, there are only finitely many $n$ such that an endpoint
of a $Q^n$ marker region separates $x$ from $y$ (this follows from (2) above).
\mys


Thus, $x \sim y$ iff for all large enough $n$ we have $x \sim_{Q^n} y$. This gives a continuous
embedding into $E_0$. 
\mys


Proof can be extended to handle non-free part of $2^\Z$ as well (and likewise for 
$2^{\Z^n}$.
\end{frame}


%\subsection{Questions}


\begin{frame}
\begin{ques}
Does there exists a continuous embedding from $2^{\Z^{< \omega}}$ into $E_0$? 
Yes for free part.
\end{ques}
\mys



\begin{ques}
How far can these regular marker arguments be extended?
\end{ques}

\begin{ques}
Are there more algebraic, less geometrical, versions of these arguments?
\end{ques}
\mys

This may be important for extending these arguments further.
\end{frame}


\subsection{Technical question}

\begin{frame}


\frametitle{A Technical Question}

\begin{itemize}
\item
In the Slaman-Steel (Borel) embedding from $2^\Z$ to $E_0$, Borel marker sets
$M_0 \supseteq M_1 \supseteq \cdots$ are constructed such that 
$\bigcap_n M_n=\emptyset$.
\item
For the continuous embedding from $2^\Z$ to $E_0$ we use clopen 
marker sets (on $F(2^\Z)$) such that $|\bigcap_m M_n \cap [x] |
=0$ or $1$ for all $x \in F(2^\Z)$.
\end{itemize}
\mys



\begin{ques}
Does there exists a sequence $M_0 \supseteq M_1 \supseteq \cdots$ of relatively clopen
marker sets in $F(2^\Z)$ with $\bigcap_n M_n=\emptyset$?
\end{ques}
\end{frame}


\section{Coloring Property}

\begin{frame}
\frametitle{A Coloring Property}

This question led to the formulation of the following property.
\mys


\begin{defn}
$c \colon G \to \{ 0,1\}$ is a {\color{red} $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{Consequences}


\begin{frame}


The following connects the coloring property with 
the dynamics of the shift action.


\begin{thm}
$x \in 2^G$ is a $2$-coloring iff $\overline{[x]} \subseteq F(2^G)$.
\end{thm}
\mys


Note: Definition formulated independently by Pestov. 
\mys


Also, the $2$-coloring property for $G$ gives a {\color{red} marker compactness property}
for $F(2^G)$:
\medskip



\begin{thm}[MCP]
Suppose $G$ has the coloring property.  
Let $S_0 \supseteq S_1 \supseteq S_2 \supseteq \cdots$ be relatively closed
complete sections of $F(2^G)$. Then $\bigcap_n S_n \neq \emptyset$. 
\end{thm}
\end{frame}


\subsection{Main Theorem}


\begin{frame}


\frametitle{Main Theorem}


\begin{thm}[Gao, J, Seward]
Every countable group has the $2$-coloring property.
\end{thm}
\mys


Note: Partial results were obtained independently also by Glasner and Uspenski.
\mys


\begin{rem}
By  different arguments first showed the coloring property for 
abelian, solvable, and free groups, and for every group $G$
with $\Z \unlhd G$.
\end{rem}
\end{frame}


\begin{frame}

The proof uses {\color{red}two idea}:


\begin{itemize}
\item
Construct suitable marker regions for the group $G$.
\item
Exploit polynomial vs.\ exponential growth.
\end{itemize}
\medskip

We first describe the construction of the marker regions. 
Recall $G$ is a countable infinite group.
\end{frame}








\begin{frame}
We inductively define marker sets $\Delta_n \subseteq G$ and finite 
sets $F_n \subseteq G$ (with $1 \in F_n$). 
\medskip

The $n$th level marker regions will be the translates $gF_n$ for $g \in \Delta_n$.
\medskip


Will have:


\begin{itemize}
\item
$F_0 \subseteq F_1 \subseteq F_2 \subseteq \cdots$
\item
$\bd_0 \supseteq \bd_1 \supseteq \bd_2 \supseteq \cdots$
\end{itemize}
\medskip



Each $F_n$ region will be a union of copies of $F_i$ for $i<n$. 
\medskip

$F_n$ will be constructed inside a region $H_n$.


\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}
Will maintain two properties:
\mys

\begin{itemize}
\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}


We label the copies of $F_{n-1}$ inside of $F_n$ by 

$$
\lambda^n_1 F_{n-1},\dots, \lambda^n_{s(n)} F_{n-1}, $$

$$
\lambda^n_{s(n)+1} F_{n-1},
\lambda^n_{s(n)+2} F_{n-1},
\lambda^n_{s(n)+3} F_{n-1}.
$$
\mys



Each copy of an $F_n$ will have two  distinguished points, $a_n$ and $b_n$. 
\mys

Will have {\color{red}Marker Identification Property}:

(MIP) There is a $A_n \subseteq F_{n-1}$  such that if $c(ga)=c(a)$
for all $a \in A_n$, then $g \in \Delta_n$.

\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 b_{n-1},\dots, \bd_n \lambda^n_{s(n)} b_{n-1}$, 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}
