\documentclass{beamer}\usepackage{beamerthemesplit}

\usepackage{amsmath}
\usepackage{amssymb}
\usepackage[all]{xy}



\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{\ww}{{\omega^\omega}}


\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}{\mathsf{id}}
\newcommand{\lecc}{\text{lecc}}








\begin{document}


\setbeamercovered{dynamic}

\title{A $\bp^0_3$ Completeness Phenomenon in Group Actions}



\author{S.\ Jackson}



\institute{
Joint with {\color{red}S.\ Gao} and {\color{red}B.\ Seward} \\[10pt]
Department of Mathematics\\
University of North Texas\\
%jackson@unt.edu
}






\date{
November, 2009\\
Urbana, Illinois}


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





\section{Introduction}



\begin{frame}
Let $X$ be a Polish space and $G$ a countable group.
\mys


Let $(g,x) \mapsto g \cdot x$ be a Borel action of $G$ on $X$. 
\mys



The groups action induces a countable Borel equivalence relation 
$\sim$ on $X$:

$$
x \sim y \text{ iff } \exists g \in G\ ( g \cdot x =y)
$$

\begin{thm}[Feldman-Moore]
Every countable Borel equivalence relation is induced by the action
of a countable group.
\end{thm}


\end{frame}



\begin{frame}
For $G$ a countable group, the space $2^G$ is a compact Polish space.
\mys

$G$ acts on $2^G$ by the {\color{red} shift-action}:


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




This is a continuous action of $G$ on the space $X=2^G$. 





\end{frame}








\begin{frame}
A notion of complexity is provided by the following notion of 
reduction:


\begin{defn}
$(X,E) \leq (Y,F)$ if there is a Borel function $f \colon X \to Y$
such that 
$$(x_1\,  E\,  x_2) \leftrightarrow (f(x_1)\,  F\,  f(x_2)).$$
\end{defn}



The simplest equivalence relations are the {\color{red} smooth} or {\color{red}tame}
relations:


\begin{defn}
$(X,E)$ is smooth if $(X,E) \leq (Y, =)=\id$. 
\end{defn}
\mys


Being smooth for a countable Borel equivalence relation is equivalent to having
a Borel {\color{red}selector}.
\end{frame}



\begin{frame}
By Silver dichotomy, $\id \leq (X,E)$ for any Borel equivalence relation $E$
on an uncountable Polish space $X$.
\mys


\begin{defn}
$E_0$ on $\ww$ (or $2^\omega$) is defined by:

$$
(x \, E_0 \, y) \leftrightarrow \forall^* n\ (x(n)=y(n))
$$
\end{defn}
\mys

By the {\color{red}Harrington-Kechris-Louveau} dichotomy, 
for any Borel equivalence relation $E$, either $E \leq \id$ or 
$E_0 \leq E$.
\end{frame}


\begin{frame}
The Countable Borel equivalence relations $E \leq E_0$ are exactly the 
{\color{red}hyperfinite} relations.
\mys


\begin{defn}
$E$ is hyperfinite if $E$ can be written as an increasing unions 
$E=\bigcup_n E_n$ where each $E_n$ is a {\color{red} finite}
Borel equivalence relation.
\end{defn}


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

\begin{itemize}
\item
$E$ is hyperfinite.
\item
$E \leq E_0$.
\item
The (infinite) $E$ classes can be uniformly $\Z$-ordered in a Borel manner.
\end{itemize}
\end{thm}


\end{frame}



\begin{frame}
We say the countable group $G$ is hyperfinite if all its Borel actions
are hyperfinite.
\mys


\begin{ques}
Which groups are hyperfinite?
\end{ques}
\mys


$\Z$ is hyperfinite by Slaman-Steel.
\mys


\begin{thm}[Weiss]
Each $\Z^n$ is hyperfinite.
\end{thm}


\begin{thm}[Gao-J]
All countable abelian groups are hyperfinite.
\end{thm}
\end{frame}


\begin{frame}
If every action of $G$ is hyperfinite, then $G$ must be amenable.
\mys



\begin{conj}[Kechris]
Every amenable group is hyperfinite.
\end{conj}
\mys





\begin{fact}
For $G=F_2$, the shift action of $G$ on $2^G$ is a universal 
countable Borel equivalence relation.
\end{fact}
\mys





