PDF files of articles are only available for institutions which have paid for the online version upon signing an Institutional User License.

Borel chromatic numbers of graphs of commuting functions

Volume 253 / 2021

Connor Meehan, Konstantinos Palamourdas Fundamenta Mathematicae 253 (2021), 219-237 MSC: Primary 03E15; Secondary 05C15. DOI: 10.4064/fm577-5-2020 Published online: 23 October 2020


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.


  • Connor Meehan7419 19th Ave.
    Burnaby, BC, Canada, V3N 1E2
  • Konstantinos Palamourdas10982 Roebling Ave. #439
    Los Angeles, CA 90024, U.S.A.

Search for IMPAN publications

Query phrase too short. Type at least 4 characters.

Rewrite code from the image

Reload image

Reload image