Category Archives: topic ideas

Orbit-finite CSPs

Consider the following decision problem (for classical Turing machines). Let \Sigma be a fixed, finite signature.

Input: Two orbit-finite relational structures \str A,\str B, over \Sigma.

Decide: is there a homomorphism from \str A to \str B?

Question 1. Is the above problem decidable?

Observe that we are not asking for the existence of an equivariant homomorphism. If this were the case, the problem would be clearly decidable, since there are only finitely many equivariant homomorphisms between orbit-finite sets, and they can be effectively scanned. In this problem, the homomorphisms do not even have to be finitely supported! Below is an example where a homomorphism exists, but no finitely supported homomorphism exists.

Example. Consider the equality atoms. Let \str A be the graph whose vertices are pairs of distinct atoms, and in which edges join a pair with its inverse. Let \str B be the 2-clique. Then \str A maps to \str B, but no finitely supported homomorphism exists.

Following the idea of this post, in order to solve this problem, it might be useful to move to the totally ordered atoms (\str Q,\le).

Question 2. In the totally ordered atoms, if there is a homomorphism between orbit-finite structures \str A, \str B, is there one which is equivariant?

A positive answer to Question 2 would imply a positive answer to Question 1.

Edit. After reading Bartek’s comment below, I noticed that Question 2 has an even more negative answer. Consider the structures \str A=(\str Q,<) and \str B=(\str Q,>) (orders reversed). There is a homomorphism from \str A to \str B, namely the mapping x\mapsto -x, but there is none which is finitely supported.