Borel CSP complexity dichotomy conjecture

Let D\mathcal{D} be a finite relational structure, and let CSPB(D)\mathrm{CSP}_B(\mathcal{D}) denote the set of codes for Borel structures admitting Borel homomorphisms into D\mathcal{D}. The projective pointclasses Π11\mathbf{\Pi}^{1}_{1} and Σ21\mathbf{\Sigma}^{1}_{2} classify the complexity of such sets.

Borel CSP dichotomy conjecture. For every D\mathcal{D}, the set CSPB(D)\mathrm{CSP}_B(\mathcal{D}) is either in Π11\mathbf{\Pi}^{1}_{1} or is Σ21\mathbf{\Sigma}^{1}_{2}-complete.

The source says that this dichotomy follows assuming Σ21\mathbf{\Sigma}^{1}_{2}-determinacy, but whether it holds in ZFC is open. It is intended as a descriptive-set-theoretic analogue of the finite CSP dichotomy.

Sources & referencesView supporting material

Primary source

Riley Thornton, “An algebraic approach to Borel CSPs”, arXiv:2203.16712 (2022).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.