\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{\bas}{\bar{s}}
\newcommand{\bag}{\bar{g}}


\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{\sR}{\mathcal{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}



\newcommand{\lh}{\text{lh}}
\newcommand{\mys}{\medskip}
\newcommand{\id}{\mathsf{id}}
\newcommand{\lecc}{\text{lecc}}
\newcommand{\ecc}{\text{ecc}}
\newcommand{\dom}{\text{dom}}


\newcommand{\ncl}[2]{\overline{#2}^{#1}}
\newcommand{\conc}{{}^\smallfrown}
\newcommand{\supp}{\text{supp}}
\newcommand{\fp}{\otimes}




\begin{document}


\setbeamercovered{dynamic}

\title{Colorings and Supercolorings on Countable Groups}



\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{
December 2011\\
Paris}


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





\section{Introduction}
\begin{frame}
We consider the {\color{red} shift action} of a countable group $G$ on the compact Polish space
$X=2^G$. 

\[
g\cdot x(h)=x(g^{-1}h)
\]


This is a continuous action of $G$ on the space $2^G$. Let $[x]$ denote the orbit of $x$
under this action. 
\medskip


We let $F(2^G)$ denote the 
{\color{red}free part} of the space: 

\[
x \in F(2^G) \Leftrightarrow \forall g \neq 1_G\ (g\cdot x \neq x)
\]


$F(2^G)$ is an invariant $G_\delta$ in $X$.
\end{frame}



\begin{frame}
A {\color{red}subflow} means a closed invariant subset of $2^G$. 
Every orbit closure $[x]$ is a subflow.
\medskip


We say a subflow $S \subseteq 2^G$ is a {\color{red} free subflow} if $S \subseteq F(2^G)$. 
\medskip


We say $S$ is a {\color{red}minimal} subflow if $S$ does not properly contain any subflows. 
So, $S=\overline{[x]}$ for all $x \in A$. 
\medskip


We say $x,y \in 2^G$ are {\color{red} orthogonal}, $x \perp y$ if 
$\overline{[x]} \cap \overline{[y]} =\emptyset$. 
\end{frame}


\section{Group Colorings}


\begin{frame}
\frametitle{2-colorings}


\begin{defn}
A {\color{red}$2$-coloring} of a group $G$ is an $x\colon G\to \{0,1\}$ 
satisfying the following: for every $s \neq 1_G$, there is a finite $T=T(s) \subseteq G$
such that: 
\[
\forall g \in G\ \exists t \in T\ (x(gt)\neq x(gst)).
\]
\end{defn}

\begin{center}
\begin{tikzpicture}

\draw (0,0) ellipse (5 and 1.8);

\filldraw [black]  (-3,-0.5) circle (1pt);

\filldraw [black] (0.5,-0.5) circle (1pt);
\filldraw [black] (1.5,-0.5) circle (1pt);
\filldraw [red] (1.0,0.5) circle (1pt);
\filldraw [green] (2.0,0.5) circle (1pt);


\draw [->>] (0.5,-0.5) .. controls (0.5,-0.2) and (0.7,0.3) .. (0.9,0.45);
\draw [->>] (1.5,-0.5) .. controls (1.5,-0.2) and (1.7,0.3) .. (1.9,0.45);

\draw (-3.1,-0.5) node[anchor=east]  {$1_G$};

\draw (0.5,-0.5) node[anchor=north] {$g$};
\draw (1.5,-0.5) node[anchor=north] {$gs$};
\draw (1.0,0.5) node[anchor=south] {$gt$};
\draw (2.0,0.5) node[anchor=south] {$gst$};
\draw (0.5,-0.5)-- (1.5,-0.5);


\end{tikzpicture}
\end{center}



\end{frame}


\begin{frame}
\begin{rem}
The notion of $2$-coloring is due to GJS and independently to Glasner-Uspensky.
\end{rem}

\medskip
The significance of $2$-colorings is contained in the following.
\medskip


\begin{thm} [GJS; independently Glasner, Uspensky]
$x\in 2^G$ is a $2$-coloring iff $\overline{[x]} \subseteq F(2^G)$.
\end{thm}




\end{frame}


\begin{frame}


{\color{blue}Proof:}

Suppose $x \in 2^G$ is a $2$-coloring. We show that $\overline{[x]}\subseteq F(2^G)$. 
\medskip

Suppose $y=\lim g_n^{-1}\cdot x \in \overline{[x]}$, and let $s \neq 1_G$. 
Let $T=T(s)$ be as in a $2$-coloring. Let $n$ be large enough so that 
$y \res T\cup sT=g_n^{-1}\cdot x\res T\cup sT$. 
\medskip


Let $t \in T$ be such that 
$x(g_ns)\neq x(g_n st)$. Then $y(t)=x(g_nt)\neq 
x(g_nst)= y(st)=s^{-1}\cdot y (t)$. 
\medskip


So, $y \in F(2^G)$.
\medskip



\end{frame}




\begin{frame}
Suppose next that $\overline{[x]} \subseteq F(2^G)$.
\medskip


Let $s \neq 1_G$. For $y \in \overline{[x]}$ let $t(y) \in G$ be least such that 
$y(t)\neq s^{-1}\cdot y(t)=y(st)$. The map $y \mapsto t(y)$ is continuous from 
$\overline{[x]}$ to $G$. 
\medskip


By compactness of $\overline{[x]}$ there is a finite $T \subseteq G$ containing
the range of this map on $\overline{[x]}$. 
\medskip


In particular, this $T$ works for all $y=g^{-1}\cdot x \in [x]$, and this shows that $x$
is a $2$-coloring: for all $g\in G$ there is a $t \in T$ such that


\[
x(gt)=g^{-1}\cdot x (t) \neq s^{-1}\cdot g^{-1}\cdot x(t) = x(gst)
\]
\qedsymbol
\end{frame}



\begin{frame}
The construction of a $2$-coloring involves putting a new kind of marker structure on 
an arbitrary countable group. 

\begin{ques}
What kinds of marker structures can we put on arbitrary groups. 
What about special families of groups?
\end{ques}

By an abstract marker structure $(\Delta,\sR)$ on $G$ we mean:
\begin{itemize}
\item
$\sR=\{ R\}$ is a pairwise disjoint collection of subsets of $G$ (``marker regions'').
\item
For each $R \in \sR$, $|\Delta \cap R|=1$ ($\Delta$ is the ``marker points'').
\item
$\cup \{ \delta_R^{-1}R \colon R\in \sR\}$ is finite, where $\{ \delta_R\}
=\Delta \cap R$.
\end{itemize}

\end{frame}



\begin{frame}
\frametitle{Special Marker Structures}

We call a marker structure $(\Delta,\sR)$:
\begin{itemize}
\item
{\color{red}regular} if there is a single $F \subseteq G$ such that 
$R=\delta_R F$ for all $R \in \sR$.
\item
{\color{red}centered} if $1_G \in \Delta$.
\item
{\color{red}total} if $\cup \sR=G$.
\end{itemize}


We usually represent regular structures as $(\Delta,F$).
\medskip


We say $(\Delta,F)$ is a {\color{red}tiling} if it is regular and total.
\medskip
\end{frame}


\begin{frame}
We say a sequence $(\Delta_n,\sR_n)$ of marker structures is:
\begin{itemize}
\item
{\color{red}coherent} if whenever $k \leq n$, $R_k \in \sR_k$, $r_n \in \sR_n$, and
$R_k \cap R_n \neq \emptyset$, then $R_k \subseteq R_n$.
\item
{\color{red}cofinal} if for every finite $A \subseteq \cup_n \cup \sR_n$
we have that for large enough $m$ that $A \subseteq R_m$ for some $R_m \in \sR_m$.
\item
{\color{red}centered} if $1_G \in \Delta_n$ for all $n$.
\end{itemize}
\medskip

For centered regular $(\Delta_n,F_n)$, being cofinal is equivalent to:
for finite $A \subseteq \cup_n \cup \Delta_n F_n$ we have 
$A \subseteq F_n$ for $n$ large enough (since wlog $1_G \in A$). 
\end{frame}





\begin{frame}
\begin{defn}[Weiss]
$G$ is {\color{red}MT} (monotilable) if it has a cofinal sequence of tilings.
\end{defn}



\begin{defn}[GJS]
$G$ ic {\color{red}ccc} if it has a coherent, cofinal, centered sequence of tilings.
\end{defn}
\medskip


Weiss showed all solvable and resiidually finite groups are MT, and this class is closed under
group extensions.
\medskip

We showed that all nilpotent and polycyclic groups (solvable with finitely
generated quotients) are ccc. 
\medskip


We have no examples on non-ccc groups.
\end{frame}



\begin{frame}
\begin{rem}
Every tiling $(\Delta,F)$ has a presentation as a centered tiling, so $G$ is ccc
iff it has a coherent, cofinal sequence of tilings.
\end{rem}
\medskip


In hyperfiniteness proofs we deal with total, but not regular marker structures.
\medskip

In the coloring theory of group actions we deal with 
regular, but not total structures.
\medskip

\begin{rem}
The above definitions extend in a natural way to equivalence relations in place
of groups. Note that the existence of a type of marker structure on an equivalence
relation generated by a free action of $G$ implies one on $G$.
\end{rem}
\end{frame}


\begin{frame}

\begin{thm}
Every countable group $G$ has a $2$-coloring. In fact, there is a perfect set of
pairwise orthogonal $2$-colorings on $G$. 
\end{thm}
\medskip

So, every shift action of $G$ on $2^G$ has a perfect set of pairwise disjoint free
subflows.
\medskip


The set of $2$-colorings is also dense in $2^G$. 
\medskip

The construction of a $2$-coloring involves constructing a sequence 
$(\Delta_n,F_n)$ of regular, coherent, centered marker structures. 
\end{frame}


\begin{frame}
We construct a sequence $(\Delta_n,F_n)$ of regular marker structures which are 
coherent, cofinal, and centered. 
\medskip


We will have $F_0 \subseteq F_1 \subseteq \cdots$ and 
$\Delta_0 \supseteq \Delta_1 \supseteq \cdots$
\medskip

Main Properties:
\begin{itemize}
\item
(coherence) If $k \leq n$ and $\psi F_k \cap \gamma F_n \neq \emptyset$, then 
$\psi F_k \subseteq \gamma F_n$ (here $\psi_k \in \Delta_k$, $\gamma \in \Delta_n$).
\item
(uniformity) If $k<n$ and $\gamma, \sigma \in \Delta_n$, then 
$\gamma^{-1}(\Delta_k \cap \gamma F_n)=\sigma^{-1}(\Delta_k \cap \sigma F_n)$.
\item
(maximal disjointness) For each $n$, $\{ \delta F_n \colon \delta \in \Delta_n\}$
is a maximal disjoint collection of copies of $F_n$
\end{itemize}
\medskip


Each $F_n$ region will be a union of copies of $F_i$ for $i<n$.
\end{frame}



\begin{frame} 
$F_n$ will be constructed inside a region $H_n$. The $H_n$ grow sufficiently fast:

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


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}


\begin{frame}
\begin{center}
\begin{tikzpicture}[scale=0.1]




\draw [rounded corners] (-30/2,-20/2) rectangle  (30/2, 20/2);
\draw (0,0) circle (15/2);
\draw[rounded corners,red] (-50/2, -40/2) rectangle (50/2,40/2);
\draw[rounded corners,red] (-70/2, -60/2) rectangle (70/2,60/2);
\draw[rounded corners,thick] (-90/2, -80/2) rectangle (90/2,80/2);
\node (0,0) {$F_{n-1}$};
\node at (-50,0) {$H_n$};

\end{tikzpicture}
\end{center}
\end{frame}











\begin{frame}
\begin{center}
\begin{tikzpicture}[scale=0.1]




\draw [rounded corners] (-30/2,-20/2) rectangle  (30/2, 20/2);
\draw (0,0) circle (15/2);
\draw[rounded corners,red] (-50/2, -40/2) rectangle (50/2,40/2);
\draw[rounded corners,red] (-70/2, -60/2) rectangle (70/2,60/2);
\draw[rounded corners,thick] (-90/2, -80/2) rectangle (90/2,80/2);
\node (0,0) {$F_{n-1}$};
\node at (-50,0) {$H_n$};








\draw[fill=black]  (0,32) circle (15/2);
\draw[fill=black]  (17,25) circle(15/2);
\draw [fill=black] (35,30) circle(15/2);
\draw [fill=black]( -17,30) circle(15/2);
\draw [fill=black] (-33,24) circle(15/2);
\draw [fill=black] (-10,13) circle(15/2);
\draw [fill=black] (-30,5) circle(15/2);
\draw [fill=black] (-35,-15) circle(15/2);
\draw [fill=black] (-14,-14) circle(15/2);
\draw [fill=black] (-30,-30) circle(15/2);
\draw [fill=black] (-5,-28) circle(15/2);
\draw [fill=black] (20,-28) circle(15/2);
\draw [fill=black] (12,-13) circle(15/2);
\draw [fill=black] (17,8) circle(15/2);
\draw [fill=black] (36,10) circle(15/2);
\draw [fill=black] (34,-13) circle(15/2);


\end{tikzpicture}
\end{center}
\end{frame}








\begin{frame}
\begin{center}
\begin{tikzpicture}[scale=0.1]




\draw [rounded corners] (-30/2,-20/2) rectangle  (30/2, 20/2);
\draw (0,0) circle (15/2);
\draw[rounded corners,red] (-50/2, -40/2) rectangle (50/2,40/2);
\draw[rounded corners,red] (-70/2, -60/2) rectangle (70/2,60/2);
\draw[rounded corners,thick] (-90/2, -80/2) rectangle (90/2,80/2);
\node (0,0) {$F_{n-1}$};
\node at (-50,0) {$H_n$};








\draw[fill=black]  (0,32) circle (15/2);
\draw[fill=black]  (17,25) circle(15/2);
\draw [fill=black] (35,30) circle(15/2);
\draw [fill=black]( -17,30) circle(15/2);
\draw [fill=black] (-33,24) circle(15/2);
\draw [fill=black] (-10,13) circle(15/2);
\draw [fill=black] (-30,5) circle(15/2);
\draw [fill=black] (-35,-15) circle(15/2);
\draw [fill=black] (-14,-14) circle(15/2);
\draw [fill=black] (-30,-30) circle(15/2);
\draw [fill=black] (-5,-28) circle(15/2);
\draw [fill=black] (20,-28) circle(15/2);
\draw [fill=black] (12,-13) circle(15/2);
\draw [fill=black] (17,8) circle(15/2);
\draw [fill=black] (36,10) circle(15/2);
\draw [fill=black] (34,-13) circle(15/2);






\draw [fill=black](-22,18) circle (8/2);
\draw [fill=black](-25,-7) circle (8/2);
\draw [fill=black](-17,0) circle (8/2);
\draw [fill=black](-18,-26) circle (8/2);
\draw [fill=black](-1,-15) circle (8/2);
\draw [fill=black](8,-25) circle (8/2);
\draw [fill=black](25,-2) circle (8/2);
\draw [fill=black](28,20) circle (8/2);
\draw [fill=black](3,18) circle (8/2);


\end{tikzpicture}
\end{center}
\end{frame}




\begin{frame}
\begin{center}
\begin{tikzpicture}[scale=0.1]




\draw [rounded corners] (-30/2,-20/2) rectangle  (30/2, 20/2);
\draw (0,0) circle (15/2);
\draw[rounded corners,red] (-50/2, -40/2) rectangle (50/2,40/2);
\draw[rounded corners,red] (-70/2, -60/2) rectangle (70/2,60/2);
\draw[rounded corners,thick] (-90/2, -80/2) rectangle (90/2,80/2);
\node (0,0) {$F_{n-1}$};
\node at (-50,0) {$H_n$};








\draw[fill=black]  (0,32) circle (15/2);
\draw[fill=black]  (17,25) circle(15/2);
\draw [fill=black] (35,30) circle(15/2);
\draw [fill=black]( -17,30) circle(15/2);
\draw [fill=black] (-33,24) circle(15/2);
\draw [fill=black] (-10,13) circle(15/2);
\draw [fill=black] (-30,5) circle(15/2);
\draw [fill=black] (-35,-15) circle(15/2);
\draw [fill=black] (-14,-14) circle(15/2);
\draw [fill=black] (-30,-30) circle(15/2);
\draw [fill=black] (-5,-28) circle(15/2);
\draw [fill=black] (20,-28) circle(15/2);
\draw [fill=black] (12,-13) circle(15/2);
\draw [fill=black] (17,8) circle(15/2);
\draw [fill=black] (36,10) circle(15/2);
\draw [fill=black] (34,-13) circle(15/2);






\draw [fill=black](-22,18) circle (8/2);
\draw [fill=black](-25,-7) circle (8/2);
\draw [fill=black](-17,0) circle (8/2);
\draw [fill=black](-18,-26) circle (8/2);
\draw [fill=black](-1,-15) circle (8/2);
\draw [fill=black](8,-25) circle (8/2);
\draw [fill=black](25,-2) circle (8/2);
\draw [fill=black](28,20) circle (8/2);
\draw [fill=black](3,18) circle (8/2);



\draw[fill=black] (-19,7)circle (4/2);
\draw[fill=black] (-21,11)circle (4/2);
\draw[fill=black] (-11,-4)circle (4/2);
\draw[fill=black] (-10,2)circle (4/2);
\draw[fill=black] (-6,-8)circle (4/2);
\draw[fill=black] (11,-2)circle (4/2);
\draw[fill=black] (17,-3)circle (4/2);
\draw[fill=black] (21,-8)circle (4/2);
\draw[fill=black] (22,-14)circle (4/2);
\draw[fill=black] (1,10)circle (4/2);
\draw[fill=black] (6,9)circle (4/2);
\draw[fill=black] (11,17)circle (4/2);
\draw[fill=black] (8,13)circle (4/2);
\draw[fill=black] (2.5,-9.5)circle (4/2);


\end{tikzpicture}
\end{center}
\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$. 
\medskip


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

\[
\Lambda_n F_{n-1}=\lambda^n_1 F_{n-1},\dots, \lambda^n_{s(n)} F_{n-1}, 
\]

\[
\alpha_n  F_{n-1},
\beta_n  F_{n-1},
\gamma_n F_{n-1}.
\]
\medskip


$F_n$ will have two distiguished points $a_n$, $b_n$:

\begin{equation*}
\begin{split}
a_n&= \alpha_n a_{n_1}\\
b_n&=\beta_n b_{n-1}
\end{split}
\end{equation*}





\end{frame}



\begin{frame}
We let $\Delta_n F_n$ be the copies of $F_n$ placed in the construction.
\medskip

We define a coloring of $G= \bigcup_n \Delta_n \Lambda_n b_{n-1}$ inductively.
We extend $c_{n-1}$ to $c_n$ by coloring all the points of $\Delta_{n-1}a_{n-1}$,
$\Delta_{n-1}b_{n-1}$ except those in $\Delta_n a_n$, $\Delta_n b_n$,
$\Delta_n\Lambda_n$.
\medskip


We maintain {\color{red}local recognizability}
of the $\Delta_n$ points:
\medskip


There is an $A \subseteq \gamma_{n-1} F_{n-1}\cap \dom(c_n)$ such that for any $c$ extending $c_n$
and any $g \in G$, if $c(ga)=c(a)$ for all $a \in A$, then $g \in \Delta_n$.
\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 $\bigcup_n c_n$ to a $2$-coloring $c$. We color the  points of 
$\bd_n \{ \lambda^n_1,\dots, \lambda^n_{s(n)}\} b_{n-1}$ to take care of
the 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}



\begin{frame}

\section{Further Results}

Using these marker methods we can get other results connecting the algebraic properties 
of the group with the dynamics of the group action.
\mys



\begin{thm}
There is a minimal $2$-coloring, in fact the set of such $x$ is dense.
\end{thm}
\medskip


It is easy to see that the set of $2$ colorings is always $\bs^0_2$ hard,
and that it is a $\bp^0_3$ set.
\mys



\begin{thm}
For any $G$, the set of minimal elements is $\bp^0_3$-complete.
\end{thm}
\mys


For the set of $2$-colorings, the complexity depends on the properties of the group.
\end{frame}


\begin{frame}
\frametitle{flecc groups}


\begin{defn}
$G$ is {\color{red} flecc} if there is a finite set $A\subseteq G-\{1_g\}$
such that for all $g \in G-\{ 1_G\}$ there is an $i \in \Z$ and an $h \in G$
such that $h^{-1}g^i h \in A$. 
\end{defn}



For $g \in G$, let ${\color{red}\ecc(g)}=\bigcup_n \{ h^{-1} g^n h \colon h \in G\}$. 
\mys

Let ${\color{red}\lecc(g)}= \bigcap_n \ecc(g^n)-\{ 1_G\}$ if $g$ has infinite order
and otherwise any $\ecc(g^k)-\{ 1_G\}$ where $g^k$ is of prime order is a $\lecc$
of $g$. 
\mys


\begin{fact}
Any two $\lecc{}s$ which intersect must coincide.
\end{fact}
\end{frame}


\begin{frame}
\begin{thm}
If $G$ is flecc then the set of $2$-colorigs of $G$ is $\bs^0_2$. If $G$ is 
non-flecc then the set of $2$-colorings of $G$ is $\bp^0_3$-complete.
\end{thm}
\mys


Suppose $G$ is flecc. Let $A \subseteq G-\{ 1_G\}$ be finite and witness $G$
is flecc. Then $x \in 2^G$ is a $2$-coloring iff for every $s \in A$ 
$x$ blocks $s$, that is
\[
\exists T \in G^{<\omega}\ \forall g \in G\ \exists t \in T\ [c(gt)\neq c(gst)].
\]
\mys


This is because if $x$ blocks $s^i \neq 1_G$ for some $i$ then $a$ blocks $s$,
and $x$ blocks $s$ iff $x$ blocks $h^{-1}sh$ for all $h\in G$. 
\end{frame}



\begin{frame}
\frametitle{Some Properties of Flecc Groups}
\begin{itemize}
\item
If $G\times H$ is flecc, then $G$, $H$ are flecc.
\item
If $G$ is flecc and $H$ is a torsion flecc group, then $G \times H$ is flecc.
\item
If $G$ is flecc and $H \unlhd G$, then $H$ is flecc.
\item
If $T$ is is the torsion subgroup of a flecc group, then $G/T$ is flecc.
\item
An abelian group is flecc iff it is a finite sum of quasicyclic groups
$\Z(p^\infty)$ and finite cyclic groups.
\end{itemize}



\begin{ques}
Is a product of two flecc groups a flecc group? Is the quotient of a flecc group
a flecc group?
\end{ques}


\begin{ques}
If the set of minimal $2$-colorings for a non-flecc group $\bp^0_3$-complete?
\end{ques}
\end{frame}



\begin{frame}
\frametitle{Topological Conjugacy}


\begin{defn}
We say subflows  $S_1,S_2 \subseteq 2^G$ are topologically conjugate if there is
a homeomorphism $\varphi \colon S_1 \to S_1$ satisfying 
$\varphi(g \cdot x)=g \cdot \varphi(x)$.
\end{defn}
\mys



Let $S(G)=\{ A \subseteq 2^G \colon A \text{ is a subflow } \}$. $S(G)$ 
is a compact Polish space. 
\mys


We consider also:

\begin{equation*}
\begin{split}
S_F(G)&=\text{ the set of free subflows} \\
S_M(G)&=\text{ the set of minimal subflows}\\
S_{MF}(G)&=\text{ the set of minimal free subflows}
\end{split}
\end{equation*}
\end{frame}




\begin{frame}
These sets are all standard Borel spaces. 
\mys



Let $TC(G)$ be the topological conjugacy relation on $S(G)$, and let 
$TC_F(G)$, $TC_M(G)$, $TC_{MF}(G)$ be the restrictions to the above sets. 
\mys


\begin{fact}
These are all countable Borel equivalence relations.
\end{fact}

We have the following reductions:
\mys



\begin{center}
\begin{tikzpicture}


\node[left] at (-2,0) {$TC_{MF}(G)$};
\node[above] at (0,1) {$TC_F(G)$};
\node[right] at (2,0) {$TC(G)$};
\node[below] at (0,-1) {$TC_M(G)$};


\draw (-2,0) --(0,1);
\draw (-2,0) --(0,-1);
\draw (0,1) --(2,0);
\draw (0,-1) --(2,0);
\end{tikzpicture}
\end{center}
\end{frame}


\begin{frame}
\begin{thm}
$E_0$ continuously embeds into $TC_{MF}(G)$ (and so into $TC_{M}(G)$, $TC_F(G)$,
$TC(G)$).
\end{thm}



\begin{thm}
If $G$ is locally finite then $TC(G)$ is Borel reducible to $E_0$ 
(and so also are $TC_{MF}(G)$,  $TC_{M}(G)$, $TC_F(G)$).
\end{thm}


\begin{thm}
Let $G$ be a nonlocally finite group. Then $TC_F(G)$ (and so $TC(G)$) is a 
universal countable Borel equivalence relation.
\end{thm}


\begin{rem}
Clemens showed first that $TC(\Z^n)$ is a universal countable Borel
equivalence relation, and also independently obtained the last two results.
\end{rem}


\begin{ques}
What is the complexity of $TC_M(G)$, $TC_{MF}(G)$?
\end{ques}
\end{frame}



\section{Supercolorings}

\begin{frame}
\frametitle{Supercolorings}


\begin{defn}
A {\color{red}super $2$-coloring} of $G$ is a $2$-coloring in which $|T(s)|$
is bounded independently of $s$. 
\end{defn}
\medskip


$2$:coloring:
\[
\forall s \neq 1_G\ \exists T(s) \in G^{<\omega}\ \forall g \in G\ 
\exists t \in T(s)\ ( c(gt)\neq c(gst))
\]

Super $2$-coloring:
\[
\exists n\ \forall s \neq 1_G\ \exists T(s) \in G^n\ 
\forall g \in G\ 
\exists t \in T(s)\ ( c(gt)\neq c(gst))
\]

\begin{rem}
We can't make $T(s)$ independent of $s$.
\end{rem}
\end{frame}

\begin{frame}
We say $c$ is a super $2$-coloring of degree $n$ if the $T(s)$ have size $n$.
\mys

A topological definition:


\begin{defn}
For $A \subseteq 2^G$ we define the {\color{red}$n$-closure} of $A$ by:

\[
y \in \ncl{n}{A} \Leftrightarrow \forall F \in G^n\ \exists x \in A \ 
(y \res F=x\res F).
\]
\end{defn}

\begin{itemize}
\item
$\ncl{1}{A} \supseteq \ncl{2}{A} \supseteq \cdots 
\ncl{n}{A} \supseteq \cdots \supseteq \ncl{\infty}{A}
=\overline{A}$.
\item
Each $\ncl{n}{A}$ is a closed set.
\item
Each $\ncl{n}{[x]}$ is a closed invariant set in $2^G$ (i.e., is a subflow).
\item
$\ncl{1}{[x]}=2^G$ unless $x$ is the constant $0$ or constant $1$ element.
\end{itemize}

\end{frame}


\begin{frame}
We say $x \in 2^G$ is an {\color{red}$n$-free orbit} if 
$\ncl{n}{[x]} \subseteq F(2^G)$.
\mys

\begin{fact}
If $G$ has super $2$-coloring of degree $n$ (i.e., $|T(s)|=n$),
then there is an orbit $[x]$ with $\ncl{2n}{[x]} \subseteq F(2^G)$.
\end{fact}




So, the existence of a super $2$-coloring on $G$ implies the existence of a $2n$-free orbit.
\mys



\begin{proof}
Let $x \in 2^G$ be a super $2$-coloring of degree $n$. Let $y \in \ncl{2n}{[x]}$. To
show $y \in F(2^G)$, fix $s \neq 1_G$. Let $T=T(s)$ of size $n$ be as in super $2$-coloring.
\mys


Let $F=T\cup sT$. Let $g \in G$ be such that $y \res F= g^{-1}\cdot x \res F$. 
Let $t \in T$ be such that $x(gt)\neq x(gst)$. Then 
$y(t)=x(gt)\neq x(gst)=y(st)$, so $s^{-1}\cdot y \neq y$. 



\end{proof}






\end{frame}

\begin{frame}
So, 
\mys

\begin{tabular}{l}
 There is a super $2$-coloring of degree $n$ of $G$\\
 $\Rightarrow$ There exists a $2n$-free orbit\\
 $\Rightarrow$ There is a free orbit\\
 $\Leftrightarrow$ There is a $2$-coloring of $G$.
\end{tabular}
\mys



\begin{ques}
Which groups admit super $2$-colorings? Which shift actions admit 
$n$-free orbits?
\end{ques}

\begin{rem}
It was open for a while whether $\Z$ has a super $2$-coloring.
\end{rem}

\end{frame}

\begin{frame}
\frametitle{Connection with combinatorics}
The failure of $G$ to have a super $2$-coloring inplies a Van DerWaerden-type
result for colorings of $G$:
\mys


If $x \colon G \to \{ 0, 1\}$, then for any $n\in \N$ there is an $s \in G$ and a  $g \in G$ 
such that \[ x(g)=x(sg)=x(s^2g)=\cdots =x(s^ng).\]
\mys

For $G=\Z$ this statement implies VanDerWaerden's theorem (for two colorings). 
\end{frame}


\begin{frame}
For a general $G$ we can define its supercoloring or $n$-free orbit degree.
\mys


\begin{itemize}
\item
$n_f(G)$ is the least ``integer'' $n$ in $\{ 2,3,\dots\} \cup \{ \infty\}$ such that 
$G$ has an $n$-free orbit.
\item
$n_s(G)$, if it exists, is the least integer $n$ such that $G$ has a super $2$-coloring of degree $n$.
\end{itemize}
\mys


So, if $n_s(G)$ exists, then $n_f(G)$ is finite and $n_f(G)\leq 2n_s(G)$. 
\end{frame}


\section{Supercoloring Results}

\begin{frame}
We showed that $\Z$ has a $3$-free orbit.
\mys

H.\ Li showed that $\Z$ has a supercoloring of degree $13$.
\mys

So, $n_s(\Z)\leq 13$, $n_f(\Z)\leq 3$. 
\end{frame}

\begin{frame}
\frametitle{Other Results}

\begin{itemize}
\item
If $G=\oplus_{i=1}^\infty G_i$ with each $G_i$ nontriviasl, then $G$ has a super $2$-coloring of degree $5$.
\item
A free product or groups $G_1$ with $|G_0|\geq 5$ has a super $2$-coloring of degree $6$.
\item
If $\Z \unlhd G$, then $G$ has a $7$-free orbit.
\end{itemize}



Also, $\Z$ has a {\color{red}perfect set} of $5$-free orbits.
\mys


\begin{ques}
Does every group has a super $2$ coloring (of some degree)? Does it have an 
$n$-free orbit?
\end{ques}










\end{frame}










\end{document}
