\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}













\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{Shift Equivalence Relations and Markers}



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



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






\date{
March, 2009\\
Gainesville Fl.}


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


\section{Introduction}

\begin{frame}
Throughout $G$ will denote a countable group, $X$ a standard Borel space.
$2^G$ is a compact Polish space. 
\medskip

We consider the {\em shift action} of $G$ on $2^G$:
\medskip

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

This is a continuous action of $G$.
\medskip


Let $F(2^G)$ denote the free part of $2^G$ under this action:
\medskip


$$
F(2^G)=\{ x \in 2^G \colon \forall g \neq 1\ g \cdot x \neq x\}.
$$
\medskip
$F(2^G)$ is a $G_\delta$ in $2^G$, so is a Polish space in the subspace topology.
\end{frame}












\begin{frame}




Recall the Feldman-Moore Theorem:




\begin{thm}
Let $E$ be a countable Borel  equivalence relation on a standard Borel space $X$. 
Then $E$ is generated by the Borel action of a countable group $G$.
\end{thm}




Thus, we can study countable equivalence relation ``group by group.'' 


Recall the simplest non-trivial equivalence relation are the hyperfinite ones:

\begin{defn} 
$E$ is hyperfinite if $E=\bigcup_n E_n$ where each $E_n$ is finite.
\end{defn}
\end{frame}




\begin{frame}
Say a group is hyperfinite if all its Borel actions are hyperfinite. 




\begin{thm}[Slaman-Steel]
$E$ is hyperfinite iff $E$ is induced by a Borel action of $\Z$.
\end{thm}
\medskip



Can study equivalence relations from several points of view:


\begin{itemize}
\item
Borel bi-reducibility
\item
Orbit equivalence
\item
Isomorphism of group actions
\end{itemize}


\end{frame}



\begin{frame}
Basic technique in study of countable group actions is the notion of \color{red}Marker sets \color{black} and
\color{red}Marker regions\color{black}. 
\medskip


We consider these notions both for equivalence relations and for groups.
\medskip
\end{frame}


\begin{frame}
\frametitle{Markers For Equivalence Relations}
Formally, a marker set is a Borel set $S \subseteq X$. By ``marker regions'' be 
mean formally a Borel finite subequivalence relation of $E$. 
\medskip

Usually we construct a sequence $S_n$ of marker sets, and $S_n$ is associated to a
marker region decomposition (note: marker regions easily give marker sets). 
\medskip


We try to get marker regions with some kind of geometric or combinatorial properties.
\end{frame}




\begin{frame}
\frametitle{Markers For Groups}
A marker set is a set $S \subseteq G$.
\medskip

Marker regions means the classes of a finite equivalence relation on $G$.
\medskip


note: Marker sets (regions) for $E(2^G)$ give Marker sets (regions) for $G$
\end{frame}






\section{Markers for equivalence relations}




\begin{frame}
If we can get marker regions that totally cohere, then this shows $E$ is hyperfinite.
\medskip


This was the original proof of the hyperfiniteness of $\Z^n$ actions. 

More precisely, this produced Borel marker regions $R_n$ which cohered and
such that $\bigcup_n R_n$ has finite index in $E$. 
\medskip


This suffices by a result of (J-Kechris-Louveau). 
\medskip



In J-Kechris-Louveau this was extended to show all finitely generated groups
of polynomial growth have hyperfinite actions. These coincide (Gromov)
with the almost nilpotent groups. 
\medskip
\end{frame}





\begin{frame}
\begin{conj}[Kechris]
The actions of an amenable group are hyperfinite.
\end{conj}




In [Boykin-J] we use ``regular'' (i.e., rectangular) marker regions in a different way 
to give another proof of the hyperfiniteness of $\Z^n$ actions. We in fact showed:


\begin{thm}[Boykin-J]
There is a continuous embedding from $2^{\Z^n}$ into $E_0$. 
\end{thm}



The new idea was to use rectangular marker regions, and make them ``anti-cohere.''
\medskip




With Gao we extended this up actions of abelian groups, but we lose continuity:



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



\end{frame}



\subsection{Continuous Embeddings}



\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$. 
\medskip



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).
\medskip

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$). 
\medskip



\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}
\medskip




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


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









\begin{frame}
Next we modify the marker regions to anti-cohere. 
\medskip



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. 
\medskip


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


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


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$. 
\medskip


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$.
\medskip


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



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.
\medskip



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



\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}
\medskip

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).
\medskip


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$. 
\medskip


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}
\medskip



\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}
\medskip

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


\section{Markers for groups}



\begin{frame}
We now turn to markers and marker regions for groups.
\medskip



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



Note that if $F(2^G)$ admits a certain marker structure, then this copies over to $G$, but
not (obviously) conversely. 
\medskip








Say $G$ admits {\em rectangular marker regions} if $G=\bigcup_n S_n$ 
such that for each $n$, $G$ is a disjoint union of translates of $S_n$. 
\medskip



