Siblings of an \aleph₀-categorical relational structure

zbMATH Open1477.03129arXiv1811.04185MaRDI QIDQ5154973FDOQ5154973

Norbert Sauer, R. E. Woodrow, Maurice Pouzet, Claude Laflamme

Publication date: 5 October 2021

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'e 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 $alep{h}_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'ery 2013 and studied further by Oudrar and Pouzet 2015, and a result of Frasnay 1984.

Full work available at URL: https://arxiv.org/abs/1811.04185

zbMATH Keywords

treeshomogeneityrelational structuresisomorphyequimorphyultrahomogeneityoligomorphic groups

Mathematics Subject Classification ID

Categoricity and completeness of theories (03C35) Model theory of denumerable and separable structures (03C15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Transitivity of permutation groups on unordered sets
• On Fraissé's order type conjecture
• Isomorphy up to complementation
• Sur l'extension aux relations de quelques propriétés des ordres
• Model Companions for ℵ 0 -Categorical Theories
• Countable Ultrahomogeneous Undirected Graphs
• Über die Permutationsgruppe der natürlichen Zahlenfolge
• The morphology of infinite tournaments; application to the growth of their profile
• On Better-Quasi-Ordering Countable Series-Parallel Orders
• Ubiquity in category for metric spaces and transition systems
• A proof of the rooted tree alternative conjecture
• Twins of rayless graphs
• Mutually embeddable graphs and the tree alternative conjecture
• A proof of a partition theorem for [ℚ]ⁿ
• Relational structures determined by their finite induced substructures
• Coinductive ℵ₀-categorical theories
• Some relational structures with polynomial growth and their associated algebras. I: Quasi-polynomiality of the profile
• Countable structures of given age
• Quelques problèmes combinatoires concernant les ordres totaux et les rélations monomorphes
• Large and small existentially closed structures
• The reconstruction of multirelations, at least one component of which is a chain
• Equimorphy: the case of chains
• Relational structures having finitely many full-cardinality restrictions

Cited In (6)

• Bi‐embeddability spectra and bases of spectra
• COUNTING SIBLINGS IN UNIVERSAL THEORIES
• ℵ₀-categorical tree-decomposable structures
• An example of Tateno disproving conjectures of Bonato-Tardif, Thomasse, and Tyomkyn
• A Cantor-Bendixson rank for siblings of trees
• A proof of the alternate Thomassé conjecture for countable \(N\)-free posets

This page was built for publication: Siblings of an $\aleph_0$-categorical relational structure

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5154973)