Submission date: 10 November 2018

Abstract:

A sibling of a relational structure R is any structure S which can be embedded into R and, vice versa, in which R can be embedded. Let sib(R) be the number of siblings of R, these siblings being counted up to isomorphism. Thomassé conjectured that for countable relational structures made of at most countably many relations, sib(R) is either 1, countably infinite, or the size of the continuum; but even showing the special case sib(R)=1 or infinite is unsettled when R is a countable tree. This is related to Bonato-Tardif conjecture asserting that for every tree T the number of trees which are sibling of T is either one or infinite.
We prove that if R is countable and ℵ_0-categorical, then indeed sib(R) is one or infinite. Furthermore, sib(R) is one if and only if R is finitely partitionable in the sense of Hodkinson and Macpherson. The key tools in our proof are the notion of monomorphic decomposition of a relational structure introduced in a paper by Pouzet and Thiéry 2013 and studied further by Oudrar and Pouzet 2015, and a result of Frasnay 1984.

Mathematics Subject Classification: 06A, 06B

Keywords and phrases:

Full text arXiv 1811.04185: pdf, ps.