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

1. Specific questions for graphs of small degree

Let $G$ be the Schreier graph on $X = F(2^{\F_2})$ (The free part of the 2-shift) induced by the standard generating set. Let $\mu$ be the coin flip measure on $X$. Let $a$ and $b$ be the generators.


    1. Add remark

      Problem 1.1.

      What is the $\mu$-measurable chromatic number of $G$?
          It is either 3 or 4.


        • Add remark

          Problem 1.2.

          What is the approximate $\mu$-measurable chromatic number of $G$?


            • Add remark

              Problem 1.3.

              What is the Borel edge chromatic number of $G$?
                  It is either 5 or 6.


                • Add remark

                  Problem 1.4.

                  What is the $\mu$-measurable edge chromatic number of $G$?
                      It is either 4 or 5.

                    •     Let
                      1. $H = \{\ldots , a^{-1} , 1, a , a^2, \ldots\} = \langle a \rangle \subset \F_2 $
                      2. $ V = \{\ldots , b^{-1}, 1, b , b^2, \ldots\} = \langle b \rangle \subset \F_2$
                      3. $ D = \{\ldots, a^{-1}b^{-1}, b^{-1}, 1, a, ba, aba, \ldots \} \subset \F_2 $

                      Add remark

                      Problem 1.5.

                      Is there a Borel partition of the edges of G, say into A, B, and C, such that
                      1. For all $x \in X$, $H \cdot x$ contains an edge from $A$ (meaning it contains both endpoints of the edge).
                      2. “ “ $V$ “ “ $B$
                      3. “ “ $D$ “ “ $C$
                          There is if we weaken Borel to $\mu$-measurable.

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