1. χ_{BM}(G_T)≤3

problem

Let $X$ be a Polish space and let $T\colon X→X$ be a Borel map without fixed points. Fill in the details of the proof that $χ_{BM}(G_T)≤3$ sketched in class.

Here’s the outline of how the proof goes:

• Find a Borel set $A⊆X$ so that the set of vertices

  $$X' ≔ \{x∈X : \text{\((x,Tx,T²x,…)\) visits $A$ and $A^∁$ both infinitely often}\}$$

  is comeager (in $X$).

  To do so, start with a countable Borel proper coloring $c\colon X→ℕ$. Partition $X$ into two subsets $P,P^∁$.

  $$\begin{aligned} P &= \{x : \text{\((c(Tⁿx))_{n=0}^∞\) decreases infinitely often}\}, \\ P^∁ &= \{x : \text{\((c(Tⁿx))_{n=0}^∞\) eventually only increases}\}. \end{aligned}$$

  We will construct $A₀⊆P$ and $A₁⊆P^∁$, then set $A=A₀∪A₁$:

  • Take $A₀=\{x∈P:c(Tx)<c(x)\}$.

  • Within $P^∁$, for each $x∈X$ let $C(x)=\{c(Tⁿx)\}_{n∈ℕ}$ (the set of all colors in the $T$-orbit of $x$), and let

    $$𝒮(x) ≔ \{S∈2^ℕ : \text{\([C(x)∩S],[C(x)∖S]\) both infinite}\}.$$

    Equivalently, $S∈𝒮(x)$ if and only if $(Tⁿx)_{n=0}^∞$ visits $c⁻¹(S)$ and $c⁻¹(S)^∁$ both infinitely often, i.e., $(c(Tⁿx))_{n=0}^∞$ visits $S$ and $S^∁$ both infinitely often.

    Observe that for each fixed $x∈P^∁$, $𝒮(x)$ is comeager in $2^ℕ$. Then by Kuratowski–Ulam, for generic $S∈2^ℕ$,

    $$Y(S) ≔ \{x∈P^∁ : \text{\([C(x)∩S],[C(x)∖S]\) both infinite}\}$$

    is comeager in $P^∁$. So fix such an $S$ and let $A₁=c⁻¹(S)$.

  So $A=A₀∪A₁$ is the set of points satisfying

  • if $(c(Tⁿx))_{n=0}^∞$ decreases infinitely often, then $c(Tx)<c(x)$;
  • if $(c(Tⁿx))_{n=0}^∞$ eventually only increases, then $c(x)∈S$.

  Then $A^∁=(P∖A₀)∪(P^∁∖A₁)$ is the set of points $x$ satisfying

  • if $(c(Tⁿx))_{n=0}^∞$ decreases infinitely often, then $c(Tx)>c(x)$;
  • if $(c(Tⁿx))_{n=0}^∞$ eventually only increases, then $c(x)∉S$.

  To see that $X'$ is comeager, notice that if $x∈X'^∁$ then it can only fail the second case (where $x∈P^∁$), and so $x∈P^∁∖Y(S)$. So $X'^∁⊆P^∁∖Y(S)$, but recall that $Y(S)$ is comeager in $P^∁$, so $X'$ is comeager as well.

• $X'$ and $X'^∁$ are $T$-invariant, which means that there are no edges between $G_T[X']$ and $G_T[X'^∁]$. So color these components separately:

  • In $X'$, both $A$ and $A^∁$ are recurrent, so use the Borel construction to $3$-color $G_T[X']$.

  • $X'^∁$ is comeager, so $3$-color it arbitrarily (using the general result that $χ(G_T)≤3$, via De Bruijn–Erdős).