Structures with Small Orbit Growth

Abstract

Let $K_{exp+}$ be the class of all structures $A$ such that the automorphism group of $A$ has at most $c{n}^{dn}$ orbits in its componentwise action on the set of $n$-tuples with pairwise distinct entries, for some constants $c,d$ with $d<1$. We show that $K_{exp+}$ is precisely the class of finite covers of first-order reducts of unary structures, and also that $K_{exp+}$ is precisely the class of first-order reducts of finite covers of unary structures. It follows that the class of first-order reducts of finite covers of unary structures is closed under taking model companions and model-complete cores, which is an important property when studying the constraint satisfaction problem for structures from $K_{exp+}$. We also show that Thomas' conjecture holds for $K_{exp+}$: all structures in $K_{exp+}$ have finitely many first-order reducts up to first-order interdefinability.

References in corpus (5)

• A Dichotomy for First-Order Reducts of Unary Structures
• Canonical Functions: a proof via topological dynamics
• Homogeneous coloured multipartite graphs
• Second cohomology groups and finite covers
• $2^{{\aleph }_0}$ pairwise non-isomorphic maximal-closed subgroups of Sym$(\mathbb{N})$ via the classification of the reducts of the Henson digraphs

Cited by in corpus (1)

• Monadic stability and growth rates of $\omega$-categorical structures