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

2. Complexity of combinatorial questions and dichotomy theorems


    1. Add remark

      Problem 2.1.

      Are the following decidable?
      1. Given a finite set of tiles in $\Z^n$, is there a continuous tiling of $F(2^{\Z^n})$ with those tiles?
      2. Same as a, but where we are given that there is a (not necessarily definable) tiling. I.e, a tiling of the Cayley graph with those tiles.
          The answer to (a) is no if there are no definability constraints.


        • Add remark

          Problem 2.2.

          Is there a dichotomy characterizing which Borel graphs admit Borel orientations for which every vertex has finite out degree?


            • Add remark

              Problem 2.3.

              What is the complexity of the set of pmp graphs admitting a measurable 3-coloring?


                • Add remark

                  Problem 2.4.

                  Let $G$ be an acyclic analytic Borel graph with uncountable Borel chromatic number. Is there an injective continuous reduction $f$ from $\mathbb{G}_0$ to $G$ ($x \mathbb{G}_0 y$ iff $f(x) G f(y)$)?
                      The answer is yes if $G$ is contained in a potentially $F_\sigma$ acyclic graph.

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