Also, the shift action of $G$ on $\R^G$ is universal for the Borel actions of $G$.
\end{frame}


\section{Dynamics of the Shift Action}






\begin{frame}
For $x \in 2^G$, let $[x]$ denote the equivalence class of $x$ under the shift
action of $G$ on $X=2^G$. 
\mys



Let $F\subseteq X$ denote the {\color{red} free part} of $2^G$, that is.

$$
x \in F \leftrightarrow \forall g \neq 1\ (g \cdot x \neq x).
$$
\mys


$F$ is a (dense) $G_\delta$ in $X$, so $F$ is a Polish space in the subspace topology.
\mys




\end{frame}



\begin{frame}

\frametitle{Free Orbit Closures}

We say $x \in F$ has {\color{red} free orbit closure} if $\overline{[x]} \subseteq F$. 
\mys

The following definition was formulated independently by Glasner and Uspensky.
\mys



\begin{defn}
A {\color{red} $2$-coloring} on a countable group $G$ is a $c \colon G \to \{ 0,1\}$
satisfying:

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


\end{frame}


\begin{frame}
\begin{thm}
The following are equivalent.

\begin{itemize}
\item
$x \in 2^G$ has free orbit closure.
\item
$x$ is a $2$-coloring of $G$.
\item
If $M_0 \supseteq M_1 \supseteq M_2 \supseteq \cdots$ are relatively closed 
subsets of $F$ with $M_i \cap [x] \neq \emptyset$ for all $i$, then 
$\bigcap_i M_i \neq \emptyset$.
\end{itemize}
\end{thm}
\mys


\begin{cor}
If $G$ has a $2$-coloring, then every decreasing sequence $\{ M_i \}$ 
of relatively closed, complete sections of $F$ has a non-empty intersection. 
\end{cor}
\end{frame}



\begin{frame}
\frametitle{sketch of proof}

Suppose $x \in 2^G$ is a $2$-coloring. Suppose $y=\lim_n g^{-1}_n \cdot x  \in \overline{[x]}$.
\mys



Let $1 \neq s \in G$, we show $s^{-1} \cdot y \neq y$. 
\mys

Let $T \in G^{<\omega}$ be as in the
definition of $2$-coloring. Let $n$ be large enough so that 
$y$ and $g^{-1}_n \cdot x$ agree on $T\cup sT$. Let $t \in T$ be such that 
$x(g_n t) \neq x(g_n s t)$. Then:


$$
s^{-1}\cdot y (t)= y(st) = g^{-1}_n \cdot x (st)= x(g_n st)\neq x(g_n t)
=g_n^{-1}\cdot x (t) =y(t)
$$
\medskip


So, $\overline{[x]} \subseteq F$.
\end{frame}


\begin{frame}

Suppose $\overline{[x]} \subseteq F$. Let $s \in G$. Let $T_n$ be the first $n$ group elements. 
\mys


If $T_n$ doesn't work for $s$, let $g_n \in G$ be a counterexample. 
So, $x(g_n t)=x(g_n s t)$ for all $t \in T_n$. 
\mys



Let $y$ be a limit of $\{ g_n^{-1} \cdot x\}$, (w.l.o.g.) $y= \lim_n g_n^{-1} \cdot x \in F$.
\mys


But, for any $t \in G$ we have (for large enough $n$, $t \in T_n$):


$$
s^{-1}\cdot y(t)= y(st)= g_n^{-1} \cdot x (st)= x(g_n st)
=x(g_n t)= g_n^{-1}\cdot x (t)= y(t).
$$

This contradicts $y \in F$. 
\end{frame}




\begin{frame}
\begin{thm}
Every countable group $G$ has the $2$-coloring property.
\end{thm}
\mys


The proof uses a construction of certain ``marker set'' 
for an arbitrary group $G$ that we will also use in our
result here.
\end{frame}

\begin{frame}
\frametitle{Marker Sets and Regions}

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

A {\color{red}marker set} for $E$ is a 
Borel set $M \subseteq X$ such that $M \cap [x] \neq \emptyset$
for all $x \in X$. 
\mys

We say $M$ is a marker set for the marker regions $R$
if $| M \cap [x]_R|=1$ for all $x \in X$. 
\end{frame}

