Submission date: 13 April 2020

Abstract:

It has been conjectured that the class of first-order reducts of finitely bounded homogeneous Ramsey structures enjoys a CSP dichotomy; that is, the Constraint Satisfaction Problem of any member of the class is either NP-complete or polynomial-time solvable. The algebraic methods currently available that might be used for confirming this conjecture, however, only apply to structures of the class which are, in addition, model-complete cores. We show that the model-complete core associated with any member of this class again belongs to the class, thereby removing that obstacle. Our main result moreover answers several open questions about Ramsey expansions: in particular, if a structure has an ω-categorical Ramsey expansion, then so do its model companion and its model-complete core.

Mathematics Subject Classification:

Keywords and phrases:

Full text arXiv 2004.05936: pdf, ps.