joint work with S. Lasota, J. Ochremiak and S. Toruńczyk

Consider infinite relational structures where both the universe and the relations are definable by first-order formulas over natural numbers with equality. An example of such a structure is the countable clique graph, or a graph where nodes are 2-element sets of numbers and two nodes are adjacent iff they have interesection of size 1.

Consider the decidability of the homomorphism problem for such structures: given (the finite definitions of) structures A and B over the same signature, is there a homomorphism from A to B? I will explain a few variants of this problem; their landscape of decidability would make Lewis Carroll scratch his head in confusion.