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



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


\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{
March 24, 2011\\
College Station}


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


Every orbit closure $[x]$ is a subflow.
\medskip


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


We say $A$ is a {\color{red}minimal} subflow if $A$ does not properly contain any subflows. 
So, $A=\overline{[x]}$ for all $x \in A$. 
\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{defn}
A {\color{red}super $2$-coloring} of $G$ is a $2$-coloring in which $|T(s)|$
is bounded independently of $s$.
\end{defn}

We say a group is $2$-colorable (super $2$-colorable) if it has a 
$2$-coloring (super $2$-coloring).


\begin{rem} We can't require that $T(s)$ be independent of $s$.
\end{rem}


\end{frame}





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




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



\begin{thm}
$G$ is $2$-colorable iff $2^G$ has a free subflow.
\end{thm}




\end{frame}



\begin{frame}


\begin{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 \leq 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{proof}
\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)
\]
\end{frame}


%\subsection{n-free orbits}

\begin{frame}

Recall in a super $2$-coloring we bound the size of $|T(s)|$ independently of $s$. 
\mys


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

So, $\ncl{1}{A} \supseteq \ncl{2}{A} \supseteq \cdots \ncl{n}{A} \supseteq \cdots \supseteq \ncl{\infty}{A}
=\overline{A}$.
\mys


Each $\ncl{n}{A}$ is a closed set.
\mys


Each $\ncl{n}{[x]}$ is a closed invariant set in $2^G$ (i.e., is a subflow).
\mys


Note that $\ncl{1}{[x]}=2^G$ unless $x$ is the constant $0$ or constant $1$ element.
\end{frame}


\begin{frame}

\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 $n$-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 $2$-colorings or super $2$-colorings. Which shift actions admit 
$n$-free orbits?
\end{ques}

\end{frame}


\begin{frame}

\begin{thm}[GJS]
Every countable group $G$ has a $2$-coloring.
\end{thm}


\begin{cor}
Every shift action of a countable group $G$ has a free subflow.
\end{cor}




On the other hand, we don't know the answer to the following:
\mys

\begin{ques}
Does $\Z$ have a super $2$-coloring?
\end{ques}
\mys


We do know that there are groups $G$ which admit super $2$-colorings.
\end{frame}



\begin{frame}


However, it is easy to see:

\begin{fact}
$2^\Z$ has a $3$-free orbit.
\end{fact}


\begin{proof}
Define a sequence $s_n \in 2^{[\ell_n, r_n]}$, for some $\ell_n, r_n$, as follows. 
\mys


Let $s_1=0101$, where $\ell_1=-2$, $r_1=1$. 
\mys



Each $s_{n+1}$ will be a concatenation of copies of $s_n$ and $\bas_n$ (the digit flip of $s_n$).
\mys


First, concatenate copies of $s_n$ to get $s'_{n+1}$ which has length a multiple of 
$n+1$. Then let $s_{n+1}= \bas'_{n+1} \conc s'_{n+1} \conc \bas'_{n+1}$.
\end{proof}


\end{frame}

\subsection{Direct Sums}

\begin{frame}

\begin{thm}
Let $G= \oplus_{i=1}^\infty G_i$ where each $G_1$ is non-trivial. Then 
$G$ has a super $2$-coloring of degree $5$.
\end{thm}