\begin{frame}


For $G$ a countable group, a set of marker regions is a finite 
subequivalence relation $R$ of $G$.
\mys


A marker set is a non-empty $M \subseteq G$. 
\mys

We say $R$ is a {\color{red}tiling} of $G$ if there is a finite $F \subseteq G$
such that each $R$ class is of the form $x F$.
\mys

{\color{blue}Note}: Marker regions and sets for $E$ give 
marker regions and sets for $G$ (for free action).
\end{frame}


\begin{frame}
\begin{defn}
A sequence $(\Delta_n, F_n)$ of tilings of $G$ is {\color{red}coherent}
if each class $\delta F_n$ of $R_n$ is contained in a class $\delta' F_{n+1}$ of $R_{n+1}$.
We say the sequence is {\color{red}cofinal} if every finite subset of $G$
is contained in some $R_n$ class. We say it is {\color{red}centered} 
if $1 \in \Delta_n$, $1 \in F_n$ for all $n$. 
\end{defn}


\begin{defn}
$G$ is a {\color{red}c.c.c.\ group} if it has a coherent, cofinal, centered tiling.
\end{defn}



\begin{rem}
There is no loss of generality in assuming the tilings are centered.
In this case $F_n \subseteq F_{n+1}$.
\end{rem}

\end{frame}


\begin{frame}
\begin{ques}
Which groups are c.c.c.\ groups?
\end{ques}


\begin{thm}
Every nilpotent and every solvable group with finitely generated quotients
is c.c.c.\ Every free product of non-trivial groups is c.c.c.\
\end{thm}
\mys

Is every solvable group c.c.c.? Is there a non-c.c.c.\ group?
\end{frame}






\begin{frame}
\frametitle{Minimal flows}

\begin{defn}
$x \in 2^G$ is {\color{red}minimal} if whenever $y \in \overline{[x]}$ then 
$\overline{[y]}=\overline{[x]}$. 
\end{defn}
\mys

We give a combinatorial reformulation of minimality.


\begin{lem}
$x$ is minimal iff for all $A \in G^{< \omega}$ there is a $T \in G^{<\omega}$
such that:

$$
\forall g \in G\ \exists t \in T\ \forall a \in A\ 
(x(a)=x(gta)).
$$
\end{lem}
\end{frame}

\section{Main Result}

\begin{frame}
For $G$ a countable group, a straightforward computation gives:
\mys

\begin{fact}
The set of $x \in 2^G$ which are $2$-colorings of $G$ is $\bp^0_3$.
\end{fact}


\begin{fact}
The set of $x \in 2^G$ which are minimal is $\bp^0_3$.
\end{fact}
\mys

So, the set of minimal $2$-colorings is also $\bp^0_3$.
\mys


\begin{ques}
When are these sets $\bp^0_3$-complete?
\end{ques}

\end{frame}


\begin{frame}
It is fairly easy to see that the set of $2$-colorings is $\bs^0_2$-hard,
and the set of minimal colorings is $\bp^0_3$-complete.
\mys


\begin{rem}
The set of $2$-colorings is meager, in fact, the set of colorings that 
``block'' a particular $s \neq 1$ is meager. It is also dense,
so it cannot be $\bp^0_2$. 
\end{rem}


\begin{rem}
The $\bp^0_3$-completeness of the minimal colorings follows from 
our general marker region construction by a similar but easier 
argument to the main result. 
\end{rem}
\end{frame}



\begin{frame}
\frametitle{Main Result}


\begin{defn}
$G$ is a {\color{red}flecc} group if there is a finite $A \subseteq G$
such that for all $1 \neq g \in G$, there is an $h \in G$ and $i \in \omega$
such that $h g^i h^{-1} \in A-\{ 1\}$.
\end{defn}
\mys


The following is our main result.
\mys


\begin{thm}
The set of $2$-colorings is $\bp^0_3$-complete  iff $G$ is not a flecc group.
If $G$ is a flecc group, the the set of $2$-colorings is $\bs^0_2$.
\end{thm}
\end{frame}


\subsection{flecc groups}

\begin{frame}
\frametitle{flecc groups}

\begin{defn}
The {\color{red}limit extended conjugacy class} of $g \in G$ is 

