STRUCTURES WITH NOT TOO FAST UNLABELLED GROWTH
Open Access
- 31 July 2026
- journal article
- research article
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- p. 1-52
Abstract
Let $\mathscr {S}$ script upper S be the class of all structures whose growth rate on orbits of subsets of size $n$ n is not faster than $\frac {2^n}{p(n)}$ StartFraction 2 Superscript n Baseline Over p left parenthesis n right parenthesis EndFraction for any polynomial $p$ p . In this article we give a complete classification of all structures in $\mathscr {S}$ script upper S in terms of their automorphism groups. As a consequence of our classification we show that $\mathscr {S}$ script upper S has only countably many structures up to bidefinability, all these structures are first-order interpretable in $(\mathbb {Q};<)$ left parenthesis double struck upper Q semicolon less than right parenthesis and they are interdefinable with a finitely bounded homogeneous structure. Furthermore, we also show that all structures in $\mathscr {S}$ script upper S have finitely many first-order reduct up to interdefinability, thereby confirming Thomas’ conjecture for the class $\mathscr {S}$ script upper S .