Publishing house / Journals and Serials / Fundamenta Mathematicae / All issues

Abstract

Let $\mathbf{D} = (X, D)$ be a Borel directed graph on a standard Borel space $X$ and let $\chi _B(\mathbf{D})$ be its Borel chromatic number. If $F_0, \ldots , F_{n-1}: X \to X$ are Borel functions, let $\mathbf{D}_{F_0, \ldots, F_{n-1}} $ be the directed graph that they generate. It is an open problem if $\chi _B(\mathbf{D}_{F_0, \ldots, F_{n-1}} ) \in \{1, \ldots , 2n + 1, \aleph _0\}$. This was verified for commuting functions with no fixed points. We show here that for commuting functions with the properties that $\chi _B(\mathbf{D}_{F_0, \ldots, F_{n-1}} ) \lt \aleph _0$ and that there is a path from each $x \in X$ to a fixed point of some $F_j$, there exists an increasing filtration $\{X_m\}_{m \lt \omega }$ with $X = \bigcup _{m \lt \omega } X_m$ such that $\chi _B(\mathbf{D}_{F_0, \ldots, F_{n-1}} {\restriction} X_m) \le 2n$ for each $m$. We also prove that if $n = 2$ in the previous case, then $\chi _B(\mathbf{D}_{F_0, F_1} ) \le 4$. It follows that the approximate measure chromatic number $\chi _M^{ap}(\mathbf{D} )$ does not exceed $2n + 1$ when the functions commute.