| Register
\(\newcommand{\Cat}{{\rm Cat}} \) \(\newcommand{\A}{\mathcal A} \) \(\newcommand{\freestar}{ \framebox[7pt]{$\star$} }\)

4. Relationships between different definable settings


    1. Add remark

      Problem 4.1.

      Let $d \in \omega$. Given an SFT (sub-shift of finite type) of $\Z^d$, say $S$ (equivalently, given a LCL (locally checkable labelling problem), say $\Pi$), are any of the following equivalent?
      1. $T$ here is a Borel equivariant map $F(2^{\Z^d}) \rightarrow S$. (Equivalently, a Borel $\Pi$-coloring)
      2. “ “ Baire measurable “ “
      3. “ “ $\mu$-measurable “ “, for $\mu$ a given Borel probability measure on $F(2^{\Z^d})$.
          They are all equivalent for $d = 1$.


        • Add remark

          Problem 4.2.

          Let $\Pi$ be a LCL such that every highly computable graph admits a computable $\Pi$-coloring. Does every locally finite Borel graph admit a Baire measurable $\Pi$-coloring?

              Cite this as: AimPL: Descriptive graph theory, available at http://aimpl.org/descriptgraph.