$$
\lecc(g)=\bigcap_n \{ h g^{n i} h^{-1} \colon h \in G, i \geq 1\}
$$

\noindent
for $g$ of infinite order, and for $g$ of finite order, every 
conjugacy class of any $g^k$ where $g^k$ has prime power order is a 
$\lecc$ of $g$.
\end{defn}


\begin{fact}
If $\lecc(g_1) \cap \lecc(g_2)\neq \emptyset$, then $\lecc(g_1)=\lecc(g_2)$.
\end{fact}

\begin{thm}
$G$ is a flecc group iff $G$ has only finitely many $\lecc$ classes.
\end{thm}


\end{frame}



\begin{frame}
\begin{ex}
Every quasi-cyclic group $\Z_{p^\infty}$ is a flecc group.
\end{ex}

\begin{fact}
Every abelian flecc group is a torsion group. 
\end{fact}


\begin{fact}
Any infinite sum of non-trivial groups is not a flecc group.
\end{fact}




\begin{thm}
An abelian group is a flecc group iff it is a finite sum of 
quasicyclic groups and  reduced $p$-groups each with finitely many elements of order $p$.
\end{thm}
\end{frame}



\begin{frame}
\begin{cor}
The collection of abelian flecc groups is closed under products.
\end{cor}

\begin{ques}
Are the flecc groups closed under products?
\end{ques}


\begin{fact}
The collection of flecc groups is not closed under quotients or subgroups. 
\end{fact}

For the first, take a (Zippin) group $G=\langle x, y_1,y_2,\dots\rangle$
where $y_i^p=x$, $x^p=1$.
\medskip

For the second, use the fact that every torsion-free group is a subgroup of a group
$G$ with $2$ conjugacy classes (and so only finitely many $\lecc$ classes).
So, every torsion-free group is a subgroup of a $\lecc$ group.
\end{frame}



\begin{frame}
Proof that $G$ is flecc implies the set of $2$-colorings is $\bs^0_2$. 
\mys


\begin{fact}

\begin{itemize}
\item
If $T$ blocks the element $s^i$, then $s$ is blocked by 
$T \cup sT \cup \cdots \cup s^{i-1} T$.
\item
If $T$ blocks $s$, then $hsh^{-1}$ is blocked by $hT$.
\end{itemize}
\end{fact}


Let  $G$ be flecc, and $A$  as in the definition of flecc. 
For each $s \in A$, let $T_s$ block $s$. By the above facts, there is a finite $T$
which blocks all $s \in G$. 

So, $x$ is a $2$-coloring of $G$ iff 
$$\exists T\  \forall s \neq 1\ \in G^{<\omega}\ 
\forall g \in G\ (\exists  t \in T \ x(gt) \neq x(gst)).$$

\end{frame}






































\subsection{Marker Regions for General G}

\begin{frame}
We construct marker regions (partial tilings) $(\Delta_n, F_n)$ 
for a general countable group $G$.
\mys

We have the following properties:


\begin{itemize}
\item
$1 \in F_0 \subseteq F_1 \subseteq F_2 \subseteq \cdots$.
\item
$\Delta_0 \supseteq \Delta_1 \supseteq \Delta_2 \supseteq \cdots$, $1 \in \Delta_n$.
\item
The $\Delta_n$ translates of $F_n$ are maximally disjoint in $G$.
\item
$F_n$ is a disjoint union of copies of $F_{n-1},\dots, F_0$. 
\item
The copies $\gamma \Delta_k$, $k <n$ which intersect a copy $\delta \Delta_n$
of $F_n$ are exactly those of the form $\delta \eta F_k$
where $\eta \in F_n \cap \Delta_k$. 
\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]{$F_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}

















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

The $a_n$ will be used to establish a {\color{red}
marker identification property}.
\mys


The $b_n$ will be free points used to make the coloring have desired 
properties (e.g., be a $2$-coloring).
\mys


{\color{red}Marker Identification Property}:
There is a finite $A_n \subseteq G$ such that 
$\forall a \in A (c(ga)=c(a))$ iff $g \in \Delta_n$.
\mys