Fix an injection $\pi \colon G \to \omega$ with $\pi(g)> |g|= \max \supp (g)$.
Let $\pi'(g)=\pi(g)+1$. 
For $s \neq 1_G$, let $\sigma(s)$, $\sigma'(s)$  be a non-identity element of 
$G_{\pi(s)}$, $G_{\pi'(s)}$. 
\mys



{\color{blue}\underline{idea}}: $\sigma(s)$ will serve as a ``switch'' for the shift $s$, turning on or off 
a contribution pertaining to $s$ in the coloring.
\mys

For $s \neq 1_G$, let $m(s)=\min \supp(s)$.
\mys
\end{frame}



\begin{frame}
For each $G_i$ and $h\neq 1_{G_i}$ in $G_i$ we define a coloring $\chi_{i,h}$ of 
$G_i$ by: 
\mys


Fix coset representatives (containing $1_{G_i}$) in $G_i$ for $\langle h \rangle$. 
\mys

Let $\chi_{i,h}(g)=
0$ if the least $n$ such that $g= xh^n$ is even, where $x$ is a coset representative,
and $=1$ if $n$ is odd. 
\mys








We set:

\[
\begin{split}
x(g)= & \sum_{h \neq 1_G} \chi_{\pi(h),\sigma(h)}(g(\pi(h))) \cdot \chi_{m,h(m)}(g(m))\\
& \qquad  + \chi_{\pi'(h),\sigma'(h)}(g(\pi'(h))) \cdot \chi_{m,h^{-1}(m)}(g(m))
\end{split}
\]
where $m=m(h)$.
\mys



Note that the above sum is a finite sum.



\end{frame}




\begin{frame}
To show $x$ is a super $2$-coloring, fix $s \neq 1_G$. 
\mys


Let $T(s)=\{ 1_G, \sigma(s), \sigma^2(s), \sigma'(s), {\sigma'}^2(s)\}$.
\mys


Let $g \in G$, and assume that $x(g) = x(gs)$. 
Select either $\pi(s)$ or $\pi'(s)$ depending on whether 
$ \chi_{m,s(m)}(g(m))\neq  \chi_{m,s(m)}(gs(m))$ (where $m=m(s)$)
or 
$ \chi_{m,s(m)}(g(m))\neq  \chi_{m,s^{-1}(m)}(gs(m))$.
\mys



Say the first holds.
\mys

Consider either $\sigma(s)$ or $\sigma^2(s)$ depending on whether 
$\chi_{\pi(s),\sigma(s)}(g(\pi(s))) \neq \chi_{\pi(s),\sigma(s)}(g \sigma(s)(\pi(s))) $.
\mys

Say the first holds.
\mys


Then $x(g\sigma)\neq x(gs\sigma)$.
\end{frame}


\subsection{Free Products}

\begin{frame}

\begin{thm}
A free product of groups $G_i$ with $|G_0|\geq 5$ has a super $2$-coloring 
of degree $6$.
\end{thm}


\begin{cor}
Every free group on $\geq 2$ generators has a super $2$-coloring.
\end{cor}
\mys





{\color{blue}Proof.}
For simplicity, assume $G=G_0 \fp G_1$.
\mys


Let $a_0,a_1,a_2,a_3$ be non-identity elements of $G_0$. 
\mys


Let $b_0$ be a non-identity element of $G_1$.
\mys

A {\color{red} code word} is a word of the form 
\[
(g\neq 1,a_0) b_0 a_0 b_0 \cdots a_0 b_0 (g\neq 1,a_0) b_0 a_0 b_0 \cdots a_0 b_0
\]
\end{frame}




\begin{frame}
Define the coloring $x$ of $G$ as follows.
\mys



If $g\in G$ does not end in a code word, set $x(g)=0$.
\mys


Suppose 

\[
\begin{split}
g=& (g_0) h_1 g_1 h_1 \cdots g_k h_k\cdot \\ &
(g\neq 1,a_0) b_0 a_0 b_0 \cdots a_0 b_0 (g\neq 1,a_0) b_0 a_0 b_0 \cdots a_0 b_0.
\end{split}
\]
\mys


Say there are $i, j$ occurrences of $b_0$ in the two segments of the code word. 
\mys
\end{frame}


\begin{frame}


If $j \notin [1,10]$, then set $x(g)=0$. Let
\mys 

\[
g'=(g_0) h_1 g_1 h_1 \cdots g_k h_k g a^{-1}_{j/2-2},
\]

if $j$ is even (where $a_{-1}=1_{G_0}$) and for $j$ odd use $a^{-1}_{(j+1)/2-2}$.
\mys


Let $s$ be the $i^{\text{th}}$ non-identity element of $G$. 
\mys


Then if $j$ is even let $x(g)=\chi_s(g')$, which as before is the coloring using coset representatives 
for $\langle s\rangle$ (if $j$ is odd, use $\chi_{s^{-1}}(g')$). 
\end{frame}




\begin{frame}
To see this works, fix $s \neq 1_G$.
\mys



Let $T(s)$ be $1_G$ together with all elements of the form 

\[
\{a_{-1},\dots,a_3\} b_0a_0b_0\cdots a_0 b_0\cdot a_1 b_0 a_0 b_0\cdots a_0 b_0
\]

where if $i,j$ are as before, then the $i^{\text{th}}$ non-identity element is 
$s$, and $j \in [1,10]$. There at most $51$ such elements. 
\mys



Given $g \in G$, consider $g, gs$. At least one of $a_{-1},\dots,a_3$ has the property 
$ga_k$ and $gsa_k$ both end with a term $g \in G_0$, $g \notin \{ 1_{G_0}, a_0\}$. 
\mys


Let $w$ be the codeword coding this $i$ and where $j$ codes this value of $k$
and is even or odd depending on whether $\chi_s(g)\neq \chi_s(gs)$ or 
 $\chi_{s^{-1}}(g)\neq \chi_{s^{-1}}(gs)$.
\end{frame}




\begin{frame}
Let $t=a_k w \in T(s)$.
\mys


Then $(gt)'=g$ and $(gst)'=gs$, and so $x(gt)\neq x(gst)$.
\mys



\begin{cor}
Every free product of infinite groups has an $n$-free orbit for some $n$.
\end{cor}
\end{frame}


\subsection{Orthogonality}


\begin{frame}

\frametitle{more on n-free orbits}



\begin{defn}
We say $x,y \in 2^G$ are {\color{red}orthogonal}, $x \perp y$, if there is a finite $T \subseteq G$
such that for any $g_1,g_2 \in G$, there is a $t \in T$ with 
$x(g_1 t)\neq y(g_2t)$. 
\end{defn}



We say a family $x_{\alpha}$, $\alpha \in 2^\omega$ is strongly pairwise orthogonal 
if whenever $\alpha \neq \beta$ then $x_\alpha \perp x_\beta$, and the set 
$T_{\alpha,\beta}$ depends only on $\min \{ n \colon \alpha(n)\neq \beta(n)\}$. 
\mys



\begin{thm}[GJS]
For any countable group $G$ there is {\color{red}strongly pairwise orthogonal} family of 
$2$-colorings of $G$.
\end{thm}



\begin{cor}
For any $G$, there is a perfect set of pairwise disjoint free subflows of $2^G$. 
\end{cor}
\end{frame}



\begin{frame}
So, a natural question would be:



\begin{ques}
For every group $G$, does there exists a perfect set of pairwise disjoint 
$n$-closed free subflows (for some $n$)?
\end{ques}
\mys


This is equivalent to saying there is a perfect set $x_\alpha$, $\alpha \in 2^\omega$,
of $n$-free colorings such that for all $\alpha \neq \beta$ we have 
$x_\beta \notin \ncl{n}{[x_\alpha]}$.
\mys



We call this a {\color{red} perfect $n$-free set}.
\end{frame}


\subsection{A Partial Result}



\begin{frame}

\begin{thm}
There is a perfect $5$-free set of colorings of $\Z$.
\end{thm}
\mys



To show this, we modify the previous construction of a $3$-free coloring of $\Z$.
\mys



Suppose at stage $n$ we have defined $s_u$ for $u \in 2^n$. For $u' \in 2^{n+1}$
extending $u \in 2^n$, we will have that $s_{u'}$ is a concatenation
of copies of $s_u$ and $\bas_u$.
\mys



First concatenate copies of each $s_u$ for form $t_u$ whose lengths are all (the same)
multiple of $(n+1)!$. 
\mys



Now proceed in $\binom{2^n}{2}$ stages.
\end{frame}



\begin{frame}
For each $u_1 \neq u_2$, concatenate the current $t_{u_1}$
according to the pattern $010101$ and concatenate the current $t_{u_2}$
according to the pattern $001001$. Concatenate the other $t_u$ to have the same length as well. 
\mys



At the end of the $\binom{2^n}{2}$ stages, the current $t_u$ is the new $s_u$.
\mys



This works since any concatenation of $010101$ and its flips cannot agree on $7$
consecutive digits with a concatenation of $001001$ and its flips.
\end{frame}


\begin{frame}


\begin{thm}
Assume $\Z \unlhd G$. Then $2^G$ has a $7$-free orbit.
\end{thm}
\mys



Let $g_0\Z, g_1\Z,\dots$ enumerate the cosets of $\Z$ in $G$, with $g_0=1_G$.
\mys


We construct by induction on $n$ sequences $s^i_n$ for all $i$, which are partial colorings
for $g_i\Z$. The construction is a modification of the previous theorem.
\mys



First extend each $s^i_n$ to $t^i_n$ by concatenating copies of $s^i_n$ so that the length
of $t^i_n$ is a multiple of $s=n+1$.
\mys
\end{frame}


\begin{frame}
Let $\chi_s(g_i) \in \{ 0,1,2\}$ be defined as follows. 
\mys


Let $\bag_i$ be the coset representative in $G/\Z$ of $g_i$ 
with respect to the subgroup $\langle s \rangle \Z$. 
\mys


Set $\chi_s(g_i)=0$ if $g_i\Z= \bag_i s^k \Z$ where $k$ is even and if $s$ has finite 
odd order $r$ in $G/\Z$ then $k \neq r-1$. If $k$ is odd, set $\chi_s(g_i)=1$,
and if $k$ is even and $k=r-1$ with $r$ odd, then set $\chi_s(g_i)=2$. 
\mys

 

Extend $t^i_n$ to $s^i_{n+1}$ by concatenating copies of $t^i_n$ and its flip
according to the pattern $010101010101$ if $\chi_s(g_i)=0$, 
according to $001001001001$ if $\chi=1$, and according to $000100010001$ if $\chi=2$.
\mys

This works since no sub-words of length $7$ from concatenations of these patterns and their flips
can be equal for the three different patterns.
\end{frame}



\begin{frame}

\begin{rem}
The above argument is similar to an argument that showed that if $\Z \unlhd G$ then $G$
has a $2$-coloring. This proof, however, did not generalize to show that all $G$ have 
$2$-colorings.
\end{rem}


Similar aguments might show:


\begin{thm}
Every Abelian group has a $7$-free orbit.
\end{thm}



\begin{conj}
Every countable $G$ has an $n$-free orbit for some $n$.
\end{conj}












\end{frame}





















































































\end{document}
