Structures with not too fast unlabelled growth

Bertalan Bodor

mathematical logic

Structures with not too fast unlabelled growth

arXiv:2507.16985

summary

The paper classifies all relational structures whose orbit‑growth on n‑element subsets is bounded by 2ⁿ divided by any polynomial, describing them via their automorphism groups, showing they are first‑order interpretable in (ℚ,<) and interdefinable with finitely bounded homogeneous structures, and proving they have only finitely many first‑order reducts, thus confirming Thomas' conjecture for this class.

Abstract

Let $S$ be the class of all structures whose growth rate on orbits of subsets of size $n$ is not faster than $\frac{2 ^{n}}{p ( n )}$ for any polynomial $p$ . In this article we give a complete classification of all structures in $S$ in terms of their automorphism groups. As a consequence of our classification we show that $S$ has only countably many structures up to bidefinability, all these structures are first-order interpretable in $(Q; <)$ and they are interdefinable with a finitely bounded homogeneous structure. Furthermore, we also show that all structures in $S$ have finitely many first-order reduct up to interdefinability, thereby confirming Thomas' conjecture for the class $S$ .

Topics & keywords

#orbit growth #automorphism groups #homogeneous structures #first-order reducts #Thomas conjecturegrowth rateautomorphism groupfirst-order interpretabilityfinitely bounded homogeneousbidefinabilitymodel theory