\begin{ques}
Which groups admit rectangular marker structures?
\end{ques}




\end{frame}






\begin{frame}
\begin{thm}
Every abelian group admits rectangular markers.
\end{thm}



\medskip



\begin{lem}
If $K \unlhd G$, $K \leq Z(G)$, and $K$, $G/K$ admit rectangular markers, then so does $G$.
\end{lem}
\medskip




\begin{cor}
Every nilpotent group admits rectangular markers.
\end{cor}
\end{frame}






\subsection{The coloring Property}






\begin{frame}
We now turn to the topological properties of orbits by the  shift action of $G$
on $2^G$ for countable $G$. 
\medskip



\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}





\begin{frame}

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


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


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



\begin{thm}[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$. 
\end{thm}
\medskip


\begin{rem}
The MCP for $\Z$ shows we cannot get a continuous embedding from even $F(2^Z)$ into $E_0$
by constructing (as in Slaman-Steel for Borel) a decreasing set relatively
clopen marker sets $S_0 \supseteq S_1 \supseteq S_2 \supseteq \cdots$.
\end{rem}


\end{frame}




\subsection{Sketch of Proof}



\begin{frame}
\begin{thm}
Every countable group $G$ has a $2$-coloring.
\end{thm}
\medskip

The proof uses \color{red}two ideas\color{black}:


\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:
\medskip

\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}








\subsection{Construction of the $F_n$}





\begin{frame}
\frametitle{Construction of the $F_n$}



Start with $1 \in H_0 \subseteq H_1 \subseteq H_2 \subseteq \cdots$ sufficiently fact growing.
\medskip




Say,

$$
H_{n-1} (H_0^{-1} H_0) (H_1^{-1} H_1) \cdots (H_{n-1}^{-1}H_{n-1}) \subseteq H_n.
$$


Assume $F_{n-1} \subseteq H_{n-1}$ is defined. We define $F_n \subseteq H_n$.
\medskip



We interpolate between $H_{n-1}$ and $H_n$ a sequence of sets

$$
H_{n-1} \subseteq \beta(n,0) \subseteq \beta(n,1) \subseteq \cdots \subseteq \beta(n,n-1)=H_n
$$


where
\medskip
$\beta(n,r)=\{g \colon g (H_{r+1}^{-1} H_{r+1}) \cdots (H_{n-1}^{-1} H_{n-1}) \subseteq H_n\}$.




\end{frame}




\begin{frame}
Going from $F_{n-1}$ to $F_n$:
\medskip


\begin{enumerate}
\item
First put maximal disjoint collection of copies of $F_{n-1}$ inside $H_{n}=\beta(n,n-1)$. 
\item
Next put maximal disjoint collection of copies of $F_{n-2}$ inside of 
$\beta(n,n-2)-\bigcup F_{n-2}$ copies. 
\item
At step $k$, put maximal disjoint number of copies of $F_k$ inside of 
$\beta(n,k)- \bigcup$ previous $F_{k+1},\dots, F_{n-1}$ copies.
\end{enumerate}
\end{frame}




\newlength{\ml}
\setlength{\ml}{0.5mm}





\begin{frame}
\begin{figure}[h]
\begin{center}
\setlength{\unitlength}{1mm}

\begin{picture}(150,100)(-50,-60)
\thicklines


\put(0,0){\oval(30,20)}
\put(0,0){\circle{15}}
\color{red}
\thinlines
\put(0,0){\oval(50,40)}
\put(0,0){\oval(70,60)}
\thicklines
\color{black}
\put(0,0){\oval(90,80)}








\put(-52,0){$H_n$}
\put(-3,-1){$F_{n-1}$}







\end{picture}
\end{center}
\end{figure}







\end{frame}




\begin{frame}
\begin{figure}[h]
\begin{center}
\setlength{\unitlength}{1mm}

\begin{picture}(150,100)(-50,-60)
\thicklines


\put(0,0){\oval(30,20)}
\put(0,0){\circle{15}}
\color{red}
\thinlines
\put(0,0){\oval(50,40)}
\put(0,0){\oval(70,60)}
\thicklines
\color{black}
\put(0,0){\oval(90,80)}







\put(0,32){\circle* {15}}
\put(17,25){\circle*{15}}
\put(35,30){\circle*{15}}
\put(-17,30){\circle*{15}}
\put(-33,24){\circle*{15}}
\put(-10,13){\circle*{15}}
\put(-30,5){\circle*{15}}
\put(-35,-15){\circle*{15}}
\put(-14,-14){\circle*{15}}
\put(-30,-30){\circle*{15}}
\put(-5,-28){\circle*{15}}
\put(20,-28){\circle*{15}}
\put(12,-13){\circle*{15}}
\put(17,8){\circle*{15}}
\put(36,10){\circle*{15}}
\put(34,-13){\circle*{15}}







\color{black}
\put(-52,0){$H_n$}
\put(-3,-1){$F_{n-1}$}







