Structures with Small Orbit Growth

DOI10.1515/JGTH-2018-0220MaRDI QIDQ6308143arXivFDO

Authors Manuel Bodirsky, Bertalan Bodor

Publication date 12 October 2018

Published in arXiv

Full work available at URL https://doi.org/10.1515/JGTH-2018-0220

Mathematics Subject Classification ID

Categoricity and completeness of theories (03C35) Interpolation, preservation, definability (03C40) Model-theoretic algebra (03C60) General theory for infinite permutation groups (20B07) Infinite automorphism groups (20B27)

arXiv classification

math.GRmath.LO

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.

This page was built for publication: Structures with Small Orbit Growth

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