\begin{fact}
For any $A \in G^{<\omega}$ and coloring $c_A$ of $A$ with $c_A(1)=1$, 
there is an $F_0 \supseteq A$ 
and $a_0, b_0 \in F_0$ and a coloring $c_{F_0}$ of $F_0-\{ a_0, b_0\}$ 
extending $c_A$ with the following identification property:
\medskip


For any $\Delta_0 \subseteq G$ such that $\{ \delta_0 F_0 \colon
\delta_0 \in \Delta_0\}$ is pairwise disjoint, and any 
coloring $c \in 2^G$ extending the union of the $c_{F_0}$
copied to the translates $\delta_0 F_0$ (and $c=0$ off this union),
$c$ has the m.i.p.\ (using $F_0$).
\end{fact}
\end{frame}

\begin{frame}
\frametitle{Construction of $F_0$}

Given $A \in G^{<\omega}$ and $c_A \colon A \to \{ 0,1\}$.
\mys

Pick any distinct $a_0, b_0,x,y \notin A$.
Let $B_2=A \cup \{ a_0,b_0,x,y\}$
\mys


Let $z \notin (B_2B_2^{-1} \cup B_2 B_2)$.
Let $B_3=B_2 \cup \{ z\}$. 
\mys

Let $F_0= B_3B_3$. Let $c_{F_0}(x)=c_{F_0}(y)=c_{F_0}(z)=1=c_A(1)$.
Let $c_{F_0}=0$ on $F_0-B_3$. 
\mys


This works.
\end{frame}

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

\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]{{\color{red}$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]{{\color{red}$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}

\end{center}
\end{figure}
\end{frame}


\begin{frame}
To get a $2$-coloring use the fact that there are 
{\color{red}exponentially} many ($2^{\lambda_n}\sim 2^{|H_n|}$)
choices for the color of the $b_i$ in $F_n$ but only 
{\color{red}polynomially} many colors to avoid
(about $|H_n|^5$).
\mys


Given $g$, $gs$ with $s \in H_n$, by maximal disjointness of the $H_n$
find $\gamma \in F_n F_n^{-1}$ such that $g \gamma \in \Delta_n$. 
Then 

$$
gs\gamma=g\gamma (\gamma^{-1} s \gamma)
$$

where $\gamma^{-1} s \gamma \in H_n^5$.

\end{frame}




\begin{frame}
\frametitle{The $\bp^0_3$ Construction}

Suppose $G$ is not a flecc group. Let $z \in 2^G$ be a $2$-coloring
as constructed. 
\mys


For each $k$, let $s_k$ be such that $h s_k^{\ell} h^{-1} \notin H_k$ 
for all $h \in G$ and all $\ell$ such that $s_k^{\ell} \neq 1$.
Also, $s_k \notin F_k F_k^{-1}$. 
\mys



We construct for each $k$ another auxiliary $x_k \in 2^G$:


\begin{itemize}
\item
$x_k$ will have period $s_k^{-1}$ (i.e., $x_k(g)=x_k(s_k g)$).
\item
$x_k$ will have the $2$-coloring property for first $k$-many shifts.
\item
$x_k$ will be $0$ off of a maximal disjoint collection of copies of $F_k$.
It will follow the basic construction and so will the marker identification
property for these copies.
\end{itemize}




\end{frame}



\begin{frame}
\frametitle{The Reduction}

Let $P \subseteq 2^{\omega\times \omega}$ be defined by:

$$
\alpha \in P \leftrightarrow \forall k\ \exists m\ \forall m >n\
\alpha(k,n)=0.
$$


For $u \in 2^{n \times n}$ we define a partial coloring $c_u$ of $G$,
and then take $$f(\alpha)= \bigcup_n c_{\alpha \res n}$$
for our reduction function.
\mys


For each $n$, let $k=k(n)$ be least such that $\alpha(k,n)=1$
(take $n$ if no such $k$).
\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(1, 4){\oval(1,2)}
\put(4, 4){\oval(1.5, 3)}
\put(8,4){\oval(2,4)}

\put(0.5, 2.5){$K_{0,k(0)}$}
\put(3.5, 2){$K_{1,k(1)}$}
\put(7.5,1.5){$K_{n,k(n)}$}
\put(7.5,4){{\color{red}use} $x_k$}

\put(6,7){{\color{red}use} $z$}


\end{picture}

\end{center}
\end{figure}




\end{frame}





























\end{document}