\end{picture}
\end{center}
\end{figure}







\end{frame}





\begin{frame}
\begin{figure}[h]
\begin{center}
\setlength{\unitlength}{1mm}

\begin{picture}(150,100)(-50,-60)
\thicklines


\put(0,0){\oval(30,20)}
\put(0,0){\circle{15}}
\color{red}
\thinlines
\put(0,0){\oval(50,40)}
\put(0,0){\oval(70,60)}
\thicklines
\color{black}
\put(0,0){\oval(90,80)}







\put(0,32){\circle* {15}}
\put(17,25){\circle*{15}}
\put(35,30){\circle*{15}}
\put(-17,30){\circle*{15}}
\put(-33,24){\circle*{15}}
\put(-10,13){\circle*{15}}
\put(-30,5){\circle*{15}}
\put(-35,-15){\circle*{15}}
\put(-14,-14){\circle*{15}}
\put(-30,-30){\circle*{15}}
\put(-5,-28){\circle*{15}}
\put(20,-28){\circle*{15}}
\put(12,-13){\circle*{15}}
\put(17,8){\circle*{15}}
\put(36,10){\circle*{15}}
\put(34,-13){\circle*{15}}






\put(-22,18){\circle*{8}}
\put(-25,-7){\circle*{8}}
\put(-17,0){\circle*{8}}
\put(-18,-26){\circle*{8}}
\put(-1,-15){\circle*{8}}
\put(8,-25){\circle*{8}}
\put(25,-2){\circle*{8}}
\put(28,20){\circle*{8}}
\put(3,18){\circle*{8}}






\color{black}
\put(-52,0){$H_n$}
\put(-3,-1){$F_{n-1}$}







\end{picture}
\end{center}
\end{figure}







\end{frame}





\begin{frame}
\begin{figure}[h]
\begin{center}
\setlength{\unitlength}{1mm}

\begin{picture}(150,100)(-50,-60)
\thicklines


\put(0,0){\oval(30,20)}
\put(0,0){\circle{15}}
\color{red}
\thinlines
\put(0,0){\oval(50,40)}
\put(0,0){\oval(70,60)}
\thicklines
\color{black}
\put(0,0){\oval(90,80)}







\put(0,32){\circle* {15}}
\put(17,25){\circle*{15}}
\put(35,30){\circle*{15}}
\put(-17,30){\circle*{15}}
\put(-33,24){\circle*{15}}
\put(-10,13){\circle*{15}}
\put(-30,5){\circle*{15}}
\put(-35,-15){\circle*{15}}
\put(-14,-14){\circle*{15}}
\put(-30,-30){\circle*{15}}
\put(-5,-28){\circle*{15}}
\put(20,-28){\circle*{15}}
\put(12,-13){\circle*{15}}
\put(17,8){\circle*{15}}
\put(36,10){\circle*{15}}
\put(34,-13){\circle*{15}}






\put(-22,18){\circle*{8}}
\put(-25,-7){\circle*{8}}
\put(-17,0){\circle*{8}}
\put(-18,-26){\circle*{8}}
\put(-1,-15){\circle*{8}}
\put(8,-25){\circle*{8}}
\put(25,-2){\circle*{8}}
\put(28,20){\circle*{8}}
\put(3,18){\circle*{8}}





\put(-19,7){\circle*{4}}
\put(-21,11){\circle*{4}}
\put(-11,-4){\circle*{4}}
\put(-10,2){\circle*{4}}
\put(-6,-8){\circle*{4}}
\put(11,-2){\circle*{4}}
\put(17,-3){\circle*{4}}
\put(21,-8){\circle*{4}}
\put(22,-14){\circle*{4}}
\put(1,10){\circle*{4}}
\put(6,9){\circle*{4}}
\put(11,17){\circle*{4}}
\put(8,13){\circle*{4}}
\put(2.5,-9.5){\circle*{4}}

\color{black}
\put(-52,0){$H_n$}
\put(-3,-1){$F_{n-1}$}







\end{picture}
\end{center}
\end{figure}

\end{frame}











\begin{frame}

\color{red}Main Point: 
\color{black}
If a copy of $F_k$ meets a copy of $F_l$, $l>k$, then it must
meet a copy of $F_k$ inside $F_l$.
\bigskip


This guarantees the copies of $F_k$ are maximally disjoint in $G$. 
\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}.
$$
\medskip



Each copy of an $F_n$ will have two  distinguished points, $a_k$ and $b_k$. 
\medskip

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

(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{Defining 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}



\section{Tentative Results}


\begin{frame}
\frametitle{Some Tentative Results}

\begin{thm}
The set of $x \in 2^G$ with $\overline{[x]} \subseteq F(2^G)$ is $\bp^0_3$-complete.
\end{thm}




\begin{thm}
The set of $x \in 2^G$ with $\overline{[x]} \subseteq  F(2^G)$ and minimal is 
$\bp^0_3$-complete.
\end{thm}







\end{frame}













\end{document}